#lang racket
; suppose that we want to compose a function fn with itself n times
; applying it to argument x.  

; For example, function g composed 3 times on argument y is 
; g(g(g(y))) (in normal math notation), or
; (g (g (g y))) as a Scheme expression
; Function g composed 0 times on y is just y.

(define fcompose (lambda (fn n x) 
    (if (<= n 0) 
        ; base case, the identity function, just return x
        x
        ; recursion, compute one application and then send it
        ; to n-1 applications
        ; note that fcompose is in tail-recursive position, so 
        ; this code is run as a loop with constant stack space
        ; watch how the stack grows if instead this non-tail recursive
        ; formulation is used: (fn (fcompose fn (-n 1) x))
        (fcompose fn (- n 1) (fn x))
    )
))

; compute powers of two
(define times2 (lambda (x) (* 2 x)))

(fcompose times2 5 1)
(fcompose times2 0 1)

(define power2 (lambda (x) (fcompose times2 x 1)))
(power2 4)
(power2 0)

; compute y ^ n
(define yexpn (lambda (y n) 
    (fcompose (lambda (p) (* y p)) n 1)
))

(yexpn 2 5)
(yexpn 5 3)

; sum up the first n integers 1, 2, ..., n
; we keep a state consisting of a list (sum i) of two elements
; where sum is the sum so far, and i is the next element of the 
; sequence.

; This corresponds to a loop body that looks something like this:
;     sum = sum + i
;     i = i + 1

; making lists with cons car and cdr is really annoying to read
(define loop-body-ugly (lambda (state) 
    ; new state is updated sum and next i.  Create a 2 element list
    (cons (+ (car state) (cadr state))
        (cons (+ 1 (cadr state)) '() ))
    ))

; which is why first, second, third, fourth are defined
; and there is a list function which takes an arbitrary number of 
; arguments and wraps them into a list

(define loop-body (lambda (state) 
    ; new state is updated sum and next i.  Create a 2 element list
    (list   
          (+ (first state) (second state))
          (+ 1 (second state)))
    ))

; run the loop 10 times, starting with initial state sum=0 i=1

(fcompose loop-body 10 '(0 1))

; a function to run the loop n times, starting with initial state sum=0 i=1
; this is exactly the loop
; sum = 0
; i = 1
; for (index = 0; index < n; index++) {
;     sum = sum + i
;     i = i + 1
;     }

(define sum-of-n (lambda (n)
    (first (fcompose loop-body n '(0 1)))
    ))

(sum-of-n 10)
(sum-of-n 0)
(sum-of-n 3)