haskell - Haskell 多态性的计算类型

Question

我需要计算以下表达式的类型:

• curry 饭
• 文件夹常量
• (foldr const) 。 ( curry 饭)

首先我有:

curry :: ((a, b) -> c) -> a -> b -> c
fst :: (d, e) -> d 

{}                      |   (a,b)-> c = (d,e) -> d 
{}                      |   (a,b) = (d,e) , c = d
c -> d                  |   (a,b) = (d,e)
c -> d , a ->d          |   b = e
c -> d , a ->d, b -> e  |   {}

然后将结果替换为 a -> b -> c ，得到 d -> e -> d

现在我所做的与此类似:

foldr :: (f -> g -> g) -> g -> [f] -> g
const :: h -> i -> h



{}                      |    (f -> g -> g) =  h -> i -> h 
{}                      |    f = h , g = i, g = h
f -> h                  |    g = i, g = h
f -> h, g -> i          |    i = h
f -> h, g -> i  i->h    |    {}

然后将结果替换为 g -> [f] -> g ，得到 i -> [h] -> i

接下来我要做的(foldr const) 。 (curry fst) 但我不确定这些结果是否正确。无论如何我都尝试过但被卡住了。所以:

(foldr const) :: i -> [h] -> i and (curry fst) :: d -> e -> d
(.) :: (j -> k) -> (l -> j) -> l -> k

然后我开始:

d = (j -> k) -> (l -> j) -> l -> k, e = d -> e -> d

e = (j -> k) -> (l -> j) -> l -> k -> e -> (j -> k) -> (l -> j) -> l -> k

但感觉不对，我无法继续......我的前两个结果正确吗？如果是的话，我该如何解决最后一个问题？

Answer 1

第一个结果是正确的。

在最后一步进行替换之前，第二个结果的计算是正确的。很容易错过。您有(使用 =，而不是 ->，因为后者构造函数类型，因此可能会导致困惑)

f = h, g = i, i = h

因此替换 g -> [f] -> g 给出

h -> [h] -> h

不是i -> [h] -> i，因为虽然g = i，但i = h也是如此，所以在一起，g = h。也就是说，您需要任一来标准化您的替换(应用每个新解决方案来实例化旧的替换并扩展它，给出f = h, g = h, i = h)，或一次一步地仔细应用替换:

g -> [f] -> g
  -- f = h
g -> [h] -> g
  -- g = i
i -> [h] -> i
  -- i = h
h -> [h] -> h

现在，对于计算的最后一步，您已经掌握了所有部分，但您错过了 . 是中缀运算符的方式。它的第一个参数是 foldr const ，它的类型必须是 j -> k。它的第二个参数是 curry fst ，它的类型必须是 l -> j。整个事情的类型是l -> k。因此，您必须求解的方程是

j -> k  =  h -> [h] -> h   -- from the first argument
l -> j  =  d -> e -> d     -- from the second argument

现在，-> 与右侧关联，因此第一个给出

j = h
k = [h] -> h

第二个给出

l = d
j = e -> d

将两者结合起来

h = e -> d

所以我们最终得到(标准化)

h = e -> d
j = e -> d
k = [e -> d] -> e -> d
l = d

并实例化l -> k给出类型

d -> [e -> d] -> e -> d

该函数采用默认的d，然后是函数列表，然后是输入e:如果函数列表为空，则得到默认结果;如果列表非空，您将获得将第一个函数应用于输入的结果。