函数式遍历树结构

Question

我正在尝试编写自己的“遍历树”函数，但我在FP方面还很新手

我已经编写了这些函数，并且它们能正常工作，但看起来很丑陋

(defrecord Tree [value left right])
(defn depth_walk_tree
    [tree functor]
        (let [item (functor (:value tree))]
            (let [leftlst 
                    (if (:left tree) 
                        (cons item (depth_walk_tree (:left tree) functor)) 
                        (list item))
                 ]
                    (if (:right tree)
                        (concat 
                            leftlst 
                            (depth_walk_tree (:right tree) functor)) 
                        leftlst))))

(def tree (Tree. 1 (Tree. 2 (Tree. 0 nil nil) (Tree. 90 nil nil)) (Tree. 3 nil (Tree. 10 nil nil)) ))
    (println (depth_walk_tree tree #(+ % 1) ))

程序的答案是

(2 3 1 91 4 11); is Ok

有人能告诉我如何使它更美观吗？

PS 对不起我的写作错误。英语不是我的母语。

- Daiver

Answer 1

在我看来,这个看起来更加实用:

(defn depth_walk_tree [tree functor]
  (concat
    (list (functor (:value tree)))
    (if (:left  tree) (depth_walk_tree (:left  tree) functor))
    (if (:right tree) (depth_walk_tree (:right tree) functor))))

同时它也保留了原本的结果：

(depth_walk_tree tree inc)
=> (2 3 1 91 4 11)

- Óscar López

---

太纯净了！我不知道concat会传递'nil'值。谢谢。 - Daiver

函数式编程是关于简洁和优雅的 :) - Óscar López

你如何避免非尾递归引起的堆栈溢出？ - event_jr

@event_jr 可以通过将上述内容转换为尾递归来实现，当然 :P。但这已经超出了重点，OP正在寻求一种惯用的、_美丽的_解决方案，对于初学者来说，尾递归版本会更难理解。这不是一个关于效率的问题，我怀疑OP不会定义如此大的树以致于导致堆栈溢出，这只是一个学习练习。过早优化是万恶之源... - Óscar López