深反向Clojure

Question

我正试图在clojure中实现深度逆转.如果lst是(1(2(3 4 5))(2 3)),它应该返回((3 2)((5 4 3)2)1).
这是我到目前为止:

defn dRev [lst]
    ( if (= lst ())
        nil
        ( if (list? (first lst))
            ( dRev (first lst) )
            ( concat
                ( dRev (rest lst)) (list (first lst))
            )
        )
   )
)

但是,我的实现仅在嵌套列表是最后一个元素时才有效,但结果列表也是平展的.

例如:(dRev'(1 2(3 4))将返回(4 3 2 1).
否则,例如:(dRev'(1(2 3)4))将仅返回(3 2 1).

我现在打了这个砖墙一段时间,我无法找到我的代码的问题.
有人可以帮帮我吗？

Answer 1

另一个答案为您提供了Clojure中深度反转的最佳实现,因为它使用了将clojure.walk/postwalk函数深度应用于集合的每个元素的问题.在这里,我将向您介绍您发布的实施问题.

首先,不寻常的格式化使得很难发现正在发生的事情.以下是固定格式的相同内容:

(defn dRev [lst]
  (if (= lst ())
    nil
    (if (list? (first lst))
        (dRev (first lst))
        (concat (dRev (rest lst))
                (list (first lst))))))

接下来,还有其他一些尚未修复行为的小修补程序:

• 更改函数名称以符合Clojure约定(连字符而不是camel-case),
• 使用通常的Clojure默认名称coll代替集合参数lst,
• 使用empty?检查空集,
• ()在默认情况下返回,因为我们知道我们想要返回一个列表而不是其他类型的seq,
• 并使用coll?,而不是list?因为我们本来也可能扭转任何集合,而不是仅仅列出:

(如果您确实只想反转列表并保留所有其他集合,请反转上一次更改.)

(defn d-rev [coll]
  (if (empty? coll)
    ()
    (if (coll? (first coll))
        (d-rev (first coll))
        (concat (d-rev (rest coll))
                (list (first coll))))))

现在,格式化修复使得显而易见的是实现的主要问题:在递归调用((d-rev (first coll))resp.(dRev (first lst)))中,只返回该递归的结果,但是您忘记处理列表的其余部分.基本上,您需要做的是处理集合的其余部分始终相同,并且仅根据第一个元素是否为list resp来更改处理第一个元素的方式.是否收集:

(defn d-rev [coll]
  (if (empty? coll)
    ()
    (concat (d-rev (rest coll))
            (list (if (coll? (first coll))
                    (d-rev (first coll))
                    (first coll))))))

这是一个有效的解决方案.

但它非常低效,因为它concat完全重建了每个元素的列表.通过使用尾递归算法可以获得更好的结果,这非常简单(因为序列上的尾递归反转元素的顺序很自然):

(defn d-rev [coll]
  (loop [coll coll, acc ()]
    (if (empty? coll)
      acc
      (recur (rest coll)
             (cons (if (coll? (first coll))
                     (d-rev (first coll))
                     (first coll))
                   acc)))))

作为最后一个建议,这里有一个解决方案,它halfways朝也通过解决在更高层次上的问题从另一个答案,但它仅使用核心功能reverse和map适用功能于序列的每一个元素,但不深孔自行递归:

(defn deep-reverse [coll]
  (reverse (map #(if (coll? %) (deep-reverse %) %) coll)))

Answer 2

你可以建立你与写作clojure.walk/postwalk和clojure.core/reverse.这会对树输入执行深度优先遍历,并反转它找到的任何seq.

(defn dRev [lst]
  (clojure.walk/postwalk #(if (seq? %) (reverse %) %) lst))