* Roman Cheplyaka <r...@ro-che.info> [2013-02-18 18:28:47+0200] > * Petr Pudlák <petr....@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
