#lang racket

; Combinators for generic generation of recursive functions over linear
; data structure, using direct and continuation passing style of computation.

; In general, a simple recursive function can be written as a
; combinator on functions that say how to break the problem into smaller
; pieces, and then combine them into a bigger result.  

; For example, this defines factorial recursively:

(define AtBase? (lambda (x) (<= x 1)))
(define BaseCase (lambda (x) 1))
(define Combine (lambda (x recursion-result) (* x recursion-result)))
(define Decomp (lambda (x) (- x 1)))

; Direct style

(define (gen-fn-lin AtBase? BaseCase Combine Decomp)
    ; we need the lerrec here because we want to refer to the 
    ; variable that we are defining
    (letrec (
       [ fn (lambda (x)                                                  
     (if (AtBase? x) (BaseCase x)
          (Combine x (fn (Decomp x))))) ] )
      
  fn))

(define fn (gen-fn-lin AtBase? BaseCase Combine Decomp))

; Continuation passing style

(define (gen-fn-lin-cc AtBase? BaseCase Combine Decomp) (
   (letrec (
       [ fn-cc-r (lambda (x cc)
           (if (AtBase? x) 
               ; compute the base case, and then continue
               (cc (BaseCase x)) 
               ; recurse, and then combine the result, and continue.  Note 
               ; this is tail recursive in fn-cc-r
               (fn-cc-r (Decomp x) (lambda (result) (cc (Combine x result))))
               ) ) ]
        ) 
     
        ; start the recursion with the identity continuation
        (lambda (x) (fn-cc-r x (lambda (r) r)) )
    )))

(define fn-cc (gen-fn-lin AtBase? BaseCase Combine Decomp))

(fn 3)
(fn-cc 3)

(define fm (gen-fn-lin AtBase? (lambda (x) 42) Combine Decomp))
(fm 1)
(fm 2)