累加器，conj和递归

Question

我已经解决了4clojure.com上的45个问题，并注意到在使用递归和累加器解决某些问题时，我尝试解决的一种重复性问题。

我会尽力解释我正在做什么，以便最终得到丑陋的解决方案，希望一些Clojurers能够“理解”我没有理解的东西。

例如，问题34要求编写一个函数（不使用range），将两个整数作为参数并创建一个范围（不使用range）。简单地说，您可以执行(... 1 7)，然后获得（1 2 3 4 5 6）。

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

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

我的思考过程如下：

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

• 我需要递归，并且需要跟踪一个列表，我将使用累加器，因此我在第一个函数内部编写了第二个函数，它需要一个额外的参数：

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

（显然我无法在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)

所以我最后加了一个flatten，它能工作但是非常丑陋。

我开始理解一些东西，甚至在某些情况下开始以更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)

我知道解决一些问题是一个开始，但我有点失望，因为我往往会产生丑陋的解决方案...

- Cedric Martin

---

不要害怕放弃不好的解决方案。如果你开始发现你的代码变得难以控制，那就退一步思考一下。当它感觉不对时，很可能就是不对的。 - Jeremy

@JeremyHeiler：好吧，但这个“想法”并不那么糟糕，而是“实现”/实际代码糟糕。例如，使用累加器+递归的简短解决方案是由解决了150个4clojure问题（其中一些确实不是微不足道的）的人编写的。所以我的想法似乎并不那么糟糕：但我还不能（清晰地）实现我的想法。我想这需要一些时间才能让拼图落入正确的位置 :-/ - Cedric Martin

当然可以。只要继续练习并且多写代码就好了！ - Jeremy

我对这些点赞和收藏有些惊讶：当尝试学习Clojure（或任何Lisp方言）时，我可能不是唯一面临同类问题的人。 - Cedric Martin

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有些混乱，但也很有用。上面我给出了基于 cons 的传统观点。但是Clojure鼓励您使用其他序列。并且与cons列表不同，向量从右侧增长，而不是左侧。因此，另一种反转结果的方法是使用向量：

(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 是添加在右侧。我没有在 my-range-1 中使用 conj，因此这里重新编写以更清晰明了：

(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将被视为命令）。

- andrew cooke

---

+1，非常好的答案（其他答案也很好）。我需要一些时间来消化这些内容，但其中一些已经让我有了新的认识 ：） - Cedric Martin

Answer 2

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

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

似乎这是一个相当直观的递归解决方案。唯一要更改的是在“真正”的代码中使用懒惰序列，以便于对于较大范围不会用尽堆栈。

找到这个解决方案的过程如下: 当你考虑使用递归时，我发现它有助于尝试用你能想到的最少的术语来陈述问题，并尝试将尽可能多的“工作”交给递归本身处理。特别是，如果你怀疑可以省去一个或多个参数/变量，通常就是这样做的——至少如果你希望代码易于理解和调试的话；有时为了执行速度或减少内存使用而牺牲简单性。在这种情况下，我开始写代码时所想的是:“函数的第一个参数也是范围的起始元素，最后一个参数是最后一个元素。”递归思维是你必须训练自己去做的一件事情，但一个非常明显的解决方案是说:一个范围 [a,b]是以元素a开头的序列，后面是范围[a+1,b]。因此，范围确实可以通过递归来描述。我编写的代码基本上是该想法的直接实现。

附注：我发现在编写函数式代码时，最好避免使用累加器（和索引）。有些问题需要它们，但是如果你能找到摆脱它们的方法，那么你通常会更好。

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

- Joost Diepenmaat

---

好的，那很棒，但你能解释一下在决定使用递归后，你是如何写出来的吗？请注意，另一种解决方案（使用累加器）是由一个解决了150个4clojure问题（其中一些更难）的人编写的，因此使用累加器并不是那么牵强附会 : ) - Cedric Martin

Answer 3

如果我要使用累加器来解决这个问题，我会这样做：

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的问题。

因此，您确实需要一个内部函数来使用累加器方法。

我的思维过程是，一旦完成，我要返回的答案将在累加器中。 （与您的解决方案相反，在那里您需要找到结束条件并进行大量工作。）因此，我寻找我的结束条件，如果我已经达到它，我就返回累加器。否则，我将下一个项目附加到累加器上，并为更小的情况进行递归。因此，只有两件事要弄清楚，即结束条件是什么以及我想把什么放在累加器中。

使用向量会很有帮助，因为conj将附加到它，无需使用reverse。

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

- Nathan Hughes

---

+1... 并在 4clojure 上获得不错的 "分数" : ) 我将发布一个关于 "内部函数" vs "不同参数集" 的新问题。 - Cedric Martin

