CPSC 370: Functional and Logic Programming

Homework Solutions:

From time to time I shall post solutions to homework problems here.

Previous homework solutions.

1. A tail-recursive solution is

   fun power (x,n) = let
       fun pow3 (_,0,a) = a
         | pow3 (x,1,a) = x*a
         | pow3 (x,n,a) = let
               val d = (case n mod 2 of 0 => a | 1 => x*a)
           in pow3(x, n div 2,d)
           end
   in pow3(x,n,1.0) end
   

   This uses case which we haven't formally looked at, but the meaning should be apparent. We could equivalently write

   fun power (x,n) = let
       fun pow3 (_,0,a) = a
         | pow3 (x,1,a) = x*a
         | pow3 (x,n,a) = let
               val d = (if n mod 2 = 0 then a else x*a)
           in pow3(x, n div 2,d)
           end
   in pow3(x,n,1.0) end
   

2. Here is a tail-recursive solution that uses letrec to define a local function with an accumulator.

   (define (reverse a-list)
     (letrec
         ((reverse2 
           (lambda (b-list answer)
             (cond
              ((null? b-list) answer)
              ((cons? b-list) 
               (reverse2 (cdr b-list) 
                         (cons (car b-list) answer)))))
           ))
       (reverse2 a-list '())))
     

   Slightly more strait-forward is

   (define (reverse a-list)
     (reverse2 a-list '()))
   
   (define (reverse2 b-list answer)
     (cond
      ((null? b-list) answer)
      ((cons? b-list) 
       (reverse2 (cdr b-list) 
                 (cons (car b-list) answer))))
     ))
     

3. Here is an uncurried version.

   (define (foldr f  b a-list)
     (cond
      ((null? a-list) b)
      (else (f (car a-list)
               (foldr f b (cdr a-list))))))