> Yes, you are right, but that is the same function that I wrote in my
> original message as 'newfoldr':
>
> newFoldr::(a->[a]->b->b)->b->[a]->b
> newFoldr f c [] = c
> newFoldr f c (x:xs) = f x xs (newFoldr f c xs)
Well, I merely wanted to throw in the technical term.
> I asked if that function (structural recursion over lists) was a
> 'fundamental' combinator. I know that there is not a clear definition of
> fundamental combinator. IMHO, there should be a set of recursive
> combinators in the standard prelude or in Haskell libraries that allowed
> programmers to avoid recursive definitions in their programs. Each of those
> combinators could be considered 'fundamental'.
[Just for fun: try to define `merge' with `newFoldr' (it's possible,
but it will take some time to figure out the definition). Do you find
the result readable, or would you prefer the recursive definition?]
If you ask for fundamental combinators, here is one I find quite
useful.
> foldm :: (a -> a -> a) -> a -> [a] -> a
> foldm (*) e [] = e
> foldm (*) e x = fst (rec (length x) x)
> where rec 1 (a:x) = (a, x)
> rec n x = (a * b, z)
> where m = n `div` 2
> (a, y) = rec (n - m) x
> (b, z) = rec m y
>
> mergeSort = foldm merge [] . map (\a -> [a])
Regards, Ralf