Answer 4

我无法提供比你已经收到的好答案更多的信息，但我会给出一般性的回答。在学习Clojure的过程中，你可能会发现许多但不是所有的问题都可以使用Clojure内置函数来解决，例如map以及将问题转化为序列。这并不意味着你不应该使用递归来解决问题，但你会听到 - 我认为这是明智的建议 - Clojure递归用于解决你无法用其他方法解决的非常基本的问题。

我碰巧做了很多.csv文件处理，并最近收到了一个评论，称nth会创建依赖关系。它确实会，使用maps可以让我通过名称而不是位置来比较元素。

我不会放弃已经在两个小型应用程序中使用clojure-csv解析数据的使用nth的代码。但下次我会以更顺序的方式思考问题。

从介绍向量、nth、loop..recur等方面学习Clojure很困难，然后意识到学习Clojure会让你向前发展。

我发现学习Clojure的好处之一是社区尊重和乐于助人。毕竟，他们正在帮助一个首次学习语言是Fortran IV，并且第一个商业编程语言是PL/I的人。

- octopusgrabbus

Answer 5

看起来你的问题更多是关于“如何学习”而不是技术/代码问题。你最终会写出那种代码，是因为你从任何一种方式或来源中学习了编程或Clojure，这在你的大脑中创建了一个“神经高速公路”，使你以这种特定的方式思考解决方案，最终你就会写出这样的代码。基本上，每当你面临任何问题（在这种情况下是递归和/或累积），你都会使用那个“神经高速公路”，并且总是想出那种代码。

摆脱这个“神经高速公路”的解决方案是暂停编写代码，把键盘放开，开始阅读大量现有的Clojure代码（从4clojure问题的现有解决方案到GitHub上的开源项目），并深入思考它（甚至要读2-3次函数才能真正让它在你的大脑中沉淀下来）。这样，你将摧毁现有的“神经高速公路”（产生你现在编写的代码），并创建一个新的“神经高速公路”，可以生成美丽和惯用的Clojure代码。此外，尝试不要立即开始输入代码，而是给自己一些时间清晰深入地思考问题和解决方案。

- Ankur

---

这很有趣，但实际上我认为缺乏任何“Lisp神经高速公路”使我编写这样的代码：我有点“看到”我想要的解决方案的样子（我的想法基本上与解决了所有150个问题的用户的想法相同），但是...我开始在REPL上玩耍，最终得到错误的解决方案，但随后意识到我“知道”一个（超级糟糕的）方法来解决我的问题。例如，我最终得到(1 (2 (3 4)))并认为：“啊，我只需将其展平即可”。当然这是垃圾 :( - Cedric Martin

嗯...你的解决方案最终导致了另一个问题（嵌套列表），然后你解决了这个新问题，希望最终得到所需的解决方案，如果不行的话，那么你就要解决新产生的问题:) 最后你设法解决了原始问题，但是中间问题使得你的代码变得复杂。看起来你一直在解决问题，而没有回头“查看整个问题”，而是继续采用某种暴力方法。 - Ankur

-1 ... 那恰好是我的问题。我明确表示我理解问题，我知道解决它所需要的一切，但实现起来会有问题。你一直在重复我写的话，只是为了强调我“不懂”。抱歉，你的回答没有建设性。显然你不愿意在这里提供帮助：你唯一想做的就是重申：“我不明白”。而你在评论中又再次这样做： -1。 - Cedric Martin