Proposal: Add strict iterate'

newer
Proposal: Add Data.Semigroup to...

David Feuer

29 Jul 2014 29 Jul '14

8:48 p.m.

I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose: iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

Attachments:

attachment.html (text/html — 526 bytes)

Show replies by date

Jake McArthur

30 Jul 30 Jul

8:39 a.m.

+1 for adding a strict version of iterate. I have to roll my own all the time. Regarding this particular implementation, I am neither for nor against, because I haven't thought it through yet. On Jul 29, 2014 8:48 PM, "David Feuer" wrote:

...

I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose:

iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward Kmett

10:56 a.m.

Likewise +1 for the idea, but no particular preference for implementation. On Wed, Jul 30, 2014 at 8:39 AM, Jake McArthur wrote:

...

+1 for adding a strict version of iterate. I have to roll my own all the time. Regarding this particular implementation, I am neither for nor against, because I haven't thought it through yet. On Jul 29, 2014 8:48 PM, "David Feuer" wrote:

...
I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose:

iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Bas van Dijk

6 Aug 6 Aug

1:46 p.m.

Hi David, As suggested[1] by Takano Akio a few years ago iterate can be made strict by applying headStrict to its result: headStrict :: [a] -> [a] headStrict = foldr (\x y -> seq x (x : y)) [] We might want to add this to Data.List unless there are no use-cases for a lazy accumulator in iterate in which case I'm +1 for a strict implementation. Bas [1] http://www.haskell.org/pipermail/libraries/2012-November/018775.html On 30 Jul 2014 02:48, "David Feuer" wrote:

...

I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose:

iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Iavor Diatchki

3:59 p.m.

Hello, I like the idea of using `headStrict` instead of adding another version of `iterate`. -Iavor On Wed, Aug 6, 2014 at 10:46 AM, Bas van Dijk wrote:

...

Hi David,

As suggested[1] by Takano Akio a few years ago iterate can be made strict by applying headStrict to its result:

headStrict :: [a] -> [a] headStrict = foldr (\x y -> seq x (x : y)) []

We might want to add this to Data.List unless there are no use-cases for a lazy accumulator in iterate in which case I'm +1 for a strict implementation.

Bas

[1] http://www.haskell.org/pipermail/libraries/2012-November/018775.html On 30 Jul 2014 02:48, "David Feuer" wrote:

...
I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose:

iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

David Feuer

7 p.m.

On Wed, Aug 6, 2014 at 1:46 PM, Bas van Dijk wrote:

...

As suggested[1] by Takano Akio a few years ago iterate can be made strict by applying headStrict to its result:

headStrict :: [a] -> [a] headStrict = foldr (\x y -> seq x (x : y)) []

The version of iterate' that I gave fuses with foldr, once unfoldr is fixed properly. The version above doesn't, with that definition of headStrict, but we can write headStrict :: [a] -> [a] headStrict xs = build $ \c n -> foldr (\x y -> seq x (x `c` y)) n xs This does indeed work well in this case, and it looks like it's probably safe to fuse in general. That seems like a reasonable approach.

...

We might want to add this to Data.List unless there are no use-cases for a lazy accumulator in iterate in which case I'm +1 for a strict implementation.

It's a bit hard for me to imagine why you'd need really need a lazy iterate. I believe that essentially all it does is make things like [1,2,3,undefined,undefined,...] instead of ones like 1:2:3:undefined. Since it always produces an infinite list, there's nothing much you can *do* with that spine.

David Feuer

7:13 p.m.

That 2012 post by Takano Akio mentioned using headStrict to implement scanl' as well, and a few other functions, which sounds like a fantastic idea, as long as it turns out to actually be safe.

Henning Thielemann

10 Aug 10 Aug

2:14 p.m.

Am 06.08.2014 um 19:46 schrieb Bas van Dijk:

...

As suggested[1] by Takano Akio a few years ago iterate can be made strict by applying headStrict to its result:

headStrict :: [a] -> [a] headStrict = foldr (\x y -> seq x (x : y)) []

Can this be achieved with some of the evaluation strategies from Control.Parallel.Strategies, too?

David Feuer

2:42 p.m.

I thought so for a moment, but someone else (I don't remember who) showed me why I was wrong. This headStrict function doesn't force everything in the list. Rather, it ensures that the car of each cons is forced *when that cons is forced*. That is, if we had data SList a = SNil | SCons !a (SList a) this function could be seen as converting [a] to SList a and back, lazily. On Sun, Aug 10, 2014 at 2:14 PM, Henning Thielemann wrote:

...

Am 06.08.2014 um 19:46 schrieb Bas van Dijk:

...
As suggested[1] by Takano Akio a few years ago iterate can be made strict by applying headStrict to its result:

headStrict :: [a] -> [a] headStrict = foldr (\x y -> seq x (x : y)) []

Can this be achieved with some of the evaluation strategies from Control.Parallel.Strategies, too?

3936

Age (days ago)

3947

Last active (days ago)

List overview

Download

8 comments

6 participants

participants (6)

Bas van Dijk
David Feuer
Edward Kmett
Henning Thielemann
Iavor Diatchki
Jake McArthur

Proposal: Add strict iterate'

tags

participants (6)