Last modified: 2016-10-08
This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

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))))))
      
Home page Semesters Site Map
go back Fall 2006 go forward
2017-11 other links

Semester Map
CPSC 141
CPSC 200
CPSC 370
Course Outline
Handing in Homework
Pending Homework Questions
Solutions
Policies
References
David’s Schedule