6

次の関数定義が与えられ、すべての正の整数に対して同様の定義があると仮定すると、整数を表す 2 つの関数を引数として取り、2 つの入力整数の和を表す関数を返す plus という関数の型定義とコードが得られます。たとえば(plus one two)、2 つの引数を取りf x、 を返す関数に評価する必要があります(f(f(f x)))。

one f x = f x
two f x = f (f x)
three f x = f (f (f x)))

等

私は関数型プログラミングが初めてで、これについて頭を悩ませることができません。まず、すべての正の整数の関数を書き出さずに定義する方法がわかりません (これは明らかに不可能です)。のように、 がある場合plus(sixty, forty)、60 が f に 60 回適用されることを関数がどのように認識できxますか?

私はこれを Miranda で書くことを意図していますが、私は Haskell の方が詳しいので、どちらのヘルプも大歓迎です。

4

3 に答える 3

9

等式推論1と抽象化を適用します。あなたが持っている

one   f x =       f x                       -- :: (a -> b) -> a -> b
two   f x =    f (f x)   -- = f (one f x)   -- :: (a -> a) -> a -> a
three f x = f (f (f x))  -- = f (two f x)   -- :: (a -> a) -> a -> a
--                            ~~~~~~~~~~~

したがって、後続関数nextが自然に定義されるため、three = next two. はい、上の式のnext two代わりに書くのと同じくらい簡単です。three

next :: ((b -> c) -> a -> b) -> (b -> c) -> a -> c
-- three f x = next two f x = f (two f x)   -- `two` is a formal parameter
--                            ~~~~~~~~~~~
next                num f x = f (num f x)   -- generic name `num`

zero :: t -> a -> a
zero f x = x

これは、継承のパターンをキャプチャします。後続関数として、およびゼロ値としてf使用されます。残りは次のとおりです。例えば、x

plus :: (t -> b -> c) -> (t -> a -> b) -> t -> a -> c
plus two one f x = two f (one f x)   -- formal parameters two, one
              -- = f (f (one f x))   -- an example substitution
              -- = f (f (f x)        --   uses the global definitions
              -- = three f x         --   for one, two, three

つまり、 (「通常の」の代わりに)one f xによってゼロ値として使用されるため、 を表します。「数」はn回の操作の連続を表します。twoxthreen +1

上記でも、 と は 2 つの正式な関数パラメーターにすぎないため、実際には一般的な操作を定義していますplus。twoone

Prelude> plus three two succ 0    -- built-in `succ :: Enum a => a -> a`
5
Prelude> :t plus three two
plus three two :: (a -> a) -> a -> a
Prelude> plus three two (1:) [0]
[1,1,1,1,1,0]

ここで重要なことは、関数は呼び出されたときに値を生成するオブジェクトであるということです。それ自体は不透明なオブジェクトです。それに適用する「オブザーバー」引数は、ゼロであることの「意味」を提供するか、後続の値を見つけることを意味し、数値の値を観察したときにどのような結果が生成されるかを定義します。

1つまり、任意の式で LHS を定義の RHS に、または RHS を LHS に自由に置き換えます (もちろん、既存の自由変数をキャプチャ/シャドーしないように、変数の名前を変更するまで)。

于 2014-03-07T10:33:23.960 に答える
5

数値を数値に変換するには、次のようなものを使用できます。

type Numeral = forall a . (a -> a) -> (a -> a)

toChurch :: Int -> Numeral
toChurch 0 _ x = x
toChurch n f x = f $ toChurch (pred n) f x

fromChurch :: Numeral -> Int
fromChurch numeral = numeral succ 0
于 2014-03-07T10:20:29.770 に答える
1

関数が何回呼び出しているかを認識する必要はありませんf。たとえばsucc、教会の数字に 1 を追加する を実装するには、次のようにします。

succ n f x = f (n f x)

次に、最初に必要な回数だけn適用し、最後に自分で行います。逆に、最初に自分で一度適用してから、残りを行うこともできます.fffn

succ n f x = n f (f x)

同様の手法を使用して を実装できますplus。

于 2014-03-07T10:09:53.743 に答える