www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Lazy lists

reply bearophile <bearophileHUGS lycos.com> writes:
A task from the RosettaCode site asks to generate a Sierpinski carpet like
this, on given order:


###########################
# ## ## ## ## ## ## ## ## #
###########################
###   ######   ######   ###
# #   # ## #   # ## #   # #
###   ######   ######   ###
###########################
# ## ## ## ## ## ## ## ## #
###########################
#########         #########
# ## ## #         # ## ## #
#########         #########
###   ###         ###   ###
# #   # #         # #   # #
###   ###         ###   ###
#########         #########
# ## ## #         # ## ## #
#########         #########
###########################
# ## ## ## ## ## ## ## ## #
###########################
###   ######   ######   ###
# #   # ## #   # ## #   # #
###   ######   ######   ###
###########################
# ## ## ## ## ## ## ## ## #
###########################


This is a Scala implementation of a function that prints the carpet:


def nextCarpet(carpet: List[String]): List[String] = (
  carpet.map(x => x + x + x) :::
  carpet.map(x => x + x.replace('#', ' ') + x) :::
  carpet.map(x => x + x + x))
 
def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop n
next) foreach println



A D version that uses arrays:

import std.stdio, std.string, std.algorithm, std.array, std.range;
 
string[] nextCarpet(string[] c) {
    auto b = array(map!q{a ~ a ~ a}(c));
    return b ~ array(map!q{a ~ a.replace("#"," ") ~ a}(c)) ~ b;
}
 
void main() {
    auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]);
    writeln(array(take(c, 4)).back.join("\n"));
}


Few notes:
- I don't know how to take just the 4th item of a lazy sequence. array(take(c,
4)).back is not good.

- recurrence() is a bit overkill. A function like iterate() simplifies the code:
auto c = iterate!nextCarpet(["#"], 4);

- I don't see a simple way to create a lazy nextCarpet(), without those
array(). The seed (["#"]) can't be an array, but even wrapping it with a lazy
map!q{a}(["#"]) solves nothing. chain(map(chain...))) are all different types,
so I think it can't work. The types in that Scala code are sound because it
uses a lazy list type, that supports the ::: operator for concatenation, and
List("#") to create the correctly typed seed. That carpet.map() returns a
List[String]. So both the input and output of the Scala nextCarpet() are of the
same type, List[String]. So such lazy list type template becomes really useful
if you want to program in a lazy functional style.

Bye,
bearophile
Feb 22 2011
next sibling parent spir <denis.spir gmail.com> writes:
On 02/23/2011 03:28 AM, bearophile wrote:
 A task from the RosettaCode site asks to generate a Sierpinski carpet like
this, on given order:


 ###########################
 # ## ## ## ## ## ## ## ## #
 ###########################
 ###   ######   ######   ###
 # #   # ## #   # ## #   # #
 ###   ######   ######   ###
 ###########################
 # ## ## ## ## ## ## ## ## #
 ###########################
 #########         #########
 # ## ## #         # ## ## #
 #########         #########
 ###   ###         ###   ###
 # #   # #         # #   # #
 ###   ###         ###   ###
 #########         #########
 # ## ## #         # ## ## #
 #########         #########
 ###########################
 # ## ## ## ## ## ## ## ## #
 ###########################
 ###   ######   ######   ###
 # #   # ## #   # ## #   # #
 ###   ######   ######   ###
 ###########################
 # ## ## ## ## ## ## ## ## #
 ###########################


 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
    carpet.map(x =>  x + x + x) :::
    carpet.map(x =>  x + x.replace('#', ' ') + x) :::
    carpet.map(x =>  x + x + x))

 def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop
n next) foreach println



 A D version that uses arrays:

 import std.stdio, std.string, std.algorithm, std.array, std.range;

 string[] nextCarpet(string[] c) {
      auto b = array(map!q{a ~ a ~ a}(c));
      return b ~ array(map!q{a ~ a.replace("#"," ") ~ a}(c)) ~ b;
 }

 void main() {
      auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]);
      writeln(array(take(c, 4)).back.join("\n"));
 }


 Few notes:
 - I don't know how to take just the 4th item of a lazy sequence. array(take(c,
4)).back is not good.

 - recurrence() is a bit overkill. A function like iterate() simplifies the
code:
 auto c = iterate!nextCarpet(["#"], 4);

 - I don't see a simple way to create a lazy nextCarpet(), without those
array(). The seed (["#"]) can't be an array, but even wrapping it with a lazy
map!q{a}(["#"]) solves nothing. chain(map(chain...))) are all different types,
so I think it can't work. The types in that Scala code are sound because it
uses a lazy list type, that supports the ::: operator for concatenation, and
List("#") to create the correctly typed seed. That carpet.map() returns a
List[String]. So both the input and output of the Scala nextCarpet() are of the
same type, List[String]. So such lazy list type template becomes really useful
if you want to program in a lazy functional style.

