;;; Everything is a fold if you have the right lambda

;;; Read SICP Section 2.2 through p. 165 (p. 194 of the PDF). 

;;; Read the first half of https://www.cs.cornell.edu/courses/cs3110/2014sp/lectures/5/map-fold-map-reduce.html about Map and Reduce

;; eLisp includes many Common Lisp in cl-lib, including cl-reduce. By default, it's a left fold:

(require 'cl-lib)

(cl-reduce '+ '(1 2 3 4 5))
15

(cl-reduce '* '(1 2 3 4 5))  ;; oh look, it's our good friend the factorial
120

;; Let's trace how it works for the left fold

(defun myplus (x y)
  (print (list "myplus" x y)) ; print a trace message
  (+ x y))
myplus

(myplus 2 3)

("myplus" 2 3)
5

(cl-reduce 'myplus '(1 2 3 4 5))
                     -+- 
                       -+- 
                         -+- 
                           -+-
("myplus" 1 2)
("myplus" 3 3)
("myplus" 6 4)
("myplus" 10 5)
15

;; We can also do the right fold, starting from the right:

(cl-reduce 'myplus '(1 2 3 4 5) :from-end t) 
                           -+-
                         -+- 
                       -+-
                     -+- 

("myplus" 4 5)
("myplus" 3 9)
("myplus" 2 12)
("myplus" 1 14)
15

;; We can start with an initial value, which is actually a better way to define the fold,
;;   as we'll see below.

(cl-reduce 'myplus '(1 2 3 4 5) :initial-value 100 :from-end t)

("myplus" 5 100)
("myplus" 4 105)
("myplus" 3 109)
("myplus" 2 112)
("myplus" 1 114)
115

;; ..and the left fold with an initial value: 

(cl-reduce 'myplus '(1 2 3 4 5) :initial-value 100)

("myplus" 100 1)
("myplus" 101 2)
("myplus" 103 3)
("myplus" 106 4)
("myplus" 110 5)
115

;; But here is the kicker: the function folded over the list, left or right,
;;   need not act just on pairs of elements in the list! Instead, by choosing
;;   the right initial value and the types of the left and the right arguments,
;;   we can get classic list functions like length, map, and filter as folds over the list!

;; Length: 

(cl-reduce (lambda (x y) (1+ x))
	   '(aa bb)
	   :initial-value 0 )
2

(cl-reduce (lambda (x y) (1+ x))
	   '(aa bb cc dd ee)
	   :initial-value 0 )
5

(cl-reduce (lambda (x y) (1+ x))
	   nil
	   :initial-value 0 )
0

;; Map, a right fold: 

(defun fold-map (f xs)
  (cl-reduce (lambda (x y)
	       (cons (funcall f x) y) 
	       )
	     xs
	     :from-end t
	     :initial-value nil)) ;; we start from an empty list
fold-map

(fold-map (lambda (x) (* x x)) '(1 2 3 4 5 6))
(1 4 9 16 25 36)

;; Filter, another right fold:

(defun fold-filter (f xs)
  (cl-reduce (lambda (x y)
	       (if (funcall f x)
		   (cons (funcall f x) y)
		 y))
	     xs
	     :from-end t
	     :initial-value nil)) ;; we start from an empty list
fold-filter

(fold-filter 'cl-evenp '(1 2 3 4 5 6))
(t t t)

;; Oops. What did I do wrong? :)

(defun fold-filter (f xs)
  (cl-reduce (lambda (x y)
               (if (funcall f x)
                   (cons x y)
                 y))
             xs
             :from-end t
             :initial-value nil)) ;; we start from an empty list     
fold-filter

(fold-filter 'cl-evenp '(1 2 3 4 5 6))
(2 4 6)

;;; It is very instructive to write your own recursive folds:

;; (defun fold-left (f init-val xs) .. )
;; (defun fold-right (f xs init-val) .. )

;; Don't peek below :)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

(defun fold-left (f init-val xs)   ; init-val on the left, in the order of natural application
  (cond ((null xs)  init-val)       ; for an empty list, return init-val 
	((consp xs) (fold-left f    ; this is tail-recursive
			       (funcall f init-val (car xs))
			       (cdr xs)))))
fold-left

(fold-left '+ 0 '(1))
1

(fold-left '+ 0 '(1 2))
3

(fold-left '+ 0 '(1 2 3 4))
10

(fold-left '+ 0 nil)
0

(fold-left 'myplus 0 '(1 2 3 4 5 6 7))

("myplus" 0 1)
("myplus" 1 2)
("myplus" 3 3)
("myplus" 6 4)
("myplus" 10 5)
("myplus" 15 6)
("myplus" 21 7)
28

;; Now for the right fold

(defun fold-right (f xs init-val)   ; init-val on the right, in the order of natural application
  (cond ((null xs)  init-val)       ; for an empty list, return init-val 
	((consp xs) (funcall f
			     (car xs)
			     (fold-right f (cdr xs) init-val))))) ; Not tail-recursive, note trace below. We need to get to the end of the list before we can call any instance of f(x, y)
fold-right

(fold-right 'myplus '(1 2 3 4 5) 100)

("myplus" 5 100)
("myplus" 4 105)
("myplus" 3 109)
("myplus" 2 112)
("myplus" 1 114)
115

(fold-right (lambda (x y) (cons (* x x) y)) '(1 2 3 4 5 6 7) nil)
(1 4 9 16 25 36 49)

;; We'll see ways to optimize tail-recursion in fold-left (with named-let) and how to make fold-right efficient
;;   despite not being tail-recursive (hint: we'll do it with using the continuation-passing style
;;    of rewriting the function)

;; Now can you see how to do list reversing as a fold? Check out reverse and nreverse in eLisp
;;  for testing.