Lennart Augustsson wrote:
>
> Kevin Atkinson wrote:
>
> > Lennart Augustsson wrote:
> >
> > > No, it will not be as efficient. foldr is not the right primitive for making
> > > functions on lists. You want the more general
> > > recurse :: (a -> c a -> b -> b) -> b -> c a -> b
> >
> > Could you give me some refrence on how that function is used as this is
> > the first time I herd of it.
>
> Well, I just made up the name since it's not a standard function (it should be :-).
> It is useful for functions doing primitive recursion.
>
> > What exactly does it do? What would its defination for a list be.
> > How would you define a foldl, foldr, foldl1, foldr1, zip, etc.. with it.
>
> I think the type should (almost) explain what it does :), let me exemplfy for lists
> recurse c n [] = n
> recurse c n (x:xs) = c x xs (recurse c n xs)
>
> So it's like foldr, except that the cons function gets the tail of the list,
> not just the head. With it you can define an efficient tail function.
This function, recurse, appears to be very similar to something what
appears in Andy Gill's Thesis[1, pg52]. He calls it 'augment' The
Super Constructor
augment :: \/a.(\/r.(a -> r -> r) -> r -> r) -> [a] -> [a]
augment g h = g (:) h
The underlying idea is OK, but it seems hard to generalise to other
data types (e.g. trees).
Does this make sense?
Laszlo
[1] A.Gill: Cheap Deforestation for Non-Strict Functional Languages
PhD Thesis, University of Glasgow 1996.
(available from his home page or as Tech Report TR-1996-5)
