using less stack
24 Mar 2002 02:58:49 +0000
Gertjan Kamsteeg <firstname.lastname@example.org> 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
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