Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lazy scanl is not actually lazy. #372

Closed
kindaro opened this issue Mar 1, 2021 · 2 comments · Fixed by #364
Closed

Lazy scanl is not actually lazy. #372

kindaro opened this issue Mar 1, 2021 · 2 comments · Fixed by #364
Milestone

Comments

@kindaro
Copy link
Contributor

kindaro commented Mar 1, 2021

See the source code:

scanl f z = snd . foldl k (z,singleton z)

— Since it is written in terms of foldl, it cannot be any less strict, and foldl forces all the spine. There is a way to write scanl in terms of foldr though! See here for example.

I checked the strictness property and I found that the current definition forces all the spine and that an alternative definition may be given in terms of foldr that is strictly lazier.

This is the code I am using to check strictness:

explosiveTail = (`L.append` error "Tail of this byte string is undefined!")

property = \ xs ->
        L.take (L.length xs + 1) (L.scanl (+) 0 (explosiveTail (xs `L.append` L.singleton 1))) == (L.take (L.length xs + 1) . L.pack . fmap (L.foldr (+) 0) . L.inits) xs

Am I missing something or should this be fixed? If it should be fixed, I can do it on the cheap as part of #364 since I am already writing a bunch of strictness checks for all other lazy scans there.

@kindaro kindaro mentioned this issue Mar 1, 2021
6 tasks
@kindaro
Copy link
Contributor Author

kindaro commented Mar 1, 2021

I provisionally fixed it in #364.

@Bodigrim
Copy link
Contributor

Bodigrim commented Mar 1, 2021

Ah, interesting catch!

@Bodigrim Bodigrim added this to the 0.11.2.0 milestone Aug 19, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants