haskell - 在 Haskell 中统一类型

Question

我有点被关于我的考试的作业困住了。我想通过手动应用统一算法来找出这两个函数的类型：

map map
(\x -> x >>= (\y -> y))

有人能指出我正确的方向吗？到目前为止，我能找到的唯一资源是维基百科条目，由于高度抽象，它并没有真正帮助我。

问候和谢谢。

Answer 1

让我们做第一个。

map :: (a -> b) -> [a] -> [b]

为了清楚起见，现在我们可以用两个不同的名称再次编写它：

map :: (c -> d) -> [c] -> [d]

现在我们将第二个替换为第一个的第一个参数，得到：

(a -> b) === (c -> d) -> ([c] -> [d]) (recall the associativity of (->))
a === (c -> d)
b === ([c] -> [d])

现在我们将这些类型赋值代入第一个签名的剩余部分，得到

map map :: [c -> d] -> [[c] -> [d]]

清除？

Answer 2

的类型map是map :: (a -> b) -> [a] -> [b]。因此， 的类型map foo是[a] -> [b]通过用a和b可以从foo的类型派生的内容来获得的。例如，如果foo :: t -> t您替换a = t, b = t并获得[t] -> [t]。如果foo :: [t] -> Int，您获得[[t]] -> [Int].

在您的情况下，foo( 是map) 的类型是(x -> y) -> [x] -> [y]. 您必须将该类型与 统一起来，以a -> b找出需要替换的内容。[注意函数箭头是右结合的，.]abx -> y -> z = x -> (y -> z)

查找类型

\x -> x >>= (\y -> y)

使用已知类型的(>>=) :: Monad m => m a -> (a -> m b) -> m b. 现在忽略约束 ( Monad m =>)。

作为 的第一个参数(>>=)，x必须有一个m a未知的类型m和a。的第二个参数在(>>=)这里是身份，

(\y -> y) :: t -> t

所以你必须t -> t与统一a -> m b。这为您提供了一些信息a，即a = m b.

这给出了x :: m (m b)和(\x -> x >>= (\y -> y)) :: type_of_x -> type_of_rhs。

终于记住了暂时忘记的约束Monad m =>。