using less stack

[Gertjan Kamsteeg]

From: "Alastair Reid" <reid@cs.utah.edu>
>
> Gertjan Kamsteeg <gkamsteeg@freeler.nl> writes:
> >> You don't have to define cpsfold explicitly recursively since it
> >> can be expressed in terms of foldr:
>
> Hal Daume III <hdaume@ISI.EDU> writes:
> > Is this generally considered good design?  [...]
>
> Three different attempts at an answer:
>
> As with all code-factoring it's in the eye of the beholder.
>
>   If what you want to do is trace execution in detail, the less factored
>   code is easier to understand.
>
>   If what you want to do is understand the difference between 5
>   different recursive traversals of a list, then isolating those
>   differences (by suppressing the invariant fact of recursion) is
>   better.
>

I agree. However, although *functionally* every list traversing function
should be expressible in terms of foldr (because foldr represents the type
theoretical elimination rule for lists in most type systems with inductive
types (and without element depending types)), it's not just a matter of
taste. Execution clearly *does* depend on how things are defined. When I
said 'can be expressed', I meant extensionally equivalent, including
behavior w.r.t. reductions. For example, if, in the Prelude, foldr had been
defined in terms of foldl:

foldr f a xs = foldl (\h x y -> h (f x y)) id xs a

my definition of cpsfold in terms of foldr wouldn't go through. That is,
some stack would again overflow. What I wanted to say is that the fact that
Amanda's answer1 (maximum in terms of foldr) didn't work wasn't caused by
the definition of foldr in the Prelude.

Besides, (re)factoring is fun. So, here's another one (foldl in terms of
foldr):

foldl f a xs = foldr (\x h y -> h (f y x)) id xs a

BTW, there may be another reason for expressing list traversing functions in
terms of foldr: if one uses only functions representing 'standard'
elimination rules, it is guaranteed that all reduction sequences eventually
terminate.

Gertjan