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

[Petr Pudlák]

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 at ro-che.info>

> * 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.
>
> Roman
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130218/fce956c6/attachment.htm>