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 + x))
 

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));

}
 
void main() {

    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:


- I don't see a simple way to create a lazy nextCarpet(), without those


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[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 + x))


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));

 }

 void main() {

      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:


 - I don't see a simple way to create a lazy nextCarpet(), without those


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[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 + x))


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));

 }

 void main() {

      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:


 - I don't see a simple way to create a lazy nextCarpet(), without those


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[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:



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:



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 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 + x))

 def sierpinskiCarpets(n: Int) =



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


But then



a sort of a stuttering Yoda evokes.


Andrei
Feb 23 2011
next sibling 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 + x))

 def sierpinskiCarpets(n: Int) =



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


 But then



 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 + x))

 def sierpinskiCarpets(n: Int) =



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


 But then



 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 + x))

 def sierpinskiCarpets(n: Int) =



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


 But then



 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 next 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 + x))

 def sierpinskiCarpets(n: Int) =



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


 But then



 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 

verbose. I'd prefere:


Denis
-- 
_________________
vita es estrany
spir.wikidot.com
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:
 [ . . . ]




 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
prev 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));

 }

 void main() {

      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:


 - I don't see a simple way to create a lazy nextCarpet(), without those


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[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);

}

void main() {

     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