Lazy lists

[Andrei Alexandrescu]

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