What would be an idiomatic way to represent a tree in Clojure? E.g.:
A
/ \
B C
/\ \
D E F
Performance is not important and the trees won't grow past 1000 elements.
48
votes
WTF is wrong with you people, every time someone doesn't like the question they hit close. stackoverflow was a very good place to learn something now it has turned in to digg, with a lot of idiots. If you don't like the question thats what down vote is for.
- Hamza Yerlikaya
They voted to close it, because it's an exact duplicate.
- Rayne
Agreed; this isn't about liking the question; as you say re learning something - perhaps learn from the last time somebody asked the same question?
- Marc Gravell
The appropriate thing to do would be to downvote AND ADD A COMMENT POINTING OUT THE REASON. If you're community-minded enough to do the former, you should do the latter too. Otherwise you're just being spiteful.
- Carl Smotricz
@MarcGravell – where's the duplicate? This was the top result on Google for "clojure trees" for me just now.
- Kenny Evitt
3 Answers
5
votes
There's a scary way of doing it using just cons:
(defn mktree
([label l r] (cons label (cons l r)))
([leaf] (cons leaf (cons nil nil))))
(defn getlabel [t] (first t))
(defn getchildren [t] (rest t))
(defn getleft [t] (first (getchildren t)))
(defn getright [t] (rest (getchildren t)))
Note that children isn't a list; it's a pair. If your trees aren't just binary, you could make it a list. use nil when there's no left or right child, of course.
Otherwise, see this answer.
The tree in your picture:
(mktree 'A (mktree 'B (mktree 'D) (mktree 'E)) (mktree 'C nil (mktree 'F)))
3
votes
Trees underly just about everything in Clojure because they lend themselves so nicely to structural sharing in persistent data structure. Maps and Vectors are actually trees with a high branching factor to give them bounded lookup and insert time. So the shortest answer I can give (though it's not really that useful) is that I really recommend Purely functional data structures by Chris Okasaki for a real answer to this question. Also Rich Hickey's video on Clojure data structures on blip.tv
(set 'A 'B 'C)
