using less stack

Alastair Reid
24 Mar 2002 02:58:49 +0000

Gertjan Kamsteeg <> 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

More concretely, some prefer to avoid the recursive formulations because:

1) It is trickier to reason about.

   Functional programmers (especially Squiggol afficianados) have all
   kinds of cunning ways to reason about programs written using
   standard library functions such as foldr.  The techniques for
   reasoning directly about recursive functions are somewhat cruder
   and harder.

2) The ability to recursivly invoke the function from _anywhere_ in
   the function body has been compared (with some justification) to
   the use of goto in unstructured programming.  If you buy into this
   line of reasoning then foldr, scanr, map, etc. are to functional
   programming as while, repeat and for are to structured programming.

[These two points are connected!]

And, finally, my personal preference is:

- use explicit recursion when I don't understand what I'm doing well
  enough to know which standard recursive pattern it fits into
  (because it normally always fits a standard pattern).

- use higher-order functions when I know what I'm doing or where
  setting up the infrastructure for the recursion costs more than
  coding it directly.

Alastair Reid        Reid Consulting (UK) Ltd