;; This log demonstrates the use of the REDUCE function
;;   that can be so many things depending on how it's applied.

(require 'cl) ; Emacs' LISP (eLisp) is not Common Lisp, but has CL libraries
cl

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

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

(cl-reduce 'myplus '(1 2 3 4 5 6))

("(+)" 1 2)
("(+)" 3 3)
("(+)" 6 4)
("(+)" 10 5)
("(+)" 15 6)
21

(defun mytimes (x y)
  (print (list "(X)" x y)) ; print a trace message
  (* x y))
mytimes

(cl-reduce 'mytimes '(1 2 3 4 5 6))

("(X)" 1 2)
("(X)" 2 3)
("(X)" 6 4)
("(X)" 24 5)
("(X)" 120 6)
720

;; The above are called left-folds, as they start applying the supplied
;;   function from the left. However, right-folds applying from the right
;;   are also an option:

(cl-reduce 'mytimes '(1 2 3 4 5 6) :from-end t)

("(X)" 5 6)
("(X)" 4 30)
("(X)" 3 120)
("(X)" 2 360)
("(X)" 1 720)
720

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

("(X)" 100 1)
("(X)" 100 2)
("(X)" 200 3)
("(X)" 600 4)
("(X)" 2400 5)
("(X)" 12000 6)
72000

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

("(X)" 6 100)
("(X)" 5 600)
("(X)" 4 3000)
("(X)" 3 12000)
("(X)" 2 36000)
("(X)" 1 72000)
72000

;; length is a fold
(cl-reduce (lambda (x y) (+ x 1))
	   '("foo" "bar" "baz" "quux")
	   :initial-value 0 )
4

;; mapcar is a fold 
(defun fold-map (fun seq)
  (cl-reduce (lambda (num lst) (cons (funcall fun num)  lst))
	     seq
	     :initial-value nil
	     :from-end t))
fold-map


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

;; reverse is a fold
(cl-reduce (lambda (lst x) (cons x lst))
	   '(A B C D E)
	   :initial-value nil )
(E D C B A)

;; What about filter? 
(seq-filter 'evenp '(1 2 3 4))
(2 4)

;; filter is a fold too:
(cl-reduce (lambda (x lst) (if (evenp x) (cons x lst) lst))
	   '(1 2 3 4 5 6)
	   :initial-value nil
	   :from-end t )
(2 4 6)

;; In class, we briefly looked at the implementation of cl-reduce in eLisp.
;;  Can you implement it in a tail-recursive way ?

(defun foldl (fn acc lst)
  (if (null lst)
      acc
      (foldl fn (funcall fn acc (car lst)) (cdr lst))))
foldl