; We can easily imagine s-expression as a tree, for example
; '(+ (- 1 2) (+ 3 4) (- 5 (+ 6 7)))
;
; +-+
; |+|
; _+-+_
; _,' | `._
; _.' | `._
; _.' | `._
; .' | `.
; +-+ +-+ +-+
; |-| |+| |-|
; +-+ +-+ +-+
; / \ / \ / \
; / \ / \ / \
; / \ / \ / \
; +-+ +-+ +-+ +-+ +-+ +-+
; |1| |2| |3| |4| |5| |+|
; +-+ +-+ +-+ +-+ +-+ +-+
; / \
; / \
; / \
; +-+ +-+
; |6| |7|
; +-+ +-+
;
; When we see it as tree, we can easily recognize branches and
; leaves of that tree - they are subexpressions of the original
; s-expression. In this case, our intuition is good enough so
; I can avoid mathematical definitions, and instead write two
; functions that return list of all branches and leafs of a given
; s-expression. By definition, original s-expression and all
; leaves are also branches.
(set 'branches
(lambda(L)
(if (list? L)
(cons L (apply append (map branches (rest L))))
(list L))))
(set 'leafs
(lambda(L)
(if (list? L)
(apply append (map leafs (rest L)))
(list L))))
(println (branches '(+ (- 1 2) (+ 3 4) (- 5 (+ 6 7)))))
(println (leafs '(+ (- 1 2) (+ 3 4) (- 5 (+ 6 7)))))
; ((+ (- 1 2) (+ 3 4) (- 5 (+ 6 7)))
; (- 1 2) 1 2 (+ 3 4) 3 4 (- 5 (+ 6 7)) 5 (+ 6 7) 6 7)
; (1 2 3 4 5 6 7)
; Note that expression '(+ 1 2) is leaf, while (quote (+ 1 2))
; isn't.
; Graph is drawn with excellent ASCII editor Jave, www.jave.de
;
(exit)
Trees, Branches and Leaves.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment