时间戳

首页 > 解决方案 > 理解 foldTree 函数的类型推导

haskell - 理解 foldTree 函数的类型推导

问题描述

看看这个定义出现在Data.Tree：

foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
    go (Node x ts) = f x (map go ts)

我的具体问题是：由于go名称出现在等式的右侧(map go ts)，函数的类型如何

(a -> [b] -> b)

被推断？

例如，有这行代码：

foldTree (:) (Node 1 [Node 2 []])

实例化定义：

foldTree (:) = go where
    go (Node 1 [Node 2 []]) = (:) 1 (map go [Node 2 []])

(:) 1 (map go [Node 2 []])没有完全评估，所以我只看到(:) 1有 type Num a => [a] -> [a]。但是，缺少一个空白，为了填补它，递归应该完成。因此，计算类型似乎有一些循环性。

非常感谢任何见解。

标签： haskelltypestreetype-inferencefold

解决方案

Haskell 的类型推断非常聪明！我不能告诉你这实际上是如何推断出来的，但让我们来看看它可能是怎样的。现实可能不会太远。在这种情况下，实际上不需要类型签名。

foldTree f = go where
    go (Node x ts) = f x (map go ts)

foldTree被定义为接受一个参数，并且go被定义为接受一个参数，所以我们从一开始就知道这些是函数。

foldTree :: _a -> _b
foldTree f = go where
    go :: _c -> _d
    go (Node x ts) = f x (map go ts)

现在我们看到它f是用两个参数调用的，所以它实际上必须是（至少）两个参数的函数。

foldTree :: (_x -> _y -> _z) -> _b
foldTree f = go where
    go :: _c -> _d
    go (Node x ts) = f x (map go ts)

由于foldTree f = go和go :: _c -> _d，结果类型_b实际上必须是_c -> _d*：

foldTree :: (_x -> _y -> _z) -> _c -> _d
foldTree f = go where
    go :: _c -> _d
    go (Node x ts) = f x (map go ts)

f传递给（类型_y）的第二个参数是map go ts. 因为go :: _c -> _d,_y必须是[_d]

foldTree :: (_x -> [_d] -> _z) -> _c -> _d
foldTree f = go where
    go :: _c -> _d
    go (Node x ts) = f x (map go ts)

go将其参数与 匹配Node x ts，并且Node是 的数据构造函数Tree，因此go的参数 ( _c) 必须是Tree.

foldTree :: (_x -> [_d] -> _z) -> Tree _p -> _d
foldTree f = go where
    go :: Tree _p -> _d
    go (Node x ts) = f x (map go ts)

构造函数的第一个字段Node作为 的第一个参数传递f，因此_x和_p必须相同：

foldTree :: (_x -> [_d] -> _z) -> Tree _x -> _d
foldTree f = go where
    go :: Tree _x -> _d
    go (Node x ts) = f x (map go ts)

由于go _定义为f _ _，它们必须具有相同类型的结果，_z因此_d：

foldTree :: (_x -> [_d] -> _d) -> Tree _x -> _d
foldTree f = go where
    go :: Tree _x -> _d
    go (Node x ts) = f x (map go ts)

唷。现在编译器检查以确保这些类型有效（它们确实有效），并将它们从“元变量”（意味着推理引擎不知道它们代表什么类型的变量）“概括”为量化类型变量（肯定是多态的），它得到

foldTree :: forall a b. (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
    go :: Tree a -> b
    go (Node x ts) = f x (map go ts)

现实有点复杂，但这应该给你要点。

[*] 这一步有点作弊。我忽略了一个名为“let generalization”的功能，在这种情况下不需要它，实际上它被 GHC Haskell 中的几个语言扩展禁用。

推荐阅读