[Haskell-cafe] generalized, tail-recursive left fold that can finish tne computation prematurely

[Roman Cheplyaka]

* Roman Cheplyaka <roma at ro-che.info> [2013-02-18 18:28:47+0200]
> * Petr Pudlák <petr.mvd at gmail.com> [2013-02-18 17:10:26+0100]
> > 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.
> 
> Every structurally-recursive function is definable through foldr,
> because foldr *is* the structural recursion (aka catamorphism) operation
> for lists.
> 
> Here the trick is to make the accumulator a function. This way you can
> pass a value from left to right.
> 
> Something like
> 
>   foldr (\x rest n -> ...) id list 0
> 
> I'll leave filling in the dots as an exercise.

Er, my template is not quite right — I had 'length' in mind while writing
it. Anyway, Andres showed the correct definition.

Roman