Thanks Roman and Andres for the tip. I knew the trick with accumulating a function, but I had never imagined it could work so efficiently. I thought the problem with using foldr would be that the function would be neither tail recursive nor efficient and so I hadn't even tried. Apparently that was wrong. After your suggestion I checked its performance and how it compiles to core and to my surprise GHC optimizes the whole thing into a most-efficient tail recursive function! Best regards, Petr 2013/2/18 Roman Cheplyaka <roma@ro-che.info>
* Petr Pudlįk <petr.mvd@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.
Roman