;;; Although Lisp has loops (and eLisp often uses loops, because Emacs didn't
;;;  support tail call optimizations until fairly recently), the best insights
;;;  of Lisp come from purposefully following the objects' own recursive structure
;;;  instead of loops. This kind of loop-less programming forces you to think about
;;;  the structure of objects and all the cases---and the code almost writes itself!   

;; Let's do a recursive list length

(defun mylen (xs)
  "Length of a list"
  (cond ((null  xs) 0) ; empty list has length 0
	((consp xs) (1+ (mylen (cdr xs))))   ; however we might compute the length of a list,
					; the length of a list with one more cons cell is +1 of the former.
					; Turns out this is enough: the base case and the inductive step uniquely define length!
					; There is no more code to write. What remains is dealing with getting a non-cons, non-nil.
	(t (error "What is the length of an atom? I won't know"))))  ; Deciding what to declare to be a type error, and how to represent errors and handle them is also important. The structure of thisrecursive code compels us to make this choice so that our cond cases are complete. We'll talk more of it when we look at exceptions and monadic types, two radically different ways to handle errors.


(mylen '())
0
(mylen '(100))
1
(mylen '(1 2 33))
3

;;; Now look at eLisp's own length function, and then at safe-length. 

;;  Find the code for these functions with M-x find-function. You will be asked
;;  for the directory where Emacs' source code resides in your system. I got mine by cloning Emacs
;;  source with "git clone https://github.com/emacs-mirror/emacs.git" and then pointing to
;;  ~/emacs/src

(length '(1 2 33))
3

(length [1 2 3])
3

(length "foobar")
6

(length 1)
;; Lisp error: (wrong-type-argument sequencep 1)

(safe-length 1)
0

;;; Note that we only compute the top-level length of the list:
(mylen '(((((a) b)) c)))
1

(load "~/cs59/draw-tree.el")
t

(draw-tree '(((((a) b)) c)))
"
[o|/]
 |      
[o|o]---[o|/]
 |       |      
 |       c      
 |      
[o|/]
 |      
[o|o]---[o|/]
 |       |      
[o|/]    b      
 |      
 a      
"

;;; Let's count the atoms in the entire tree.

;; This code similarly writes itself. A tree is either a nil, an atom,
;; or a cons. No matter how we choose to compute the number of atoms
;; in the subtrees hanging off a cons' car and cdr, the count of atoms
;; for the former tree will be the sum of the latter two. So we write:

(defun count-atoms (xs)
  (cond ((null  xs) 0) ; empty tree has 0 atoms
	((consp xs) (+ (count-atoms (car xs)) (count-atoms (cdr xs))))
	((atom  xs) 1))) ; an atom counts for 1 
count-atoms

(setq t1 '(((((a) b)) c)))
((((... b)) c))

(count-atoms ())
0

(count-atoms 1)
1

(count-atoms t1)
3

;;; Let's find the sum of leaves in a tree. It's a very similar function, because
;;;  it follows the same tree structure. No matter how we compute the sums of the subtrees
;;;  in the car and cdr of a cons cell, the result for the tree with this extra cons cell
;;;  is a sum of those of the subtrees. This is enough.

(defun sum-tree (xs)
  (cond ((null  xs) 0) ; empty tree has 0 atoms
	((consp xs) (+ (sum-tree (car xs)) (sum-tree (cdr xs))))
	((atom  xs) xs)))  ; an atom counts as itself, because in Lisp number atoms eval to self
sum-tree

;; number atoms eval to self
1
1

(eval '1)
1

(eval (read "1")) ;; the input string "1" represents the atom 1. The string "1" would be "\"1\""
1

(eval (read "\"1\""))
"1"

(setq t2 '(((((1) 3)) 4)))
((((... 3)) 4))

(sum-tree t2)
8

(setq t3 '(((12 7) ((5) 3)) 1))
(((12 7) ((5) 3)) 1)

(sum-tree t3)
28

;;; Here is another example of recursive programming and function/property definition.
;;;   Recall how we computed the length of a list, ignoring whatever subtrees might hang
;;;   under the top levels of cons cells. Our mylen ignored the cars altogether, assuming
;;;;  that the list had a flat depth of 1. Can we compute the "real" depth of a tree?

;;;  First, we need to decide what is depth. The draw-tree examples suggest a definition
;;;   where only doing "down" counts. E.g., t2 below has depth 5 and t4 has
;;;   depth 4. Now, what depth should we say t3 and t5 have?

;;; The t2, t3, and t4 examples suggest that however we compute the depths of the subtree
;;;   in the car of a cons cell, the depth of the tree with the extra cons cell will be +1.
;;;   For cons cells that have a cdr, as t4 suggests, the depth should be the larger
;;;   of the depth of the car-tree plus one and the depth of the cdr-tree. In short,
;;;   going along a cdr doesn't count, but going down a car always does.

(draw-tree t2)
"
[o|/]
 |      
[o|o]---[o|/]
 |       |      
 |       4      
 |      
[o|/]
 |      
[o|o]---[o|/]
 |       |      
[o|/]    3      
 |      
 1      
"


(draw-tree t3)
"
[o|o]---[o|/]
 |       |      
 |       1      
 |      
[o|o]---[o|/]
 |       |      
 |      [o|o]---[o|/]
 |       |       |      
 |      [o|/]    3      
 |       |      
 |       5      
 |      
[o|o]---[o|/]
 |       |      
 12      7      
"

(setq t4 '((a b) (((c)))))
((a b) (((c))))

(draw-tree t4)
"
[o|o]---[o|/]
 |       |      
 |      [o|/]
 |       |      
 |      [o|/]
 |       |      
 |      [o|/]
 |       |      
 |       c      
 |      
[o|o]---[o|/]
 |       |      
 a       b      
"


(setq t5 '(((a b) (((c))))))
(((a b) ((...))))

(draw-tree t5)
"
[o|/]
 |      
[o|o]---[o|/]
 |       |      
 |      [o|/]
 |       |      
 |      [o|/]
 |       |      
 |      [o|/]
 |       |      
 |       c      
 |      
[o|o]---[o|/]
 |       |      
 a       b      
"

;;; If we assume the above, the code writes itself, once again! Note that here we
;;;   are defining the meaning of the tree structure _and_ of its "depth" property
;;;   at the same time ("co-defining" these, as the jargon goes).

(defun depth (xs)
  (cond ((null  xs) 0) ; empty tree has 0 depth
	((consp xs) (max (1+ (depth (car xs)))
			 (depth (cdr xs))))
	((atom  xs) 0)))   ; an atom counts as having depth 0 --- debatable, but it makes certain sense to count only cons cells down the car path 
depth

(depth ())
0                 ;; makes perfect sense

(depth '(1 2))    ;; makes some sense 
1

(depth 1)         ;; philosophically debatable ("is the depth of an atom 1 or 0?"), but we decided that only the down-the-car steps count, so this is consistent
0

(depth t1)
5

(draw-tree t1)
"
[o|/]
 |      
[o|o]---[o|/]
 |       |      
 |       c      
 |      
[o|/]
 |      
[o|o]---[o|/]
 |       |      
[o|/]    b      
 |      
 a      
"

(depth t2)
5

(depth t3)
4

(depth t5)
5

;;; Back to count-atoms and tree-sum, note that these two functions are very similar.
;;;  They both follow the recursive idea of how a tree is either a nil or a cons,
;;;   and only differ in how atoms and cons cells are treated. So we can have a function
;;;   that performs the common parts of the computation/traversal, and defers to supplied
;;;   actions for a leaf or non-leaf node, and, for completeness, an empty list.

(defun fold-tree (xs do-empty do-leaf do-cons)
  (cond ((null xs)  (funcall do-empty))
	((consp xs) (funcall do-cons
			     (fold-tree (car xs) do-empty do-leaf do-cons)
			     (fold-tree (cdr xs) do-empty do-leaf do-cons)))
	((atom xs)  (funcall do-leaf xs))))
fold-tree

;; count-atoms
(fold-tree t1
           (lambda ()  0)
           (lambda (a) 1)
           (lambda (r l) (+ r l)))
3

(fold-tree t3
           (lambda ()  0)
           (lambda (a) 1)
           (lambda (r l) (+ r l)))
5

;; 
(fold-tree t4
           (lambda ()  0)
           (lambda (a) 1)
           (lambda (r l) (+ r l)))
3


;; sum-tree
(fold-tree t2
           (lambda ()  0)
           (lambda (a) a)
           (lambda (r l) (+ r l)))
8

(fold-tree t3
           (lambda ()  0)
           (lambda (a) a)
           (lambda (r l) (+ r l)))
28

;;; Can depth be represented in the same way?