アキュムレータ、conj、再帰

StackOverflow https://stackoverflow.com//questions/10666228

質問

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

私が得ていないものを一部の Clojurers が「理解」してくれることを期待して、私が最終的には不完全な解決策を得るために何をしているのかをできる限り説明しようとします。

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

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

もし私が 欲しい 再帰とアキュムレータを使用してこれを解決するには?

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

  • 2 つの引数を取る関数を書く必要があります。まず、 (fn [x y] )

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

    （fn [xy
    （（fn g [xy acc] ...）x y '（））

(どうやら、SO ではその Clojure コードを適切にフォーマットできないようです!?)

ここで、私はそれが正しく行われているかどうかすでに確信がありません。最初の関数 しなければならない 正確に 2 つの整数引数を取ります (私の呼び出しではありません) が、よくわかりません。アキュムレータを使用したい場合、入れ子関数を作成せずにアキュムレータを使用できますか?

それから私はしたいです コンジ, 、しかし私はできません:

(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

しかし、私は上記の怪物に行き着きます。

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

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

いくつかの問題を解決できるようになるのは始まりだと思いますが、私が生み出す傾向のある醜い解決策には少しがっかりしています...

役に立ちましたか？

解決

ここで学ぶべきことがいくつかあると思います。

初め, 、一種の一般規則 - 再帰関数には通常、自然な順序があり、アキュムレータを追加するとその順序が逆転します。それは「通常」（それなし アキュムレータ) 再帰関数が実行され、値を計算する作業が行われ、その後再帰的にリストの末尾が生成され、最終的には空のリストで終了します。対照的に、アキュムレータでは、空のリストから始めて、先頭に内容を追加します。リストは増加していきます。 反対方向に.

したがって、通常、アキュムレータを追加すると、順序が逆になります。

今では、これは重要ではないことがよくあります。たとえば、シーケンスではなく、 可換 演算子 (加算や乗算など)。どちらの方法でも同じ答えが得られます。

しかしあなたの場合、それが重要になります。リストを逆方向に取得します。

(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 つの異なる引数セットを持つ関数として記述することです。これにより、ネストされた関数を必要とせずに、非常にクリーンな (個人的な) 実装が得られます。

また、シーケンスに関するより一般的な質問もあります。 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 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) とともに ' 目の前はまるで (list 0 1 2) - ' リストの評価を停止します (それがなければ、 0 コマンドとして扱われます)。

他のヒント

それを読んだ後はまだ蓄電池が必要な理由はわかりません。 

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

はかなり直感的な再帰的解決策のようです。私が "本物の"コードで変わる唯一のことは、lazy-seqを使うことですので、大幅な範囲でスタックがなくなりません。

私はその解決策にどのように着いたか：

再帰を使っていることを考えているとき、私はそれが考えることができる可能性のある条件で問題を試してみるのに役立ち、再帰自体に多くの「仕事」を身につけるようにしてください。

特に、あなたが1つ以上の引数/変数を落とすことができるならば、それは通常行く方法です - 少なくともコードが理解してデバッグすることができます。時々、実行速度を支持する、またはメモリ使用量の削減に伴い、シンプルさが損なわれることがなくなります。

この場合、私が書き始めたときに私が考えたのは： "関数の最初の引数も範囲のstart要素であり、最後の引数は最後の要素です"です。再帰的な思考はあなたができるようなものです。しかし、かなり明白な解決策は、次のように言うことです。 [a, b]の範囲。だから範囲は実際に再帰的に説明され得る。私が書いたコードはその考えの直接的な実装です。

補遺：

機能コードを書くときは、アキュムレータ（およびインデックス）が避けられることを発見しました。いくつかの問題はそれらを必要としていますが、あなたがそれらを取り除く方法を見つけることができるならば、あなたは通常あなたがそうするならば、あなたはより良いです。

補遺2：

再帰関数とリスト/シーケンスに関しては、そのようなコードを書くときに考えるための最も便利な方法は、「リストの最初の項目（頭）」という点で問題を述べることです。 「リストの残りの部分（尾）」

私はあなたが受け取ったすでに良い答えに追加することはできませんが、一般的に答えます。 Clojure Learningプロセスを経験すると、マップのように、すべての解決策を使用して、すべてのソリューションを使用して解決できるが、すべてのソリューションをマップのように解決できることがわかります。これはあなたが再帰的に物事を解決しないでください、しかしあなたは聞くでしょう - そして私はそれが賢明なアドバイスであると信じています - Clojureの再帰は非常に低いレベルの問題を解決するためのものですあなたは別の方法を解決することはできません。

私は、多くの.csvファイル処理を行い、最近Nthが依存関係を生み出すコメントを受け取りました。それは行い、地図の使用を許可することができ、名前ではなく名前で比較の要素に取得することができます。

すでに製造中に2つの小さなアプリケーションでClojure-CSV解析データを使用してNTHを使用するコードを捨てません。しかし、私は次回の順序付け方法で物事について考えるつもりです。

ベクトルとNTH、ループ、レチュールなどについて話す本から学ぶことは困難であり、それから学習CLOJUREがそこから前進することを実現しています。

Clojureを学ぶことについて良いことの一つは、コミュニティは尊重して役に立つことです。結局のところ、彼らは最初の学習言語がパンチカードを備えたCDCサイバー上のFortran IVである人を助け、最初の商業計画言語がPL / Iです。

私がアキュムレータを使ってこれを解決した場合私は次のようなことをします： 

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も、BTW。私は忙しかったので最近倒れました。

あなたの質問は「学ぶ方法」についてのより多くの問題のように見えます。あなたが一般的な、または特定の方法で解決策を考えてきて、あなたがこの特定の方法で解決策について考えてきた、あなたがあなたの脳内の「ニューラルハイウェイ」を作成したとしても、あなたが脳の中の「ニューラルハイウェイ」を作成したので、あなたはそのようなコードを書いています。このような。基本的にあなたが問題に直面するときはいつでも（この特定のケースの再帰や蓄積の中で）あなたはその "ニュラリア高速道路"を使って常にそのようなコードを思いついています。

この「ニュラリア高速道路」を取り除くための解決策は、瞬間のコードの書き込みを停止し、そのキーボードを遠ざけ、既存のCLOJUREコードの多くを読み取り、既存のCLOJUREコードの読み込みを開始することです（4Clojure問題の既存のソリューションからGitHub上のオープンソースプロジェクトへ）。そしてそれについて考えてみると（本当にそれをあなたの脳の中で落ち着かせるために2~3回読んでも）。このようにして、あなたは既存の「ニュラリア高速道路」（今すぐ書くコードを作成する）を破壊し、美しく慣用のClojureコードを作成する新しい「ニューラルハイウェイ」を作成します。また、問題を見たとすぐにコード入力にジャンプしないようにしてください。むしろ、問題や解決策について明確かつ深く考えるのに時間をかけてください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top