search

gusty / FsControl

[ARCHIVED] FsControl in now included in FSharpPlus https://fsprojects.github.io/FSharpPlus
Apache License 2.0
105 stars 16 forks source link

Traversing infinite sequences #26

Closed mausch closed 7 years ago

mausch commented 10 years ago

Traversing an infinite list works fine in Haskell: http://ideone.com/GuytMd But the equivalent F# + FSharpPlus code doesn't terminate and eats infinite memory:

let x = traverse (fun x -> if x > 4 then Some x else None) (Seq.initInfinite id)

This is probably because foldr is currently strict for seq

Maybe a specialized foldr would work here, e.g. http://fpish.net/blog/anton.tayanovskyy/id/1453/http~3a~2f~2fwww.intellifactory.com~2fblogs~2fanton.tayanovskyy~2f2009~2f12~2f11~2fFoldr-or-FoldBack-on-Infinite-F~21sharp~21-Sequences.article

(BTW this stackoverflow question made me realize this).

gusty commented 10 years ago

I'm not sure if is possible to define a foldr working over infinite sequences. I would rather try to write a more efficient traverse for seq using low level enumerators instead of foldr. Still I'm not sure if it would be possible to make it work with infinite sequences, but I would give it a try.

mausch commented 10 years ago

Yes, such a foldr is not possible with the usual signature, so yes, the 'optimization' needs to happen in the implementation of traverse. I'm currently trying to implement such a traverse for a LazyList, then the implementation for seq would just internally use the one for LazyList. Doing this using low-level enumerators as you say should also be possible, it just seems more complicated.

gusty commented 10 years ago

Hopefully I'm wrong but I'm afraid that even implementing a traverse for LazyList will not be lazy enough. A poor man solution is to add specific instances, I did one that is able to run your sample code. https://github.com/gmpl/FsControl/commit/0496a739c20b8fdf57cbb9a91e382b13dac07459

gusty commented 7 years ago

The poor man solution seems to be the way to approach this problem. Each time an optimized or a lazy version is needed a specific instance should be added. I would say there will be more cases like this, in which the lazyness is not the default since it will not be automatically derived, see for instance the new Delay method for workflows.

gusty commented 7 years ago

This issue was moved to gmpl/FSharpPlus#41