Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
Higher-order functions in 'Functional Programming Languages'


Here is the Scheme version of the prod, fac, and power functions from the paper - directly translated.

(define (prod m n f) (if (= n m) (f m) (* (f m) (prod m n f)))) (define (fact n) (let ((f (lambda (i) i))) (prod 1 n f))) (define (power x n) (let ((f (lambda (i) x))) (prod 1 n f)))

The problem is that prod recurses forever. It is an easy fix, however:

(define (prod m n f) (if (= n m) (f m) (* (f m) (prod (+ m 1) n f)))) ; First parameter of prod: (+ m 1) instead of just m. (define (fact n) (let ((f (lambda (i) i))) (prod 1 n f))) (define (power x n) (let ((f (lambda (i) x))) (prod 1 n f)))

Here is an iterative, memory efficient, tail-recursive version of prod:

(define (prod m n f) (prod-iter m n f 1)) (define (prod-iter m n f r) (if (> m n) r (prod-iter (+ m 1) n f (* r (f m)))))