🚀 go-pugleaf

     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