13

編集：これを書いている過程で自分の質問に対する部分的な答えを発見しましたが、簡単に改善できると思うので、とにかく投稿します。多分そこにもっと良い解決策がありますか？

letに頼らずにフォームで再帰関数を定義する簡単な方法を探していますletfn。letこれはおそらく不合理な要求ですが、私がこの手法を探している理由は、多くのネストされたandletfnステートメントを必要とする方法で相互に依存するデータと再帰関数が混在しているためです。

次のような遅延シーケンスを生成する再帰関数を書きたいと思いました (例としてフィボナッチ数列を使用)。

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

fibsしかし、バインド中に独自のシンボルを使用できないのは clojure のようです。それを回避する明白な方法はletfn

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

しかし、前に述べたように、これは多くの厄介なネストと交互のletandにつながりletfnます。

letfnだけを使用せずにこれを行うためにlet、U-combinator と思われるものを使用するものを作成することから始めました (今日その概念について聞いたばかりです)。

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

しかし、どのように冗長性を取り除くの(fi fi)ですか?

この時点で、コンビネータ Q に 1 時間も苦労して少しずつビットを追加した後、自分の質問に対する答えを発見しました。

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

Q再帰シーケンスを定義するために使用しているこのコンビネータは何と呼ばれていますか? 引数のない Y コンビネータのように見えますx。それは同じですか？

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

YまたはQの機能を提供するclojure.coreまたはclojure.contribの別の機能はありますか? 私がしたことが慣用的だったとは想像できません...

4

2 に答える 2

11

レトレック

私はletrec最近、Clojure 用のマクロを作成しました。ここに Gist があります。これは、Scheme のように動作します (たまたまそれを知っている場合)。これは、とletrecの間のクロスであることを意味します: 名前のセットを相互に再帰的な値にバインドできます。それらの値を関数にする必要はありません (遅延シーケンスも問題ありません)。他の項目を参照せずに各項目のヘッドを評価できる限り (これは Haskell またはおそらく型理論の用語です。ここでの「ヘッド」は、たとえば遅延シーケンス オブジェクト自体を表す場合があります。 ! -- 強制は含まれません)。letletfn

あなたはそれを使って次のようなものを書くことができます

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

これは通常、トップレベルでのみ可能です。その他の例については、Gist を参照してください。

質問のテキストで指摘されているように、上記は次のように置き換えることができます

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

指数時間で同じ結果が得られます。バージョンのletrec複雑さは線形です (トップレベルの(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))フォームと同様)。

繰り返す

自己再帰的な seq は、多くの場合、次のように構築できますiterate。つまり、指定された要素を計算するのに固定範囲の後読みで十分な場合です。で計算するclojure.contrib.lazy-seqs方法の例については、を参照してください。fibsiterate

clojure.contrib.seq

c.c.seqと呼ばれる興味深い機能を提供し、次のrec-seqようなことを可能にします

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

単一の自己再帰シーケンスの構築のみを許可するという制限がありますが、より多様なシナリオを可能にするいくつかの実装アイデアをそのソースから持ち上げることは可能かもしれません。トップレベルで定義されていない単一の自己再帰シーケンスが求められている場合、これは慣用的な解決策でなければなりません。

コンビネータ

質問文に表示されているようなコンビネーターに関しては、JVM での TCO (末尾呼び出しの最適化) の欠如によって妨げられていることに注意することが重要です (したがって、Clojure では、JVM の呼び出し規約を直接使用することを選択します)。最高のパフォーマンス）。

トップレベル

相互に再帰的な「もの」を最上位、おそらく独自の名前空間に配置するオプションもあります。これらの「もの」を何らかの方法でパラメータ化する必要がある場合、これはうまく機能しませんが、必要に応じて名前空間を動的に作成できます (clojure.contrib.with-ns実装のアイデアについては、を参照してください)。

最終コメント

私は、letrecこれが慣用的な Clojure とはかけ離れていることをすぐに認めます。また、他に何かできることがあれば、プロダクション コードで使用することは避けたいと思います (そして、常にトップ レベルのオプションがあるため...)。ただし、(IMO!) で遊ぶのは素晴らしく、十分に機能するようです。私は個人的に、マクロなしletrecでどれだけ達成できるか、そしてマクロがどの程度letrec物事をより簡単/きれいにするかを見つけることに興味があります.私はまだそれについて意見を述べていません. それで、ここにあります。繰り返しになりますが、単一の自己再帰 seq の場合、iterateまたは contrib が最善の方法かもしれません。

于 2010-07-30T19:01:27.077 に答える
8

fnその名前が本体の関数にバインドされたオプションの name 引数を取ります。この機能を使用すると、次のように記述できますfibs。

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))
于 2010-08-01T01:53:38.767 に答える