了解foldTree函数的类型派生 [英] Understanding foldTree function's type derivation

问题描述

查看此定义出现在 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)中方程的右侧时，函数的类型如何

My specific question is: as go name appears in the right-hand side of the equation in (map go ts), how is the type of the function

(a -> [b] -> b)

被推断吗?

例如，具有以下代码行:

For example, having this line of code:

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

实例化定义:

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

(:) 1(map go [节点2 []])没有得到完全评估，所以我只看到(:) 1 具有类型数a =>[a]->[a] .但是，缺少一个空白，并且为了填补该空白，应该完成递归.因此，计算类型似乎有些循环.

(:) 1 (map go [Node 2 []]) is not fully evaluated, so I just see (:) 1 having the type Num a => [a] -> [a]. However, there is one gap missing and, in order to fill it, the recursion should be completed. So, there seems to be some circularity for calculating the type.

任何见解都会受到赞赏.

Any insights are much appreciated.

推荐答案

Haskell的类型推断非常聪明！我无法告诉您这实际上是如何推断的，但让我们逐步了解一下它可能是怎样的.现实可能还不太遥远.在这种情况下，实际上不需要类型签名.

Haskell's type inference is very clever! I can't tell you how this actually gets inferred, but let's walk through how it might be. The reality is probably not too far off. The type signature is actually not required in this case.

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

foldTree 定义为接受一个参数，而 go 定义为接受一个参数，因此我们从一开始就知道这些是函数.

foldTree is defined to take an argument, and go is defined to take an argument, so we know right from the start that these are functions.

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

现在我们看到 f 用两个参数调用，因此它实际上必须是(至少)两个参数的函数.

Now we see that f is called with two arguments, so it must actually be a function of (at least) two arguments.

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 *:

Since foldTree f = go, and go :: _c -> _d, the result type _b must actually be _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]

The second argument passed to f (of type _y) is map go ts. Since go :: _c -> _d, _y must be [_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 .

go matches its argument against Node x ts, and Node is a data constructor for Tree, so go's argument (_c) must be a 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 必须相同:

The first field of the Node constructor is passed as the first argument of f, so _x and _p must be the same:

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:

Since go _ is defined as f _ _, they must have results of the same type, so _z is _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)

哇.现在，编译器进行检查以确保这些类型可以工作(它们可以做到)，并通用化"这些类型.他们来自元变量"(表示推断引擎不知道它们代表什么类型的变量)到量化的类型变量(绝对是多态的变量)，并且得到

Whew. Now the compiler checks to make sure these types work out (which they do), and it "generalizes" them from "metavariables" (variables that mean the inference engine doesn't know what type they represent) to quantified type variables (variables that are definitely polymorphic), and it gets

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)

现实有点复杂，但这应该能给您带来要点.

The reality is a bit more complicated, but this should give you the gist.

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

[*] This step is a bit of a cheat. I'm ignoring a feature called "let generalization", which isn't needed in this context and which is actually disabled by several language extensions in GHC Haskell.

这篇关于了解foldTree函数的类型派生的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！