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

* Roman Cheplyaka [2013-02-18 18:28:47+0200]

* Petr Pudlák [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