累加器，conj和递归

Question

我已经解决了45个问题4clojure.com 我注意到一个反复出现的问题，我试图解决一些问题使用递归和累加器。

我会尽力解释我所做的最好的事情，最终得到fugly解决方案，希望一些Clojurers会"得到"我没有得到的东西。

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

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

如果我 要 要使用递归和累加器来解决这个问题？

我的思维过程是这样的:

• 我需要写一个函数接受两个参数，我从 (fn[x y])

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

  （fn [x y]
  ((fn g[x y acc]。..) x y '())

（显然我无法正确格式化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)

所以我最终做了一个额外的 展平 它有效，但它是完全丑陋的。

我开始理解一些事情，在某些情况下，我甚至开始以更clojuresque的方式"思考"，但我在编写解决方案时遇到了问题。

例如在这里我决定:

• 使用累加器
• 通过递增来递归 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

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

第一个, ，一种一般规则递归函数通常具有自然顺序，并且添加累加器会逆转该顺序。你可以看到，因为当一个"正常"（没有 累加器）递归函数运行，它做一些工作来计算一个值，然后递归生成列表的尾部，最后以空列表结束。相比之下，使用累加器，您从空列表开始，并将内容添加到前面-它正在增长 在另一个方向.

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

现在通常这并不重要。例如，如果您生成的不是序列，而是重复应用a的值 交换,交换 运算符（如加法或乘法）。然后你会得到同样的答案。

但在你的情况下，这很重要。你会把名单倒过来的:

(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 所以在左边增加了一些东西。但是对于一个向量，它将数组（-like thing）扩展到右边。另外，请注意 conj 将现有序列作为第一个arg，将要添加的东西作为第二个，而 cons 是相反的（要添加的东西是第一位的）。

---

以上所有守则可于 https://github.com/andrewcooke/clojure-lab

---

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

Answer 2

阅读所有内容后，我仍然不确定为什么需要累加器。

((fn r [a b]
    (if (<= a b) 
       (cons a (r (inc a) b)))) 
  2 4)
=> (2 3 4)

.

似乎是一个非常直观的递归解决方案。我唯一改变“真实”代码的内容是使用Lazy-Seq，以便您不会为大型范围堆栈耗尽。

如何到达该解决方案：

当您考虑使用递归时，我发现它有助于尝试并解决您可以思考的最少可能的术语问题，并尝试将“工作”交给递归本身。 特别是，如果您怀疑您可以删除一个或多个参数/变量，这通常是去的方式 - 至少如果您希望代码易于理解和调试;有时，您最终会损害简单，有利于执行速度或减少内存使用情况。 在这种情况下，我想什么时候我开始写作是：“函数的第一个参数也是范围的开始元素，最后一个参数是最后一个元素”。递归思维是你必须训练自己的事情，但是一个相当明显的解决方案是说：范围 [a, b]是元素生成的序列后跟 a的范围。所以可以递归地描述范围。我写的代码几乎是直接实施这个想法。

附录：

我发现，在编写功能代码时，最好避免累计累加器（和索引）。有些问题需要他们，但如果你能找到一种方法来摆脱它们，你通常会更好的话，如果你这样做。

附录2： 关于递归函数和列表/序列， 在编写那种代码时思考的最有用方式是在“列表的第一个项目（头）”中陈述您的问题“列表的其余部分（尾部）”。

Answer 3

我不能增加你收到的已经好的答案，但我会一般回答。当您通过Clojure学习过程时，您可能会发现许多但并非所有解决方案都可以使用Clojure内置的，如地图，也可以在序列方面思考问题。这并不意味着你不应该递归地解决事情，但你会听到 - 而且我认为它是明智的建议 - 即康全递归是为了解决您无法解决的较低水平问题。

我碰巧做了很多.csv文件处理，最近收到了nth创建依赖性的注释。它确实如此，使用地图可以允许我获得元素，以便按名称和不正确进行比较。

我不会丢掉在生产中已经在生产中的两个小型应用程序中使用的clojure-csv解析数据的代码。但是我将在下次以更孤独的方式考虑事情。

很难从谈论vector和nth，loop的书籍中学习。复发等等，然后实现学习clojure从那里向你生长。

我发现的一件事是善于学习克洛库，是社区尊重和乐于助人。毕竟，他们帮助某人在CDC网络与打击卡上的第一次学习语言是Fortran IV，并且其第一个商业编程语言是PL / I.

Answer 4

如果我用累加器解决了这个问题，我会做类似的事情:

user=> (defn my-range [lb up c]
         (if (= lb up)
           c
           (recur (inc lb) up (conj c lb))))
#'user/my-range

然后用它来调用

#(my-range % %2 [])

当然，我会用 letfn 或者不需要的东西 defn 可用。

所以是的，你确实需要一个内部函数来使用累加器方法。

我的思维过程是，一旦我完成了我想要返回的答案将在累加器中。（这与您的解决方案形成鲜明对比，您在查找结束条件方面做了大量工作。）所以我寻找我的结束条件，如果我已经达到它，我返回累加器。否则，我将下一个项目钉在累加器上，并重新出现一个较小的情况。所以只有2件事要弄清楚，结束条件是什么，以及我想放入累加器中的内容。

使用向量有很大帮助，因为 conj 将附加到它，没有必要使用 reverse.

我也在4clojure上, ，顺便说一句。我最近很忙,所以落后了.

Answer 5

看起来你的问题更多关于“如何学习”，然后是一个技术/代码问题。您最终写了那种代码，因为从任何方式或来源都是从您学习的方式或来源，或者特定的Clojure在您的大脑中创造了一个“神经高速公路”，让您以这种特殊方式思考解决方案，并且您最终结束了编写代码像这样。基本上，只要你面临任何问题（在这种特殊情况下递归和/或累积中），您最终使用了“神经高速公路”并始终提出那种代码。

摆脱这种“神经高速公路”的解决方案是为了停止编写代码，让键盘远离并开始阅读很多现有的Clojure代码（从现有的4Clujure问题解决方案到GitHub上的开源项目）并深入地思考它（甚至读取了2-3次函数，真的让它安定在你的大脑中）。这样你最终会摧毁你现有的“神经高速公路”（它产生了现在写的代码），并将创建一个新的“神经高速公路”，它会产生美丽和惯用的Clojure代码。另外，尽快尽快跳转到键入代码，而是给自己一些时间清晰地思考问题和解决方案。