i have a scheme question

i have created a function called "repeat" that composes a function with itself n times. i have written it in two different ways. one works and the other doesn't. can you help me understand why the one doesn't work? tia.

the code:
https://gist.github.com/3134464

Line 3.

>>2
the function call inside the lambda? how could i change it to make it work?

>>3
No, I mean you have a typo.

>>1

This is an ugly tail recursive version,


(define (repeat f n)
  (letrec ((loop (lambda (n accumulation)
                   (if (= n 0)
                     accumulation
                     (loop (- n 1) (compose f accumulation))))))
    (loop (- n 1) f)))

Repeated squaring:


(define (repeat f n)
  (cond ((= n 1) f)
        ((even? n) (repeat (compose f f) (/ n 2)))
        (else (compose f (repeat f (- n 1))))))

>>4
what is the typo? i don't see it.

>>5
thank you. is there any way to make it work using only a lambda to compose instead of a separate procedure called compose?

>>7

yeah, just replace (compose ___F___ ___G___) with


(let ((f ___F___)
      (g ___G___))
  (lambda (x)
    (f (g x)))

wherever compose is called.

>>8

although that brings up an interesting difference between using


(lambda (x)
  (___F___ (___G___ x)))

>>8

thank you. that's very helpful.

using that i can rewrite my nonworking repeat function as:

(define (repeat f n)
        (if (> n 1)
              (let ((g (repeat f (- n 1))))
                 (lambda (x)
                               (f (g x))))
          f))

can you explain why it is seemingly necessary to define g outside of the lambda? as in, why can't i remove the let and replace (g x) inside the lambda with (repeat f (- n 1) ?

>>9

yes. this is what i am curious about.

>>10

both are correct, but the times at which the closures are evaluated will be different. Say you (define fn (repeat f n)). If repeat was defined as:


(define (repeat f n)
        (if (> n 1)
              (let ((g (repeat f (- n 1))))
                 (lambda (x)
                   (f (g x))))
          f))

then all the composition closures are constructed and linked together when you called (repeat f n). When (fn x) is called, the constant linked data structure of closures is then traversed and applied to x and each other's return values.

If repeat was instead defined as:


(define (repeat f n)
        (if (> n 1)
            (lambda (x)
              (f ((repeat f (- n 1)) x))))
          f))

Then the call to (repeat f n) would return immediately in O(1) time. But then every time (fn x) was evaluated, then chain of composed closures would be recreated, over and over again.

But the two forms are ultimately equivalent. They just might differ in efficiency.

>>1
Your first example would work if you wrote it like that:

(define (repeat f n)
  (if (< n 2)
      (lambda (x) (f x))
      (lambda (x) (f ((repeat f (- n 1)) x)))))

((repeat square 2) 3)

>>10
it's not.

change from this
(define (repeat f n)
        (if (> n1)
            (lambda (x) (f (repeat f (- n 1))))
            f))
to this:
(define ...
        (if ...
            (lambda (x) (f ((repeat f (- n 1)) x)))
            ...))

the difference is in when the recursive call is evaluated. putting the repeat in the lambda causes it to be evaluated every time the function is called. you're working with higher order functions so its fairly strange you would want to embed a recursive call to the lambda creating a lambda into the lambda that's being created.

also you should define the base case as values or identity.

a simple definition:
(define (repeat n proc)
  (foldl compose values (make-list n proc)))

>>14

that is a crystal clear explanation. i completely understand what is happening now. thank you again.

gist
back to facebook, ``please"!

>>16

what's wrong with gist?

you guys should troll this guy
417-209-1160

>>17
just leave

>>19

https://gist.github.com/3147673