Haskell中两个函数的最通用的“乘积”类型

debugcn 发表于 Dev

武卡塞纳（Vucicasena）

我必须在Haskell中从给定的函数中找到最通用的类型，或者如果存在的话，就找到两个函数的“乘积”的最通用的类型。我不确定，但也许我应该使用鲁滨逊统一算法，但我听不懂。我需要逐步的详细解决方案，这样我才能理解。

功能：

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

如何找到最通用的类型

map iterate
iterate map

这不是功课。

内斯

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

若要派生类型函数和类型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迭代:: :: [a-> a]-> [a-> [a]]

* Main>：t迭代映射

：1：9：
发生检查：无法构造无限类型：a〜 [a]
预期类型：（a-> b）->
a- > b实际类型：（a-> b）-> [a]-> [b]
在“ iterate”的第一个参数中，即“ map”
在表达式中：迭代映射

：1：9：进行
检查：无法构造无限类型：b〜[b]
预期类型：（a-> b）->
a- > b实际类型：（a-> b）- > [a]-> [b]
在“ iterate”的第一个参数中，即“ map”
在表达式中：iterate map