関数型プログラミングにおける関数の型の決定

Question

次の方程式はMiranda Syntaxで書かれていますが、MirandaとHaskellの類似点のために、私はHaskellのプログラマが理解するはずです。

次の関数を定義する場合：

rc v g i = g (v:i) 
rn x = x 
rh g = hd (g []) 


f [] y = y 
f (x:xs) y = f xs (rc x y) 

g [] y = y 
g (x:xs) y = g xs (x:y) 

あなたは機能の種類を仕事はどうすればよいですか？私はf、g、rnの仕組みを理解していると思いますが、部分的なアプリケーション部分については混乱しています。

rnがあることを行っている* - > *（か何か - >何でも、私はそれがだと思う - Haskellでは> A？）、fとgの場合

関数型の両方です[*] - > * - > *？

私はrcとrhの型を探す方法には不明です。 rcでは、gは変数iに部分的に適用されているので、これがiの型を制約すると推測しています[*]。 rcの定義に適用されるrcとgの順序は何ですか？ gはiに適用され、結果関数はrcの引数として使用されますか？あるいは、rcはv、g、iの3つの別々のパラメータを取るか？私は本当に混乱しています..どんな助けもありがとう！みんなありがとう。

申し訳ありませんが、そのHDを追加するのを忘れリストのための標準的なヘッド機能であり、以下のように定義されています。型はすでにタイプで知られており、どのように表現が定義で使用されているものから推測される

hd :: [*] -> * 
hd (a:x) = a 
hd [] = error "hd []" 

Answer 1

。

のでrc :: a -> b -> c -> d

rc v g i = g (v : i) 

、の上部に始めましょう、我々はおよそa, b, cとdを知ることができるかを見る必要があります。右側に(v : i)が表示されますので、v :: aではi :: [a],c = [a]と表示されます。その後gはv : iに適用されるので、g :: [a] -> d、完全に、

rc :: a -> ([a] -> d) -> [a] -> d 

rn x = x

が rnの引数の型に制約ませんし、その戻り値の型は、 rn :: a -> a同じであることを意味しています。 rhの引数 gはRHSの空のリストに適用されているので

rh g = hd (g []) 

、それはタイプ[a] -> bを持っている必要があり、おそらくより多くの情報を約aまたはb続きます。実際、g []はRHS上hdのでg [] :: [c]とg :: [a] -> [c]の引数は、最初の引数がリストされ、それが空の場合、結果は、したがって

rh :: ([a] -> [c]) -> c 

、次に

f [] y = y 
f (x:xs) y = f xs (rc x y) 

あります第2引数であるので、最初の式からはf :: [a] -> b -> bが続きます。さて、2番目の式では、RHSでは、fの2番目の引数はrc x yであるため、rc x yのタイプはyでなければなりません。bとなります。しかし、

rc :: a -> ([a] -> d) -> [a] -> d 

、b = [a] -> dです。したがって

f :: [a] -> ([a] -> d) -> [a] -> d 

最後に

g [] y = y 
g (x:xs) y = g xs (x:y) 

我々はg :: [a] -> b -> bを推測最初の方程式から。私たちは、このように

g :: [a] -> [a] -> [a] 

Answer 2

、第二にgの最初の引数と短所、それの頭を取るため、第二から、我々は、b = [a]を推測私は種類を書くためにHaskellの構文を使用するつもりです。その種類はa -> b -> c -> dのようなものになりますので、ここでrc

rc v g i = g (v:i) 

は、3つのパラメータを取ります。 v:iは、vとiと同じタイプの要素のリストである必要があります。したがって、v :: aとi :: [a]の要素のリストである必要があります。 gがそのリストに適用されるので、g :: [a] -> dです。 まとめておけばrc :: a -> ([a] -> d) -> [a] -> dとなります。

あなたはすでにrn :: a -> aを見つけたので、それは単なるIDです。

rhで使用しているhd関数の種類についてはわかりません。その点を省略します。

ここ

f [] y = y 
f (x:xs) y = f xs (rc x y) 

f 2つのパラメータを取りますので、その種類はa -> b -> cのようなものになります。 最初のケースからは、yを返すので、b == cと推測できます。最初の引数はリストです。 今のところ我々はf :: [a'] -> b -> bを知っています。 xとyがrcへの入力に与えられている方法を第二ケース通知に ：（それはfのその2番目の引数として渡されるので、yのものもでなければならないタイプ）y機能[a'] -> d、及びrc x y :: a' -> dでなければなりません。 最後に、f :: [a'] -> ([a'] -> d) -> ([a'] -> d)と言うことができます。 ->は右結合であるため、[a'] -> ([a'] -> d) -> [a'] -> dに相当します。

残りのものについても同様の理由で理由を付けることができます。