Maybe we should reverse the point of view and start with Range. A base type for anything 'sequential' (iterable) is Range of E (element type). Then, an array E[] is a Range of E that just happens to have its elements pre-stored. Ditto for any other collection. And a slice, or any other kind of 'view' into a collection, is a Range of E that just happens to have direct access to its elements (in memory, via pointer; or via cursor, or whatever). Denis -- _________________ vita es estrany spir.wikidot.com
Feb 22 2011
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
    carpet.map(x =>  x + x + x) :::
    carpet.map(x =>  x + x.replace('#', ' ') + x) :::
    carpet.map(x =>  x + x + x))

 def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop
n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.
 A D version that uses arrays:

 import std.stdio, std.string, std.algorithm, std.array, std.range;

 string[] nextCarpet(string[] c) {
      auto b = array(map!q{a ~ a ~ a}(c));
      return b ~ array(map!q{a ~ a.replace("#"," ") ~ a}(c)) ~ b;
 }

 void main() {
      auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]);
      writeln(array(take(c, 4)).back.join("\n"));
 }


 Few notes:
 - I don't know how to take just the 4th item of a lazy sequence. array(take(c,
4)).back is not good.

 - recurrence() is a bit overkill. A function like iterate() simplifies the
code:
 auto c = iterate!nextCarpet(["#"], 4);

 - I don't see a simple way to create a lazy nextCarpet(), without those
array(). The seed (["#"]) can't be an array, but even wrapping it with a lazy
map!q{a}(["#"]) solves nothing. chain(map(chain...))) are all different types,
so I think it can't work. The types in that Scala code are sound because it
uses a lazy list type, that supports the ::: operator for concatenation, and
List("#") to create the correctly typed seed. That carpet.map() returns a
List[String]. So both the input and output of the Scala nextCarpet() are of the
same type, List[String]. So such lazy list type template becomes really useful
if you want to program in a lazy functional style.

 Bye,
 bearophile

-- /Jacob Carlborg
Feb 23 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jacob Carlborg:

 def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop
n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

In software engineering there aren't many free things. For some of the Scala features you have to pay with a higher amount of memory used by the Java virtual machine, and with the compilation time of the function optimizations (and type system management) done by the Scala compiler. There is a faster Scala compiler, named fsc, but I don't know how fast it is for larger projects. Bye, bearophile
Feb 23 2011
parent Jacob Carlborg <doob me.com> writes:
On 2011-02-23 13:13, bearophile wrote:
 Jacob Carlborg:

 def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop
n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

In software engineering there aren't many free things. For some of the Scala features you have to pay with a higher amount of memory used by the Java virtual machine, and with the compilation time of the function optimizations (and type system management) done by the Scala compiler. There is a faster Scala compiler, named fsc, but I don't know how fast it is for larger projects. Bye, bearophile

