49

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.

5
  • 34
    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. Nov 24, 2009 at 4:43
  • 4
    They voted to close it, because it's an exact duplicate.
    – Rayne
    Nov 24, 2009 at 5:42
  • 1
    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? Nov 24, 2009 at 16:35
  • 18
    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. Nov 25, 2009 at 9:42
  • 18
    @MarcGravell – where's the duplicate? This was the top result on Google for "clojure trees" for me just now. Dec 15, 2013 at 20:38

3 Answers 3

39
'(A (B (D) (E)) (C (F)))
5

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
  • 1
    it has first & rest in place of car cdr Nov 24, 2009 at 4:38
  • thanks ;) common lisp has both. i'll edit. it does have 'cons' though? Nov 24, 2009 at 6:45
  • I think you should edit it to say "I only know common lisp". Common Lisp is not 'Lisp'. It's a Lisp.
    – Rayne
    Nov 24, 2009 at 9:07
3

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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.