固定小数点コンビネーター

Func<Func<T,T>,T>



の形式の関数がフォームのdefault (T)



構造を使用せずに存在できるかどうかを最初に尋ねられたときdefault (T)



それは深い認知的不協和音に突入しました。

値を取得する場所のない関数はどのようにできますか? 明らかなオプションについて
T Fix<T>(Func<T,T> func){

return func(Fix(func));

}




私も考えることができませんでした。 そのような機能を実行することは可能ですか? それは無限に呼び出され、結果を与えません。 C#のような言語では、そのような構造は実際にループを引き起こしますが、PythonやHaskellのような言語ではうまく機能するかもしれません。 Haskellのコードが少しありますが、構文がだいたい誰にでも明確になることを願っています。

最も簡単な例:
fix f = f( fix f)

const42 x = 42

print (fix const42) -- , ?




呼び出しを展開すると、次の一連の計算が行われることがわかります。
fix const42 -> const42 ( fix const42) -> 42



最後の遷移は、関数の値を計算するために関数の引数を必要としないという事実により発生します。

問題は、関数がその引数に依存する場合、計算が停止しない場合、次に何をすべきかということです。

停止しないでください。 値が使用されない場合、Haskellの遅延のおかげで計算されません。
:リストの先頭にアイテムを追加する機能です。 例: 1:[2,3] = [1,2,3], n:[] = [n]





fix (1:)



関数を検討してください。 明らかに無限になりますが、まだ使用できるリストを返します。
take 3 (fix (1:)) -> take 3 (1:fix (1:)) -> 1:take 2 (fix (1:)) -> 1:(1:take 1 (fix (1:)))

-> 1:(1:(1:take 0 (fix (1:)))) -> 1:(1:(1:[])) -> 1:(1:[1]) -> 1:[1,1] -> [1,1,1]




そのため、パラメーターを使用する関数から結果を取得しました。 便利なものまで作成しました。

repeat n = fix (n:)



-1つの繰り返し要素の無限リストを生成します。

無限は悪ではありません。主なことは、どこかで、とにかく、内部または外部で、計算の連鎖が壊れることです。 どのようなデザインがチェーンを壊すことができますか?

ここまでは、修正のための関数型が重要な型であると想定していました。 しかし、なぜ高階関数を使い始めないのでしょうか? 伝統的な例を試してみましょう:
factCore f = \x -> if x == 0 then 1 else x * f (x-1)



それから、 fix factCore



関数は通常の階乗になります。 実際、毎回、f関数の代わりにfactfact関数が置き換えられます。そのため、すべてが通常の再帰と非常によく似たものになります。



もっと複雑なものを試してみましょう。 たとえば、1〜nの数字で構成される長さkのすべてのシーケンスを作成して、2つの隣接する同一の数字がないようにします。 タスクは指から吸い出されますが、それでもなお。
allDiffCore nf = \k cond -> if k == 1 then map (\x->[x]) $ filter cond [1..n] else concat $ map (\x -> map (x:) (f (k-1) (/=x)) ) ( filter cond [1..n])

sequences nk = fix (allDiffCore n) k (\x->True)




少し説明:
filter



条件とリストの2つのパラメーターを受け取る関数。 条件を満たすオブジェクトのリストを返します。

/=



-通常の「等しくない」。 これは非常に数学的な表記です。

concat



は、リストのリストを単一のリストに結合する関数です。
各ステップで、いくつかの適切な要素を取得し、次の要素が適切かどうかを決定する関数を定義します。 このテンプレートを使用すると、多くの異なるシーケンスを生成できます。 たとえば、増え続けるシーケンスを取得するには、フィルタリング機能を担当する部分を変更するだけで十分です。つまり、(/ = x)を(> x)に置き換えます。



そして今、タスクは考えることです:サイズn * nのチェス盤でクイーンの問題を解決する関数をどのように書くか?

既にお気づきのように、修正関数(固定小数点コンビネーターの特殊なケースです)を使用すると、関数での直接的な再帰が回避されます。これは、通常の再帰はそこでは使用できないため、たとえば、ラムダ計算で役立ちます。



おまけとして、c#に対して、特定の強力に切り捨てられた固定小数点コンビネータをお勧めします。
public static Func<T1, T2> Fix<T1, T2>(Func<Func<T1, T2>, Func<T1, T2>> f)

{

// ,

// .


return f(x => Fix(f)(x));

}




さらに使用:
var fact = Fix< int , int >(self => x =>

{

if (x == 0)

return 1;

return x * self(x - 1);

});

var result = fact(5); // 120







All Articles