srlm@ukc.UUCP (S.R.L.Meira) (08/16/83)
This article is about recursion (and factorial!) again, in relation
to Joe Fasel's. The examples are in KRC --The Kent Recursive
Calculator-- parts of which have been shown in a previous article
(RECURSION IS EASIER...).
The "usual" definition of factorial
fac1 0 = 1
fac1 n = n * fac1 (n-1)
is not only the simplest way to demonstrate recursion, but it is prob-
ably the most efficient way for the calculation of factorial (in a
purely applicative language). The second method shown in Joe's article
uses the "lazy list" concept, i.e., using the notation
lis n = [1..n]
one defines the list
[1,2,3...n]
which is built by need. The in(de)crement is not necessarily 1, such
that
odd = [1,3..]
is the infinite list of odd integers. And so on. But when we define
factorial as
fac2 n = product [1..n]
its evaluation uses much more space than fac1's above. In the
ICL2960/EMAS (tree-rewriting-system) implementation of KRC (by D.
Turner) fac2 uses 60% more space than fac1 and in the experimental Unix
(combinators) implementation (by S. Croft) it uses 200% more space, the
number of reductions needed for both evaluations being basically
unchanged.
I agree with Joe (and David Turner) that the use of product, a KRC
library function defined by
product = fold '*' 1
fold op s [] = s
fold op s (a:x) = op a (fold op s x)
eliminates the "junk recursion" in fac1, but it has its price.
By the way, the use of tail recursion
fac3 n = fac3t n 1
fac3t 0 r = r
fac3t n r = fac3t (n-1) (n*r)
is also less efficient in the two implementations of KRC here at UKC.
fac3 evaluates with the same number of reductions of fac1, but it uses
20% more space in the tree-rew-sys and 50% more in the combinatoric
machine. So...
Now I'll say a little about eliminating recursion by using ZF-
expressions (see my previous article). A silly example of its use is to
redefine the length function
length [] = 0
length (a:x) = 1 + length x
whose ZF version is
lenZF x = sum {1 | a <- x}
where {1 | a <- x} is a list containing as many 1's as the number of
elements in x, and sum is
sum = fold '+' 0
A favourite example is the infinite list of primes
primes = sieve [2..]
sieve (a:x) = a : sieve {b | b <- x; b % a = 0}
where % is "remainder" and \= is "not equal".
From now on, we can redefine
map f [] = []
map f (a:x) = f a : map f x
as
map f x = {f a | a <-x}
and
filter cond [] = []
filter cond (a:x) = a : filter cond x, cond x
= filter cond x
as
filter cond x = {a | a <- x; cond a}
and so on.
The only alert here is that both "product" and ZF-expressions are
(internally) recursively defined.
Silvio Lemos Meira
...!decvax!mcvax!ukc!srlm