#lang racket

; file:    fold-demo.rkt
; author:  Robert Keller
; purpose: Showing meaning of foldr and foldl

(require htdp/testing)
(require (lib "trace.ss"))

; bin is a generic binary operator, that is intentionally not commutative.
; It returns a list of an operator symbol '+ followed by the literal arguments.

(define (bin X Y)
  (list '+ X Y))


; foldr "folds from the right". The unit (second argument) is a basis,
; then list elements, right-most first, are combined using the
; binary operator (first argument) applied to the next list element
; from the right and an accumulated value.

(check-expect (foldr bin 0 '(1 2 3 4 5)) '(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0))))))

; Here's an explanation in code:

(define (my-foldr B U L)
  (if (null? L)
      U
      (B (first L) (my-foldr B U (rest L)))))

; This definition is not tail-recursive. 

; Below we show that the explanation gives the same result as the built-in:

(check-expect (my-foldr bin 0 '(1 2 3 4 5)) (foldr bin 0 '(1 2 3 4 5)))



; foldl "folds from the left". The unit (second argument) is a basis,
; then list elements, left-most first, are combined using the
; binary operator (first argument) applied to the next list element
; from the left and an accumulated value.

(check-expect (foldl bin 0 '(1 2 3 4 5)) '(+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0))))))

; Here's an explanation in code:

(define (my-foldl B U L)
  (if (null? L)
      U
      (my-foldl B (B (first L) U) (rest L))))

; Notice that the unit is changed as recursion progresses in this case, 
; effectively treating the unit variable as an accumulator.

; This definition is tail-recursive.

; Below we show that the explanation gives the same result as the built-in:

(check-expect (my-foldl bin 0 '(1 2 3 4 5)) (foldl bin 0 '(1 2 3 4 5)))


; Returning to foldr, we can give a tail-recursive version by using
; a helper function with an accumulator argument:

(define (my-foldr-helper B L Acc)
  (if (null? L)
      Acc
      (my-foldr-helper B (rest L) (B Acc (first L)))))



(generate-report)

(trace my-foldr my-foldl)

(my-foldl bin 0 '(1 2 3 4 5))
(my-foldr bin 0 '(1 2 3 4 5))