Ok, I see now that my answer can be misinterpreted. When I wrote the answer I was actually referring to the lambda syntax used in the "map" function. This is just syntax sugar that D could use as well with no overhead. -- /Jacob Carlborg
Feb 23 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/23/11 5:10 AM, Jacob Carlborg wrote:
 On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
 carpet.map(x => x + x + x) :::
 carpet.map(x => x + x.replace('#', ' ') + x) :::
 carpet.map(x => x + x + x))

 def sierpinskiCarpets(n: Int) =
 (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

But then Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println a sort of a stuttering Yoda evokes. Andrei
Feb 23 2011
parent reply Jacob Carlborg <doob me.com> writes:
On 2011-02-23 13:57, Andrei Alexandrescu wrote:
 On 2/23/11 5:10 AM, Jacob Carlborg wrote:
 On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
 carpet.map(x => x + x + x) :::
 carpet.map(x => x + x.replace('#', ' ') + x) :::
 carpet.map(x => x + x + x))

 def sierpinskiCarpets(n: Int) =
 (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

But then Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println a sort of a stuttering Yoda evokes. Andrei

Ok, I see now that my answer can be misinterpreted. When I wrote the answer I was actually referring to the lambda syntax used in the "map" function. x => x + x + x -- /Jacob Carlborg
Feb 23 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/23/11 9:30 AM, Jacob Carlborg wrote:
 On 2011-02-23 13:57, Andrei Alexandrescu wrote:
 On 2/23/11 5:10 AM, Jacob Carlborg wrote:
 On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
 carpet.map(x => x + x + x) :::
 carpet.map(x => x + x.replace('#', ' ') + x) :::
 carpet.map(x => x + x + x))

 def sierpinskiCarpets(n: Int) =
 (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

But then Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println a sort of a stuttering Yoda evokes. Andrei

Ok, I see now that my answer can be misinterpreted. When I wrote the answer I was actually referring to the lambda syntax used in the "map" function. x => x + x + x

I understand that. What I meant to say is that it's difficult to have a language that excels on all fronts. Andrei
Feb 23 2011
parent Jacob Carlborg <doob me.com> writes:
On 2011-02-23 16:36, Andrei Alexandrescu wrote:
 On 2/23/11 9:30 AM, Jacob Carlborg wrote:
 On 2011-02-23 13:57, Andrei Alexandrescu wrote:
 On 2/23/11 5:10 AM, Jacob Carlborg wrote:
 On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
 carpet.map(x => x + x + x) :::
 carpet.map(x => x + x.replace('#', ' ') + x) :::
 carpet.map(x => x + x + x))

 def sierpinskiCarpets(n: Int) =
 (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

But then Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println a sort of a stuttering Yoda evokes. Andrei

Ok, I see now that my answer can be misinterpreted. When I wrote the answer I was actually referring to the lambda syntax used in the "map" function. x => x + x + x

I understand that. What I meant to say is that it's difficult to have a language that excels on all fronts. Andrei

Too D doesn't excel on this front. Specially since you seem to push for std.algorithms where may functions requires lambdas. -- /Jacob Carlborg
Feb 24 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/23/2011 01:57 PM, Andrei Alexandrescu wrote:
 On 2/23/11 5:10 AM, Jacob Carlborg wrote:
 On 2011-02-23 03:28, bearophile wrote:
 This is a Scala implementation of a function that prints the carpet:


 def nextCarpet(carpet: List[String]): List[String] = (
 carpet.map(x => x + x + x) :::
 carpet.map(x => x + x.replace('#', ' ') + x) :::
 carpet.map(x => x + x + x))

 def sierpinskiCarpets(n: Int) =
 (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println

Again Scala shines with its beautiful lambdas compared to Ds ugly string version.

But then Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println a sort of a stuttering Yoda evokes.

lol :-) It just requires being used to stack-based-like lingo; meaning each step is written in chrono-logical order, from left to right. Well, actually, the 'List("#")' part looks like a useless hack, and 'Iterator.iterate' is somewhat verbose. I'd prefere: (sequence(["#"])(nextCarpet) drop n next) foreach println Denis -- _________________ vita es estrany spir.wikidot.com
Feb 23 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/22/11 8:28 PM, bearophile wrote:
 import std.stdio, std.string, std.algorithm, std.array, std.range;

 string[] nextCarpet(string[] c) {
      auto b = array(map!q{a ~ a ~ a}(c));
      return b ~ array(map!q{a ~ a.replace("#"," ") ~ a}(c)) ~ b;
 }

 void main() {
      auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]);
      writeln(array(take(c, 4)).back.join("\n"));
 }


 Few notes:
 - I don't know how to take just the 4th item of a lazy sequence. array(take(c,
4)).back is not good.

popFrontN(c, 3); ... use c.front() ...
 - recurrence() is a bit overkill. A function like iterate() simplifies the
code:
 auto c = iterate!nextCarpet(["#"], 4);

 - I don't see a simple way to create a lazy nextCarpet(), without those
array(). The seed (["#"]) can't be an array, but even wrapping it with a lazy
map!q{a}(["#"]) solves nothing. chain(map(chain...))) are all different types,
so I think it can't work. The types in that Scala code are sound because it
uses a lazy list type, that supports the ::: operator for concatenation, and
List("#") to create the correctly typed seed. That carpet.map() returns a
List[String]. So both the input and output of the Scala nextCarpet() are of the
same type, List[String]. So such lazy list type template becomes really useful
if you want to program in a lazy functional style.

You shouldn't need array most at all. Use chain() instead of ~. Andrei
Feb 23 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:

 popFrontN(c, 3);
 ... use c.front() ...

Right. I have used the c.popFrontN(3); syntax and then I have not read the error message well. A drop(range, n) is an expression, it allows to write it as this: drop(c, 3).front
 You shouldn't need array most at all. Use chain() instead of ~.

I don't understand how, this is a simple try: import std.stdio, std.string, std.algorithm, std.array, std.range; auto nextCarpet(R)(R c) { auto b = map!q{a ~ a ~ a}(c); return chain(b, map!q{a ~ a.replace("#"," ") ~ a}(c), b); } void main() { auto c = recurrence!((a, n){ return nextCarpet(a[n-1]); })(["#"]); popFrontN(c, 3); writeln(c.front().join("\n")); } It gives: ...\dmd\src\phobos\std\range.d(3659): Error: cannot cast from ChainImpl!(Map!(result,string[]),Map!(result,string[]),Map!(result,string[])) to string[] Later I will think more on this. Maybe I am missing something. Thank you for your answers, bye, bearophile
Feb 23 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 02/24/2011 09:55 AM, Russel Winder wrote:
 On Wed, 2011-02-23 at 23:51 +0100, spir wrote:
 [ . . . ]
       (sequence(["#"])(nextCarpet) drop n next) foreach println

Hey guys, it's PostScript, no it's Forth ;-)

Note that method chaining in typical OO syntax writes the process in chronological order as well: o f1 f2 f3 ==> o.f1.f2.f3 or o.f1().f2().f3() Unlike common function call syntax which is written backwards: f3(f2(f1(o))) but we're so used to it... to the point that postfix syntax is also called "reversed" Polish notation, while in fact it expressive the process in 'Forth' order (lol!). Denis -- _________________ vita es estrany spir.wikidot.com
Feb 24 2011