确定函数式编程中函数的类型

Question

以下等式是用Miranda语法编写的，但由于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>一个）

对于f和g，是函数类型都[*] - > * - > *？

我不确定如何处理寻找rc和rh的类型。在rc中，g被部分应用于变量i - 所以我猜测这限制了我的类型[*]。 rc和g在rc的定义中应用了什么顺序？ g是否应用于i，然后将得到的函数用作rc的参数？还是rc需要3个独立的v，g和i参数？我真的很困惑..任何帮助将不胜感激！多谢你们。

对不起忘了补充一点，HD是列表的标准头功能，并定义为：

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

Answer 1

类型是从什么是已知的类型和表现形式是如何在定义中使用的推断。

让我们开始在顶部，

rc v g i = g (v : i) 

所以rc :: a -> b -> c -> d，我们必须看看有什么可以发现关于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 = hd (g []) 

由于rh的说法g被施加到在RHS空列表，它必须有类型[a] -> b，可能更多的信息有关a或b如下。事实上，g []是hd在RHS，所以g [] :: [c]和g :: [a] -> [c]的说法，因此

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

下一页

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

第一个参数是一个列表，如果是空的，结果是第二个参数，所以f :: [a] -> b -> b从第一个方程得出。现在，在第二个方程中，在RHS上，f的第二个参数是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。从第二个，我们推断b = [a]，因为我们采取g的第一个参数和缺点它的第二个头部，从而

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

Answer 2

我要使用Haskell语法来写的类型。

rc v g i = g (v:i) 

这里rc有三个参数，所以它的类型将会像a -> b -> c -> d。 v:i必须是与v和i相同类型的元素列表，因此v :: a和i :: [a]。 g应用于该列表，以便g :: [a] -> d。 如果你把所有的东西放在一起，你会得到rc :: a -> ([a] -> d) -> [a] -> d。

正如你已经想出rn :: a -> a，因为它只是身份。

我不知道您在rh中使用的hd函数的类型，所以我会跳过它。

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

这里f有两个参数，所以它的类型将会像a -> b -> c。 从第一种情况我们可以推断出b == c，因为我们返回y，并且第一个参数是一个列表。 现在我们知道f :: [a'] -> b -> b。 在第二种情况下通知如何x和y在输入给予rc：y必须是一个函数[a'] -> d，和rc x y :: a' -> d（即必须也y的类型，因为它是作为它的f秒参数传递）。 最后，我们可以说f :: [a'] -> ([a'] -> d) -> ([a'] -> d)。由于->是正确关联的，因此相当于[a'] -> ([a'] -> d) -> [a'] -> d。

你可以用同样的方式推理其余的。