An Illustrated Guide to "repeat"

(define (repeat fn n)
  (if (= n 0) (lambda (x) x)
     (compose fn (repeat fn (- n 1)))))

(define (compose f g)
   (lambda (x) (f (g x))))


How on earth does this work? What happens if we call (repeat square
3) ?



First, let's use this picture to represent functions like "square" or
"first":







Now, let's see what "(compose square first)" looks like:




WAIT! But why is "square" on the bottom?


(compose square first) is
(lambda (x) (square (first x)))
The square appears first!!



This is because Scheme evaluates INSIDE OUT. The first procedure call
evaluated is (first x) because it is most inside. "square" is outside
of "(first x)" so it gets called second.




So, the input x first goes through the function "first", then it goes
through the function "square"




Let's also introduce the identity function (lambda (x) x), which
doesn't do anything to the argument, so it's just a pipe. But we'll
still think of it as a machine.




Ok, so if we call (repeat square 1), we compose square with the
identity function and get:




Notice that (repeat square 1) is the machine in the picture. The
machine "repeat" is NOT IN THE PICTURE. In fact, you can think of "repeat" as a mechanic who is making all the machines that we see.



Since we are composing two machines, you might think the Scheme code
is:
(lambda (x)
   (square (lambda (y) y)))

NO! In that WRONG code, you're feeding the machine (lambda (y) y) into
the machine "square"! That is the WRONG way to connect machines in
Scheme.



The RIGHT way:
(lambda (x)
  (square ( (lambda (y) y)  x ) ) )


REMEMBER! You can't read Scheme code from left to right! You have to
read it INSIDE OUT.

Alright, what if we have (repeat square 2) then? Try mentally
picturing this yourself. Does it look like this?




Do you see that if you feed 4 into the (repeat square 2) machine, you
square 4 twice?



What about (repeat square 3)?




So what about (repeat square n) for some general n?




Where we kept the (repeat square (- n 1)) machine closed. If we open
up the (repeat square (- n 1)) machine, we will see many many machines
connected together just as before.



So, here is a question to test your understanding:
How many procedure are there TOTAL in when we call (repeat square n) ?



ONE LAST IMPORTANT WORD:
here, we treated the machine (repeat square n) as if its name is just
"(repeat square n)". In fact, "repeat" is a machinist THAT CREATES
MACHINES! So more accurately, we should say
(repeat square n) is the machine that's created by calling "repeat"


Hope that was helpful.


-min