
18 Feb
2013
18 Feb
'13
4:28 p.m.
* Petr Pudlák
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. Roman