Haskell中两个函数中最通用的"product"类型

Question

我必须从 Haskell 中的给定函数中找到最一般的类型，或者更确切地说，找到两个函数的 "product" 中最一般的类型（如果存在）。我不确定，但也许我应该使用 Robinson 统一算法，但我无法理解。我需要一个详细的解决方案，一步一步，这样我就明白了。

函数：

map :: (a → b) → [a] → [b] 
iterate :: (a → a) → a → [a]

如何为

找到最通用的类型

map iterate
iterate map

这不是作业。

Answer 1

让我们问问 GHCi：

ghci> :type map . iterate
map . iterate :: (a -> a) -> [a] -> [[a]]
ghci> :type iterate . map
iterate . map :: (a -> a) -> [a] -> [[a]]

让我们看看它是如何得到它们的：

给出

map     :: (x -> y) -> [x] -> [y]
iterate :: (b -> b) -> b -> [b]
(.)     :: (s -> t) -> (r -> s) -> (r -> t)

并使用 a ~ b 表示 "types a and b are equal"。

然后在map . iterate中我们有

map :: s -> t where
 s ~ x -> y
 t ~ [x] -> [y]

iterate :: r -> s where
 r ~ b -> b
 s ~ b -> [b]

so
 x -> y ~ s ~ b -> [b]
=>
 x ~ b
 y ~ [b]
 t ~ [b] -> [[b]]

所以map . iterate :: (b -> b) -> [b] -> [[b]].

然后在iterate . map中我们有

iterate :: r -> s where
 s ~ b -> b
 t ~ b -> [b]

map :: s -> t where
 r ~ x -> y
 s ~ [x] -> [y]

so
 b -> b ~ s ~ [x] -> [y]
 b ~ [x]
 b ~ [y]
 x ~ y
 r ~ x -> x
 t ~ [x] -> [[x]]

所以iterate . map :: (x -> x) -> [x] -> [[x]].

虽然这些函数具有相同的类型，但它们的行为却截然不同。

iterate . map 将给定一个函数和一个长度为 k 的列表，生成一个长度为 k.
map . iterate 将给定一个函数和一个长度为 k 的列表，生成一个长度为 k 的无限列表列表。

Answer 2

首先，明确写出所有省略的括号。

要导出a -> b类型的函数和c类型的值的应用类型，我们需要统一a和c类型，注意任何结果类型等价。然后应用程序的类型是 b，在上述等价项下。规则是：

f   ::     a → b
x   ::     c
        ----------
f x ::         b      , { a ~ c }

要半机械地找到这个，只需对齐类型并注意等价：

map ::    (   a1     →     b1     ) → ([a1] → [b1]) 
iterate :: (a2 → a2) → (a2 → [a2])
          --------------------------
        { a1 ~ (a2 → a2) , b1 ~ (a2 → [a2]) }

所以，

map iterate :: [a1] → [b1]

从等价代入，我们得到

            :: [a2 → a2] -> [a2 → [a2]]

现在我们可以将 a2 重命名回 a，或 t，或其他名称。你的第二个例子是类似的：

iterate :: (   a2     →       a2     ) → (a2 → [a2])
map ::      (a1 → b1) → ([a1] → [b1]) 
           ---------------------------
        { a2 ~ a1 → b1 ,  a2 ~ [a1] → [b1] }

由于 a2 ~ a2，我们得到 a1 → b1 ~ [a1] → [b1]:

               a1  →  b1
              [a1] → [b1]
            --------------
        { a1 ~ [a1] ,  b1 ~ [b1] }

两种等价都是不可能的，定义一个无限类型。所以第二个例子在 Haskell:

中没有类型

*Main> :t map iterate
map iterate :: [a -> a] -> [a -> [a]]

*Main> :t iterate map

:1:9:
Occurs check: cannot construct the infinite type: a ~ [a]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map

:1:9:
Occurs check: cannot construct the infinite type: b ~ [b]
Expected type: (a -> b) -> a -> b
Actual type: (a -> b) -> [a] -> [b]
In the first argument of 'iterate', namely 'map'
In the expression: iterate map

Haskell中两个函数中最通用的"product"类型

The most general type of "product" of two functions in Haskell

haskell

types

type-inference

unification