Fsharpplus: Traversing infinite sequences

[gusty]

_From @mausch on April 16, 2014 21:23_

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

_Copied from original issue: gmpl/FsControl#26_

[gusty]

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.

[gusty]

_From @mausch on April 17, 2014 22:49_

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]

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]

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]

@mausch I'm evaluating to generalize the 'poor man' solution (and make it a rich man solution).

The idea is that all instances for (infinite) sequences have many things in common and only one difference.

They can use a generic algorithm that first enumerates the sequence and store it in a buffer (an array) but at the same time it checks for a 'failure value', and if that value is present it will stop processing and use that value instead.

The only difference between all instances is precisely that 'failure value'. For options it will be None, for Choices it will be Choice2Of2, for lists it will be [] and so on.

So we can implement something like an IsFailure typeclass, which will be an invokable IsFailure which accepts a value and determines if it represents a failure, or more technically, if it's a monadic (or applicative) short-circuit value.

Besides from helping on eager evaluation of infinite structures, this Invokable might have other uses.

It might be useful for generalizing over error-like monads, very interesting now that F# 4.1 introduces another type to handle errors in a pure way.

[gusty]

Here you can get an idea of how the unified function would look like

[gusty]

268 solves this issue in a generic way

It requires to have available a predicate (as part of the applicative abstractions) which tells whether an element is the cancelling element for the operation, called left-zero.