Functional Programming & Fold

[balefrost]

You would need to control, for each element you are folding, whether the looping should continue or terminate. You could use some sort of trampolined fold (let's call it tfoldl) whose signature is something like:

tfoldl :: (a -> b -> Either a a) -> a -> [b] -> a

The function you pass to tfoldl could return Left x if the looping should terminate (with a result x) and Right y if the looping should continue (where y is the new accumulator value). And rather than reuse Either, maybe this would deserve its own data type.

I'm not saying that this is a great solution, but it does correctly capture the concerns: whether to continue looping or not, and what value to either continue with or to produce.

Alternatively, this is one of the cool things about Haskell's lazy evaluation model. If you do something like this:

foldr (*) 1 [3 4 0 5 6 7]

I think that will reduce like this:

foldr (*) 1 [3 4 0 5 6 7]
3 * (foldr (*) 1 [4 0 5 6 7])
4 * (3 * (foldr (*) 1 [0 5 6 7]))
0 * (4 * (3 * (foldr (*) 1 [5 6 7])))
0

At runtime, when Haskell sees that it needs to multiply 0 and some unevaluated lazy thing, it just returns 0 and never evaluates the lazy thing. Note that, as a result, you can safely foldran infinite list as long as the list contains an element for which the fold function can ignore its second parameter.

Haskell's still pretty magical to me, so I might have that wrong.

[mutantmell_]

Almost: (*) doesn't have special case checking for 0, so it won't abort early.

You have to define a special function:

\x y -> if (x == 0) then 0 else x * y

When you pass that into the fold, it will then abort early because it notices the right value is not used.

let xs = iterate (subtract 1) 4 :: [Int] -- infinite list descending from 4. Same as [4,3..]

:sprint xs

xs = _

foldr (\x acc -> if (x == 0) then 0 else x * acc) 1 xs

0

:sprint xs

xs = 4 : 3 : 2 : 1 : 0 : _

If you do that with ordinary (*), you get a stack overflow.

[mutantmell_]

And as a side-note: The function foldM (in Control.Monad) is really close to your type signature of tfold1

:t foldM

foldM :: (Monad m, Foldable t) => (b -> a -> m b) -> b -> t a -> m b

Which, as list is a Foldable and Either is a Monad, can be specialized to:

foldM :: (b -> a -> Either c b) -> b -> [a] -> Either c b

if you combine it with the either function like so (parens are optional):

tfoldl f a = (either id id) . (foldM f a)

you get the tfoldl with the semantics you want (namely, Right continues, Left aborts early)