Traversing infinite sequences about fsharpplus HOT 7 CLOSED

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

from fsharpplus.

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

from fsharpplus.

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.

from fsharpplus.

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.

from fsharpplus.

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. gusty/FsControl@0496a73

from fsharpplus.

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.

from fsharpplus.

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

from fsharpplus.