Exercise1-42 <---> Exercise1-44

Exercise 1.43

If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(...(f(x))...)). For example, if f is the function x ↦ x + 1, then the nth repeated application of f is the function x ↦ x + n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2ⁿth power. Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f. Your procedure should be able to be used as follows:

((repeated square 2) 5)
625

Hint: You may find it convenient to use compose from exercise 1.42.

Scheme solution:

; Recursive solution
(define (repeated f n)
  (cond ((< n 1) (lambda (x) x))
        (else (compose f (repeated f (- n 1))))))

; Iterative solution
(define (repeated f n)
        (define (rep-iter g count)
                (if (= count 1) g (rep-iter (compose f g) (- count 1))))
        (rep-iter f n))

((repeated square 2) 5)

Haskell solution:

repeated f 0 = id
repeated f n = f . repeated f (n-1)

Or:

repeated f n = foldr (.) id (replicate n f)

OCaml solution:

let rec repeated f = function
   0 -> fun x -> x
 | n -> compose f (repeated f (n-1))

Standard ML solution:

fun repeated (f, 0) = (fn x => x)
  | repeated (f, n) = f o repeated (f, n-1)

Alternative Scheme solution in logarithmic time and space using double:

(define (repeated f n)
  (cond ((= n 0) (lambda (x) x))
        ((even? n) (double (repeated f (/ n 2))))
        (else (compose f (repeated f (- n 1))))))

Exercise1-42 <---> Exercise1-44

Comments

Wouldn't this be a better way to get logarithmic time? This would be an iterative procedure because the (double f) is passed to the next call of 'repeated' instead of having to wait for repeated to get to 1. (define (repeated f n) (cond ((< n 1) (lambda (x) x)) ((= n 1) f) ((even? n) (repeated (double f) (/ n 2))) (else (compose f (repeated f (- n 1))))))

Posted by 134 at 2008-05-19 02:41:39 X

I don't think it's possible to get repeated to take theta(log n) time. No matter what method is used to generate the repeated function, it will contain n nested calls to f by definition. That will take theta(n) space and therefore theta(n) time to construct. It will also take theta(n) time to call the repeated method each time.

Posted by SteveChapel at 2008-05-28 02:22:40

Add your comment Markup