Haskell 中的手动类型推断

Question

考虑函数

f g h x y = g (g x) (h y)

它的类型是什么？显然我可以只使用 :t f 来找出答案，但如果我需要手动推断，最好的方法是什么？

我看到的方法是将类型分配给参数并从那里推导 - 例如x :: a、y :: b 给我们 g :: a -> c 和 h :: b -> d 对于某些 c、d（来自 g x、h y) 然后我们继续从那里进行推论（c = a 从 g (g x) (h y) 等）。

然而，这有时会变成一团糟，而且我常常不确定如何进行进一步的推论或完成后的计算。有时会发生其他问题 - 例如，在这种情况下 x 将变成一个函数，但在作弊和查找类型之前这对我来说并不明显。

是否有一种始终有效的特定算法（并且对于人类快速执行是合理的）？否则，我是否缺少一些启发式或提示？

Answer 1

让我们检查顶层的函数：

f g h x y = g (g x) (h y)

我们将从为类型分配名称开始，然后随着我们对函数的更多了解，继续对它们进行专门化。

首先，让我们为最上面的表达式指定一个类型。我们称它为 a:

g (g x) (h y) :: a

我们把第一个参数取出来，分别赋值：

-- 'expanding'  (g (g x)) (h y) :: a
h y :: b
g (g x) :: b -> a

再来一次

-- 'expanding' g (g x) :: b -> a
g x :: c
g :: c -> b -> a

再来一次

-- 'expanding' g x :: c
x :: d
g :: d -> c

但请稍等：我们现在有 g :: c -> b -> a 和 g :: d -> c。所以通过检查，我们知道 c 和 d 是等价的（写作 c ~ d）并且 c ~ b -> a.

这可以通过简单比较我们已经推断出的g的两种类型来推断。请注意，这不是类型矛盾，因为类型变量足够通用以适合它们的等价物。例如，如果我们推断 Int ~ Bool 某处将自相矛盾。

所以我们现在总共有以下信息：（省略了一点工作）

y :: e
h :: e -> b
x :: b -> a             -- Originally d, applied d ~ b -> a.
g :: (b -> a) -> b -> a -- Originally c -> b -> a, applied c ~ b -> a

这是通过替换每个类型变量的最具体形式来完成的，即用 c 和 d 替换更具体的 b -> a.

所以，简单地检查哪些论点去哪里，我们看到

f :: ((b -> a) -> b -> a) -> (e -> b) -> (b -> a) -> e -> a

GHC 证实了这一点。

Answer 2

嗯函数是：

f g h x y = g (g x) (h y)

或更详细：

f g h x y = (g (g x)) (h y)

最初我们假设所有四个参数（g、h、x和y）都有不同的类型。我们还为我们的函数引入了一个输出类型（这里是t）：

g :: a
h :: b
x :: c
y :: d
f g h x y :: t

但是现在我们要进行一些推理。例如，我们看到 g x，这意味着有一个函数应用程序具有 g 函数和 x 参数。这意味着 g 是一个函数，输入类型为 c，因此我们将 g 的类型重新定义为：

g :: a ~ (c -> e)
h :: b
x :: c
y :: d
f g h x y :: t

（这里波浪号 ~ 表示两种类型相同，所以 a 与 c -> e 相同）。

由于 g 的类型为 g :: c -> e，而 x 的类型为 c，这意味着函数应用程序的结果 g x 的类型为g x :: e.

我们看到另一个函数应用程序，g 作为函数，g x 作为参数。所以这意味着 g 的输入类型（即 c）应该等于 g x 的类型（即 e），因此我们知道 c ~ e，所以现在的类型是：

     c ~ e
g :: a ~ (c -> c)
h :: b
x :: c
y :: d
f g h x y :: t

现在我们看到一个带有 h 函数和 y 参数的函数应用程序。所以这意味着 h 是一个函数，并且输入类型与 y :: d 的类型相同，所以 h 具有类型 d -> f，因此意味着：

     c ~ e
g :: a ~ (c -> c)
h :: b ~ (d -> f)
x :: c
y :: d
f g h x y :: t

最后我们看到一个函数应用程序 g (g x) 函数和 h y 参数，这意味着 g (g x) :: c 的输出类型应该是一个函数， f 作为输入类型，t 作为输出类型，所以这意味着 c ~ (f -> t)，因此：

     c ~ e
     c ~ (f -> t)
g :: a ~ (c -> c) ~ ((f -> t) -> (f -> t))
h :: b ~ (d -> f)
x :: (f -> t)
y :: d
f g h x y :: t

所以这意味着由于 f 具有这些参数 g、h、x 和 y，f 的类型是：

f :: ((f -> t) -> (f -> t)) -> (d -> f) -> (f -> t) -> d -> t
--   \_________ __________/    \__ ___/    \__ ___/    |
--             v                  v           v        |
--             g                  h           x        y

Answer 3

您已经描述了如何操作，但您可能错过了统一步骤。也就是有时候我们知道两个变量是一样的：

x :: a
y :: b
g :: a -> b    -- from g x
h :: c -> d    -- from h y
a ~ b          -- from g (g x)

我们知道 a 和 b 是相同的，因为我们将 g x、一个 b 传递给 g，它需要一个 a。所以现在我们将所有 b 替换为 a，并继续直到我们考虑了所有子表达式...

关于您的 "huge mess" 评论，我有几点要说：

这是方法。如果太难，你只需要练习，就会变得更容易。您将开始培养一种直觉，而且它会变得更容易。
这个特殊的功能不是一个容易实现的功能。我已经编程 Haskell 12 年了，我仍然需要在纸上完成统一算法。它是如此抽象的事实并没有帮助——如果我知道这个函数的目的是什么，那就容易多了。

Answer 4

简单地记下它们下面的所有实体的类型：

f g h x y = g (g x)   (h y) 
                 x :: x  y :: y
                       h :: y -> a            , h y :: a
               g :: x -> b                    , g x :: b
            g    :: b -> (a -> t)             , x ~ b , b ~ (a -> t)
f :: (x -> b) -> (y -> a) -> x -> y -> t      , x ~ b , b ~ (a -> t)
f :: (b -> b) -> (y -> a) -> b -> y -> t      , b ~ (a -> t)
--       g           h       x    y

因此f :: ((a -> t) -> (a -> t)) -> (y -> a) -> (a -> t) -> y -> t。就这些了。

的确如此，

~> :t let f g h x y = g (g x) (h y) in f
    :: ((t1 -> t) -> t1 -> t) -> (t2 -> t1) -> (t1 -> t) -> t2 -> t

事情是这样的：

x 必须有某种类型，我们称它为 x：x :: x.
y 必须有某种类型，我们称它为 y：y :: y.
h y 必须有一些类型，我们称它为 a: h y :: a。因此 h :: y -> a.
g x 必须有某种类型，我们称它为 b：g x :: b。因此 g :: x -> b.
g _ _ 必须有某种类型，我们称它为 t。因此 g :: b -> a -> t.
这与 g :: b -> (a -> t).
g的两个类型签名必须统一，即在涉及的类型变量的某些替换下相同，由于这两个签名描述的是同一个实体，g.
因此我们必须有 x ~ b, b ~ (a -> t)。这是替换。
拥有 f 的所有参数类型，我们知道它产生 g 产生的结果，即 t。所以我们可以记下它的类型，(x -> b) -> (y -> a) -> x -> y -> t.
最后，我们根据替换来替换类型，以减少涉及的类型变量的数量。因此，我们首先用 b 替换 x，然后用 a -> t 替换 b，每次都从替换中删除消除的类型变量。
当替换为空时，我们就完成了。

当然我们可以选择首先用 x 替换 b，最后替换为 x ~ (a -> t)，然后我们最终会得到相同的类型最后，如果我们总是用更复杂的类型替换更简单的类型（例如，将 b 替换为 (a -> t)，并且不是反之亦然）。

简单的步骤，有保证的结果。

这是另一个更短/更清晰的推导尝试。我们关注 g x 作为 g 的论证，因此 g x :: x（琐碎的部分仍然存在，h y :: a）：

f g h x y = g (g x)   (h y)      {- g :: g , h :: h , x :: x , y :: y
  g h x y        x       y                 , g x   :: x   -- !
                  x       a      t         , g x a :: t
                                               x a :: t  ... x ~ a->t
f :: g             ->h     ->x     ->y->t
f :: (x     ->x   )->(y->a)->x     ->y->t 
f :: ((a->t)->a->t)->(y->a)->(a->t)->y->t      -}

毕竟很简单。

定义中的最后一个参数可以省略，如f g h x = (g . g) x . h。

Haskell 中的手动类型推断

Manual type inference in Haskell

haskell

types

type-inference