累加器，連接詞和遞歸

Question

我已經解決了4clojure.com中的45個問題，我注意到我試圖用遞歸和累加器來解決一些問題的方式中出現了一個反覆出現的問題。

我會盡力解釋我所做的最好的事情，最終得到一些富有希望的解決方案，希望一些Clojurers能夠「得到」我沒有得到的東西。

例如，問題34要求編寫一個函數（不使用範圍）以兩個整數作爲參數並創建一個範圍（不使用範圍）。簡單地說，你做（... 1 7），你得到（1 2 3 4 5 6）。

現在這個問題不是解決這個問題。

如果我想要使用遞歸和累加器來解決這個問題呢？

我的思維過程是這樣的：

• 我需要編寫一個函數取兩個參數，我開始（FN [XY]）

• 我需要遞歸我需要跟蹤一個列表，我將使用一個累加器，所以我在第一個函數內寫入第二個函數，並採取額外的參數：

  （fn [xy]
  （（FN克[XY ACC] ...） X Ý 「（））

（顯然我不能正確地格式化的Clojure代碼上SO！？）

在這裏，我已經不知道我做的是否正確：第一個功能必須需要兩個整數參數（不是我的調用），我不確定：如果我想使用累加器，可以使用累加器沒有創建嵌套函數？

然後我想連詞，但我不能這樣做：

(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，直到它到達ý

但我結束與怪物上述遞歸。

有一個很多的方式來解決這個問題，再次，這不是我所追求的。

什麼我之後是怎麼回事，之後我決定利弊/連詞，使用蓄能器，以及遞歸，我可以這樣結束了（不是我寫的）：

#(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看到，與蓄能器寫一個函數的一個很好的方式是與兩組不同的參數的函數。這爲您提供了一個非常乾淨的（imho）實現，無需嵌套函數。

---

您還有一些關於序列，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也加入到了右側。我沒有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將被視爲命令）。

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隨後一個的[a + 1, b]範圍的序列。所以範圍確實可以遞歸地描述。我寫的代碼非常直接地實現了這個想法。

編：

我發現，寫功能碼，蓄能器（和索引）時，最好避免。有些問題需要他們，但如果你能找到擺脫他們的方法，那麼你通常會更好。

附錄2：

關於遞歸函數和列表/序列，認爲當寫那種代碼說明你的問題中的第一項」方面最有用的方法（頭）列表「和」列表的其餘部分（尾部）「。

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。

I'm on 4clojure too，順便說一句。我一直很忙，所以我最近落後了。

Answer 4

看起來你的問題更多的是關於「如何學習」，然後是技術/代碼問題。你最終會寫這樣的代碼，因爲無論你通常學習編程的方式或來源如何，或者Clojure都在你的大腦中創建了一個「神經高速公路」，這讓你以這種特殊方式思考解決方案，並最終編寫代碼喜歡這個。基本上，每當遇到任何問題（在這種特殊情況下遞歸和/或累積），您最終都會使用該「神經高速公路」，並始終拿出這種類型的代碼。

擺脫這種「神經高速公路」的解決方案是停止編寫代碼，遠離鍵盤並開始閱讀大量現有的clojure代碼（從4clojure問題的現有解決方案到github上的開源項目）並深入思考（甚至可以讀取一個功能2-3次，以真正讓它安頓在你的大腦中）。這樣你最終會破壞你現有的「神經高速公路」（它產生你現在寫的代碼），並將創建一個新的「神經高速公路」，產生美麗和慣用的Clojure代碼。此外，儘量不要在看到問題時馬上跳到輸入代碼，而是給自己一些時間來思考問題和解決方案。

Answer 5

我無法添加已收到的已經很好的答案，但我會一般回答。當你通過Clojure學習過程時，你可能會發現許多但並非所有的解決方案都可以使用Clojure內置插件來解決，比如地圖，也可以考慮序列方面的問題。這並不意味着你不應該遞歸地解決問題，但是你會聽到 - 而且我相信這是明智的建議 - Clojure遞歸用於解決你無法以另一種方式解決的非常低級別的問題。

我碰巧做了很多.csv文件處理，並且最近收到了一條評論，指出nth創建了依賴關係。它的確如此，並且使用地圖可以讓我獲得用於名稱而不是位置比較的元素。

我不打算在兩個已經在生產中的小應用程序中使用clojure-csv解析數據使用nth的代碼。但我會在下一次更頻繁地考慮事情。

從談論矢量和nth，loop .. recur等等的書籍中學習是很困難的，然後意識到Clojure從那裏開始向前發展。

我發現對學習Clojure很好的事情之一是社區是尊重和樂於助人的。畢竟，他們正在幫助第一個學習語言是Fortran IV的人在CDC Cyber​​上打孔卡，並且他的第一個商業編程語言是PL/I。