0

我正在尝试在 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)。

我现在碰到这堵砖墙一段时间了，我找不到我的代码的问题。
谁能帮帮我？

4

3 回答 3

7

另一个答案为您提供了 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 约定（连字符而不是驼峰式），
  • 对集合参数使用通常的 Clojure 默认名称，coll而不是lst,
  • 用于empty?检查空集合，
  • 在默认情况下返回()，因为我们知道我们想要返回一个列表而不是其他类型的序列，
  • 并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))）中，您只返回该递归的结果，但您忘记处理列表的其余部分。基本上，您需要做的是始终以相同的方式处理集合的其余部分，并且仅根据第一个元素是否为列表来更改处理第一个元素的方式。收藏与否：

(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)))))

作为最后一个建议，这是一个解决方案，它通过在更高级别上解决问题，与另一个答案接近一半，但它仅使用核心功能reverse，map并将功能应用于序列的每个元素，但不深入 -自行递归：

(defn deep-reverse [coll]
  (reverse (map #(if (coll? %) (deep-reverse %) %) coll)))
于 2013-10-03T12:26:37.193 回答
5

clojure.walk/postwalk您可以使用和构建您正在编写的内容clojure.core/reverse。这会对你的树输入进行深度优先遍历，并反转它找到的任何序列。

(defn dRev [lst]
  (clojure.walk/postwalk #(if (seq? %) (reverse %) %) lst))
于 2013-10-03T03:37:31.590 回答
0

这是我的问题版本，如果您输入以下内容：

(deep-reverse '(a (b c d) 3))

它返回

=> '(3 (d c b) a)

问题取自九十九 Lisp Problems

我的代码最终是这样的，不过，它们可能是更好的实现，这个工作正常。

(defn deep-reverse
  "Returns the given list in reverse order. Works with nested lists."
  [lst]
  (cond
    (empty? (rest lst))   lst
    (list? (first lst))   (deep-reverse(cons (deep-reverse (first lst)) (deep-reverse (rest lst))))

    :else
    (concat (deep-reverse (rest lst)) (list (first lst)))))

希望这就是你要找的！

于 2018-01-26T07:43:45.460 回答