13

我已经从 4clojure.com 解决了 45 个问题，并且在尝试使用递归和累加器解决一些问题的过程中发现了一个反复出现的问题。

我将尽我所能解释我正在做的最好的事情，以最终得到令人毛骨悚然的解决方案，希望一些 Clojurers 会“得到”我没有得到的东西。

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

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

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

我的思考过程是这样的：

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

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

    (fn [xy]
    ((fn g [xy 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)

所以我最终做了一个额外的展平，它可以工作，但它非常难看。

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

例如在这里我决定：

  • 使用蓄能器
  • 通过递增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)

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

4

5 回答 5

9

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

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

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

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

但在你的情况下，这很重要。您将向后获取列表：

(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 鼓励您使用其他序列。与 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是添加到右边。我没用conjin 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在“自然”位置添加新元素。对于右侧的向量，但对于左侧的列表。

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

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

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

update: i rewrote the tests so that the expected result is a quoted list in the cases where the code generates a list. = will compare lists and vectors and return true if the content is the same, but making it explicit shows more clearly what you're actually getting in each case. note that '(0 1 2) with a ' in front is just like (list 0 1 2) - the ' stops the list from being evaluated (without it, 0 would be treated as a command).

于 2012-05-19T17:19:17.350 回答
5

阅读完所有内容后，我仍然不确定您为什么需要蓄能器。

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

关于递归函数和列表/序列，编写此类代码时最有用的思考方式是用“列表的第一项（头）”和“列表的其余部分（尾）”来说明您的问题.

于 2012-05-19T15:07:56.750 回答
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。我最近很忙，所以我落后了。

于 2012-05-19T16:36:41.537 回答
3

我无法添加您已经收到的已经很好的答案，但我会回答一般。在学习 Clojure 的过程中，您可能会发现使用 Clojure 内置函数可以解决许多但并非所有解决方案，例如 map 以及根据序列考虑问题。这并不意味着您不应该递归地解决问题，但是您会听到——我相信这是明智的建议——Clojure 递归是用于解决您无法以其他方式解决的非常低级的问题。

我碰巧做了很多 .csv 文件处理，最近收到一条评论说 nth 创建依赖项。确实如此，并且使用地图可以让我通过名称而不是位置来比较元素。

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

很难从谈论向量和 nth、loop .. recur 等的书籍中学习，然后意识到学习 Clojure 会让你从那里成长。

我发现学习 Clojure 的好处之一是社区相互尊重且乐于助人。毕竟，他们正在帮助那些在 CDC Cyber​​ 上使用打孔卡学习的第一门语言是 Fortran IV，而他的第一门商业编程语言是 PL/I 的人。

于 2012-05-19T17:11:22.940 回答
1

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

摆脱这条“神经高速公路”的解决方案是暂时停止编写代码，远离那个键盘，开始阅读大量现有的 clojure 代码（从 4clojure 问题的现有解决方案到 github 上的开源项目）并思考深入了解（甚至阅读一个函数 2-3 次才能真正让它在你的大脑中安定下来）。这样一来，您最终会破坏现有的“神经高速公路”（生成您现在编写的代码），并创建一条新的“神经高速公路”，以生成漂亮且惯用的 Clojure 代码。另外，尽量不要一看到问题就跳到输入代码，而是给自己一些时间来清晰而深入地思考问题和解决方案。

于 2012-05-19T16:48:36.770 回答