Bug of Data.List.Lazy iterate

[ibara1454]

My English isn't good so feel free to ask me if there is anything unclear.

Problem

The correct behavior of iterate, it should evaluate the function only n times while generating a n+1 length list. But in this implementation, iterate re-evaluate values too many times.

To show this, I constructed a list by iterate, and the value in list will be printed to console when it is evaluated.

Actually

Desire

> lazyl = iterate (\x -> spy $ x + 1) 0
> take 3 lazyl
1
2
fromStrict ((Cons 0 (Cons 1 (Cons 2 Nil))))

> take 4 lazyl
1
2
3
fromStrict ((Cons 0 (Cons 1 (Cons 2 (Cons 3 Nil)))))

[ibara1454]

Made a PR #141 for this issue.

However, maybe there still have some bugs in fix or (<$>). Because the (old) code

iterate f x = Z.fix \xs -> cons x (f <$> xs)

should not have the behavior that evaluate the same value too many times.

[natefaubion]

@ibara1454 My hunch would be that the Lazy instance does not actually share work in the fix case. One way to confirm is to rewrite this using lazy list internals directly rather than using the Lazy class.

[ibara1454]

@natefaubion OK. To confirm it, I rewrote fix without Lazy class.

import Prelude
import Data.List.Lazy (List(..), iterate, cons, step)
import Control.Lazy (fix)
import Data.Lazy (defer)
import Debug.Trace (spy)

defer' :: forall a. (Unit -> List a) -> List a
defer' f = List $ defer (step <<< f)

fix' :: forall a. (List a -> List a) -> List a
fix' f = defer' (\_ -> f (fix' f))

iterate' :: forall a. (a -> a) -> a -> List a
iterate' f x = fix' \xs -> cons x (f <$> xs)

ls = iterate (\x -> spy $ x + 1) 0
ls' = iterate' (\x -> spy $ x + 1) 0

But they have the same result ...

It seems that the bug is made by (<$>), or by defer, or by fix itself.

[natefaubion]

@ibara1454 You've just inlined the exact definition used for the Lazy instances. If you expand the definition of fix, you'll see that that recursion with fix f creates a fresh thunk every time, which prevents it from being shared. If instead, you define it as:

fix' :: forall a. (List a -> List a) -> List a
fix' f = go where go = List $ defer \_ -> step $ f go

iterate' :: forall a. (a -> a) -> a -> List a
iterate' f x = fix' \xs -> cons x (f <$> xs)

ls' :: List Int
ls' = iterate' (\x -> spy $ x + 1) 0

1
2
3
4
fromStrict ((Cons 0 (Cons 1 (Cons 2 (Cons 3 Nil)))))

[natefaubion]

This fixes other issues like with take evaluating too much, as well. So I think the underlying cause of these bugs is just a bad definition of fix in purescript-control.

[natefaubion]

Oh I take that back about take, as it's clearly unrelated to fix 😝

[ibara1454]

@natefaubion Ohh I see!!! Your solution is perfect! It exactly solved the problem that iterate evaluating too much. 😃

[JordanMartinez]

I think this was fixed by purescript/purescript-control#48?