recursion - アキュムレータ、conj、および再帰

Question

私は 4clojure.com から 45 の問題を解決しましたが、再帰とアキュムレータを使用していくつかの問題を解決しようとしているときに、繰り返し発生する問題に気付きました。

一部のClojurerが私が得ていないものを「得る」ことを期待して、醜い解決策に終わるために私がしていることをできる限り説明しようとします。

たとえば、問題 34 では、2 つの整数を引数として ( rangeを使用せずに) 関数を作成し、( range を使用せずに) 範囲を作成するよう求めています。簡単に言えば、(... 1 7) を実行すると、(1 2 3 4 5 6) が得られます。

さて、この質問は、この特定の問題を解決することではありません。

再帰とアキュムレータを使用してこれを解決したい場合はどうすればよいですか?

私の思考プロセスは次のようになります。

• (fn [xy] )で始まる、2 つの引数を取る関数を作成する必要があります。

• 再帰する必要があり、リストを追跡する必要があります。アキュムレータを使用するので、追加の引数を取る最初の関数内に 2 番目の関数を記述します。

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

(明らかに、SO で Clojure コードを適切にフォーマットできません!?)

最初の関数は正確に 2 つの整数引数 (私の呼び出しではない) を取る必要があり、確信が持てません: アキュムレータを使用したい場合、作成せずにアキュムレータを使用できますか?ネストされた関数？

次に、 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)

そのため、追加のフラット化を行うことになり、機能しますが、完全に醜いです。

私はいくつかのことを理解し始めており、場合によっては、よりクロジュレスクな方法で「考え」始めていますが、解決策を書くのに問題があります。

たとえば、ここで私は次のように決めました。

• アキュムレータを使用するには
• yに達するまでxをインクリメントして再帰する

しかし、私は上記の怪物になってしまいます。

この問題を解決する方法はたくさんありますが、繰り返しになりますが、それは私が求めているものではありません。

私が求めているのは、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

[注 - 以下に、元に戻す別の方法があります。私は自分の主張をうまく構成できなかった]

2 つ目my-range-1は、とでわかるmy-range-2ように、アキュムレータを使用して関数を記述する良い方法は、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は右に追加しています。conj私は in を使用しなかった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は、2 つのもの (その引数) を含むボックスを作成します。1 つ目はコンテンツで、2 つ目は残りのリストです。リスト(1 2 3)は基本的に(cons 1 (cons 2 (cons 3 nil)))です。対照的に、ベクトル[1 2 3]は配列のように機能します（ただし、ツリーを使用して実装されていると思います）。

conj動作方法は最初の引数に依存するため、少し混乱します。リストの場合、呼び出しconsて左側に追加します。しかし、ベクトルの場合、配列（のようなもの）を右に拡張します。conjまた、既存のシーケンスを最初の引数として取り、追加するものを 2 番目の引数として取りますconsが、逆の場合 (追加するものが最初に来る)に注意してください。

---

上記のコードはすべてhttps://github.com/andrewcooke/clojure-labで入手できます

---

更新:コードがリストを生成する場合に、期待される結果が引用されたリストになるように、テストを書き直しました。 =リストとベクトルを比較し、内容が同じ場合は true を返しますが、明示的にすると、それぞれのケースで実際に取得しているものをより明確に示します。'(0 1 2)前に a'があるのと同じであることに注意してください(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を使用することだけです。

私がその解決策にたどり着いた方法：

再帰を使用することを考えているときは、考えられる限り少ない用語で問題を述べ、再帰自体にできるだけ多くの「作業」を渡そうとすることが役立つと思います。

特に、1つ以上の引数/変数を削除できると思われる場合は、通常、それが最善の方法です。少なくとも、コードを理解しやすくデバッグしやすくしたい場合は、場合によっては、実行速度を優先したり、メモリ使用量を減らしたりするために、単純さを損なうことになります。

この場合、書き始めたときに思ったのは、「関数の最初の引数は範囲の開始要素でもあり、最後の引数は最後の要素です」ということでした。再帰的思考は、自分で行うように訓練する必要があるものですが、かなり明白な解決策は、次のように言うことです。範囲は、要素で始まり、範囲が 続くシーケンスです。したがって、範囲は実際に再帰的に記述できます。私が書いたコードは、そのアイデアを直接実装したものです。[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ます。

そうです、アキュムレータアプローチを使用するには内部関数が必要です。

私の思考プロセスは、私が終わったら、私が返したい答えはアキュムレータにあるということです。（これは、終了条件を見つけるために多くの作業を行うソリューションとは対照的です。）そこで、終了条件を探し、それに達した場合は、アキュムレータを返します。それ以外の場合は、アキュムレータの次の項目に追加して、小さいケースで繰り返します。したがって、理解する必要があるのは、最終条件とは何か、そしてアキュムレータに入れたいものは2つだけです。

conjベクトルを使用すると、ベクトルが追加され、を使用する必要がないため、非常に役立ちますreverse。

私も4clojureにいます、ところで。忙しいので最近遅れてしまいました。

Answer 4

あなたが受け取ったすでに良い回答に追加することはできませんが、一般的に回答します。Clojure の学習プロセスを進めていくと、map などの Clojure 組み込みを使用したり、シーケンスの観点から問題を考えたりすることで、すべてではないが多くの解決策を解決できることに気付くかもしれません。これは、物事を再帰的に解決してはならないという意味ではありませんが、Clojure の再帰は、他の方法では解決できない非常に低レベルの問題を解決するためのものであるということを聞くでしょう (賢明なアドバイスだと思います)。

私はたまたま多くの .csv ファイル処理を行っており、最近、nth が依存関係を作成するというコメントを受け取りました。マップを使用すると、位置ではなく名前で比較する要素を取得できます。

すでに実稼働している 2 つの小さなアプリケーションで、clojure-csv で解析されたデータで nth を使用するコードを破棄するつもりはありません。でも次はもっと順番に考えていこうと思います。

ベクトルや nth、ループ .. recur などについて説明している本から学び、Clojure を学ぶことでそこから成長することに気付くのは難しいことです。

Clojure を学んで良かったと思うことの 1 つは、コミュニティが敬意を払って助けてくれることです。結局のところ、彼らは、パンチカードを備えた CDC Cyber​​ の Fortran IV を最初に学習した言語であり、最初の商用プログラミング言語が PL/I であった人を支援しているのです。

Answer 5

あなたの質問は、技術/コードの問題ではなく、「学習方法」に関するものであるようです。そのようなコードを書くことになるのは、プログラミング全般や具体的には Clojure を学んだ方法やソースが何であれ、脳内に「ニューラル ハイウェイ」が作成され、この特定の方法で解決策を考えさせられ、最終的にコードを書くことになるからです。このような。基本的に、問題 (この特定のケースでは再帰および/または蓄積) に直面するたびに、その「ニューラルハイウェイ」を使用することになり、常にその種のコードを考え出します。

この「ニューラルハイウェイ」を取り除くための解決策は、コードを書くのを当面やめて、そのキーボードを遠ざけて、既存の clojure コードをたくさん読み始めることです (4clojure 問題の既存の解決策から github のオープンソースプロジェクトまで)。深く（関数を2〜3回読んで、実際に脳に定着させます）。この方法では、既存の「ニューラル ハイウェイ」(現在記述しているコードを生成する) が破棄され、美しく慣用的な Clojure コードを生成する新しい「ニューラル ハイウェイ」が作成されます。また、問題を見つけてすぐにコードを入力するのではなく、問題と解決策について明確かつ深く考える時間をとってください。