recursion - 累加器、conj 和递归

Question

我已经解决了 4clojure.com 上的 45 个问题，并且在尝试使用递归和累加器解决一些问题的方式中，我注意到一个反复出现的问题。

我会尽我所能解释我正在做的事情，以最终得到模糊的解决方案，希望一些 Clojurers 能够“得到”我没有得到的东西。

例如，问题 34 要求编写一个函数(不使用范围)，将两个整数作为参数并创建一个范围(不使用范围)。简单地说，你做 (... 1 7) 并且你得到 (1 2 3 4 5 6)。

现在这个问题不是关于解决这个特定问题。

如果我想使用递归和累加器来解决这个问题怎么办？

我的思考过程是这样的:

我需要编写一个带有两个参数的函数，我从 (fn [x y] )

开始

我需要递归，我需要跟踪一个列表，我将使用一个累加器，所以我在第一个函数中编写了一个带有附加参数的第二个函数:

(fn
[x y]
((fn g [x y acc] ...)
X
是
'())

(显然我无法在 SO 上正确格式化 Clojure 代码!？)

在这里，我已经不确定我做得是否正确:第一个函数必须恰好采用两个整数参数(不是我的调用)，我不确定:如果我想使用累加器，我可以使用累加器而不创建嵌套函数？

然后我想 conj，但我不能这样做:

(conj 0 1)

所以我做了一些奇怪的事情来确保我先有一个序列，最后我得到了这个:

(fn
   [x y]
   ((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x)))
    x
    y
    '()))

但是这会产生这个:

(1 (2 (3 4)))

取而代之的是:

(1 2 3 4)

所以我最终做了一个额外的扁平化并且它有效但它完全丑陋。

我开始了解一些事情，在某些情况下，我什至开始以一种更加笨拙的方式“思考”，但我在编写解决方案时遇到了问题。

例如在这里我决定:

使用累加器

通过递增 x 直到达到 y 来递归

但我最终得到了上面的怪物。

有很多方法可以解决这个问题，而且，这不是我所追求的。

我所追求的是，​​在我决定 cons/conj，使用累加器并递归之后，我可以得到这个(不是我写的):

#(loop [i %1
        acc nil]
  (if (<= %2 i)
    (reverse acc)
    (recur (inc i) (cons i acc))))

取而代之的是:

((fn
  f
  [x y]
  (flatten
   ((fn
     g
     [x y acc]
     (if (= x y) acc (conj (conj acc (g (inc x) y acc)) x)))
    x
    y
    '())))
 1
 4)

我认为这是能够解决一些问题的开始，但我对我倾向于产生的丑陋解决方案感到有点失望......

Answer 1

我认为这里有几件事要学习。

第一 ，一种一般规则 - 递归函数通常具有自然顺序，而添加累加器则相反。你可以看到，因为当一个“正常”(没有累加器)递归函数运行时，它会做一些工作来计算一个值，然后递归生成列表的尾部，最后以一个空列表结束。相比之下，对于累加器，您从空列表开始并将内容添加到前面 - 它在另一个方向上增长。

所以通常，当你添加一个累加器时，你会得到一个相反的顺序。

现在通常这无关紧要。例如，如果您生成的不是序列而是一个值，该值是可交换运算符(如加法或乘法)的重复应用。那么无论哪种方式，您都会得到相同的答案。

但在你的情况下，这很重要。你将把列表倒过来:

(defn my-range-0 [lo hi] ; normal recursive solution
  (if (= lo hi)
    nil
    (cons lo (my-range-0 (inc lo) hi))))

(deftest test-my-range-1
  (is (= '(0 1 2) (my-range-0 0 3))))

(defn my-range-1 ; with an accumulator
  ([lo hi] (my-range-1 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (cons lo acc)))))

(deftest test-my-range-1
  (is (= '(2 1 0) (my-range-1 0 3)))) ; oops!  backwards!

通常，解决此问题的最佳方法就是在最后反转该列表。

但这里有一个替代方案——我们实际上可以倒着做这项工作。您可以减少上限，而不是增加下限:

(defn my-range-2
  ([lo hi] (my-range-2 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (let [hi (dec hi)]
        (recur lo hi (cons hi acc))))))

(deftest test-my-range-2
  (is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order

[注意 - 下面还有另一种反转方式；我没有很好地构建我的论点]

第二个 ，正如您在 my-range-1 中看到的那样和 my-range-2 , 编写带有累加器的函数的一种好方法是编写一个带有两组不同参数的函数。这为您提供了一个非常干净(恕我直言)的实现，而无需嵌套函数。

你还有一些关于序列的更一般的问题， conj之类的。这里 clojure 有点凌乱，但也很有用。上面我一直在用基于缺点的列表给出一个非常传统的观点。但是 clojure 鼓励您使用其他序列。与缺点列表不同，向量向右增长，而不是向左增长。所以另一种扭转结果的方法是使用向量:

(defn my-range-3 ; this looks like my-range-1
  ([lo hi] (my-range-3 lo hi []))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-3 ; except that it works right!
  (is (= [0 1 2] (my-range-3 0 3))))

这里 conj正在添加到右侧。我没有使用 conj在 my-range-1 ，所以这里重写为更清楚:

(defn my-range-4 ; my-range-1 written using conj instead of cons
  ([lo hi] (my-range-4 lo hi nil))
  ([lo hi acc]
    (if (= lo hi)
      acc
      (recur (inc lo) hi (conj acc lo)))))

(deftest test-my-range-4
  (is (= '(2 1 0) (my-range-4 0 3))))

请注意，此代码看起来与 my-range-3 非常相似。但结果是倒退的，因为我们从一个空列表开始，而不是一个空向量。在这两种情况下， conj在“自然”位置添加新元素。对于右侧的向量，但对于列表，它在左侧。

我突然想到你可能并不真正理解什么是列表。基本上是 cons创建一个包含两个东西(它的参数)的盒子。第一个是内容，第二个是列表的其余部分。所以名单 (1 2 3)基本上是 (cons 1 (cons 2 (cons 3 nil))) .相比之下，向量 [1 2 3]更像是一个数组(虽然我认为它是使用树实现的)。

所以 conj有点令人困惑，因为它的工作方式取决于第一个参数。对于列表，它调用 cons所以在左边添加东西。但是对于向量，它将数组(类似事物)扩展到右侧。另外，请注意 conj将现有序列作为第一个参数，将要添加的内容作为第二个参数，而 cons是相反的(首先添加的东西)。

以上所有代码均可在 https://github.com/andrewcooke/clojure-lab 获得

更新:我重写了测试，以便在代码生成列表的情况下，预期结果是引用列表。 =将比较列表和向量并在内容相同时返回 true，但使其明确显示更清楚地显示您在每种情况下实际获得的内容。请注意 '(0 1 2)与 '前面就像 (list 0 1 2) - '停止评估列表(没有它， 0 将被视为命令)。