18 Feb 17:10 2013

## generalized, tail-recursive left fold that can finish tne computation prematurely

Petr Pudlák <petr.mvd <at> gmail.com>

2013-02-18 16:10:24 GMT

2013-02-18 16:10:24 GMT

Dear Haskellers,

while playing with folds and trying to implement `!!` by folding, I came to the conclusion that:

- `foldr` is unsuitable because it counts the elements from the end, while `!!` needs counting from the start (and it's not tail recursive).

- `foldl` is also unsuitable, because it always traverses the whole list.

I came up with the following tail-recursive generalization of `foldl` that allows exiting the computation prematurely:

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

foldlE f g = fld

where

fld (Left c) _ = c

fld (Right a) [] = f a

fld (Right a) (x:xs) = fld (g a x) xs

`foldl` can be defined from it as

foldl'' :: (a -> b -> a) -> a -> [b] -> a

foldl'' f z = foldlE id ((Right .) . f) (Right z)

and `!!` as:

-- Checks for a negative index omitted for brevity.

index :: Int -> [a] -> a

index i = foldlE (error $ "No such index") f (Right i)

where

f 0 x = Left x

f n _ = Right (n - 1)

Is something like that already available somewhere?

Best regards,

Petr Pudlak

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe