如何在没有 ghci 的情况下找出 haskell 表达式的类型？

Question

我很擅长推断 lambda 表达式的类型，只要它没有任何奇怪的函数，例如 map、filter、foldr 或任何组合在里面。但是，一旦我有了

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

我完全迷路了，我这辈子都想不出如何在不使用 ghci 的情况下找出类型。

如有任何帮助，我们将不胜感激

谢谢

Answer 1

故意注释错误的类型（通常 ()）会对你有所帮助。
例如：

> (\x y -> map x (y (. x))) :: ()

<interactive>:1:2: error:
    • Couldn't match expected type ‘()’
                  with actual type ‘(a0 -> b0)
                                    -> (((b0 -> c0) -> a0 -> c0) -> [a0]) -> [b0]’
    • The lambda expression ‘\ x y -> map x (y (. x))’
      has two arguments,
      but its type ‘()’ has none
      In the expression: (\ x y -> map x (y (. x))) :: ()
      In an equation for ‘it’: it = (\ x y -> map x (y (. x))) :: ()

此技巧在post中介绍：http://www.parsonsmatt.org/2018/05/19/ghcid_for_the_win.html

Answer 2

我认为 "weird" 你的意思是高阶函数。此表达式包含两个：map :: (a -> b) -> [a] -> [b] 和 (.) :: (b -> c) -> (a -> b) -> a -> c。它也是一个 lambda，所以它本身很可能是一个高阶函数。这里每个带括号的箭头都是函数参数的类型。

map 表明 y 必须 return 一个 x 接受的项目列表作为参数。所以他们有部分签名 x :: _yitem -> _outeritem 和 y :: _yarg -> [_yitem]，其中这个 map 的 return 值是 [_outeritem] 类型。请注意，我们还不知道有多少箭头适合这些通配符。

(. x) 转换为 \l -> l . x 转换为 \l r -> l (x r)。整个 lambda 是一个适合 y 的参数，因此 y 是一个高阶函数。 l 必须接受来自 x 的 return 值。它有一个名称，因此 l :: _outeritem -> _lret 和 (. x) :: (_outeritem -> _lret) -> _xarg -> _lret，因为 r 用作 x 的参数。哦，_xarg 是已知的，因为地图是 _yitem。

好的，这本身就是一堆令人困惑的步骤，所以让我们整理一下结果：

type OuterLambda = _xtype -> _ytype -> MapRet
x :: _yitem -> _outeritem
type MapRet = [_outeritem]
y :: YArg -> [_yitem]
type YArg = (_outeritem -> _lret) -> _yitem -> _lret
y :: ((_outeritem -> _lret) -> _yitem -> _lret) -> [_yitem]

进步了！这具有来自 x 和 y 的每种类型的名称。但是我们的表达式是 lambda，所以我们必须接受这两个：

(_yitem -> _outeritem) -> 
(((_outeritem -> _lret) -> _yitem -> _lret) -> [_yitem]) ->
[_outeritem]

这是一种很长的类型。让我们将它与 Yuji Yamamoto 向我们展示的编译器推断类型进行比较：

(a0 -> b0) -> 
(((b0 -> c0) -> a0 -> c0) -> [a0]) -> 
[b0]

匹配。我们这里有相当多的函数顺序：表达式需要函数 x 和 y，而 y 需要一个本身带有 l 函数的函数。我们确实有名称的所有类型都可能是任意复杂的。

如何在没有 ghci 的情况下找出 haskell 表达式的类型？

How do I find out the type of a haskell expression without ghci?

haskell

lambda

type-inference

typing

lambda-calculus