>
> Dear Jose,
>
> > I am trying to define common functions with recursive combinators
> > avoiding recursive definitions. I have found some problems with
> > the "insert" function that inserts an element x in an ordered list xs
> > This function is used when you define insertion sort as "foldr insert
[]"
> >
> > -- First attempt
> > insert::(Ord a)=>a->[a]->[a]
> > insert x = ...
>
> BTW I like to think of `foldr' as a special case of _structural
> recursion on lists_.
>
> > structuralRecursionOnLists
> > :: solution -- base
> > -> (a -> [a] -> solution -> solution) -- extend
> > -> [a] -> solution
> > structuralRecursionOnLists base extend
> > = rec
> > where rec [] = base
> > rec (a : x) = extend a x (rec x)
> >
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)
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'.
In another message, Bjarte uses a generalised unfold that solves also the
'insert' problem. His function could be another 'fundamental' combinator.
Regards, Jose Labra
