如何评估Haskell中的这种通用抽象语法树？

Question

我一直想看看我是否可以制作一个非常简单的 AST，它由操作和叶节点组成。但更具体地说，我希望能够使用任何类型作为叶节点，而不是像这样在 AST 数据类型本身中明确指定它。

-- Instead of this
data Tree = Number Int | Word String | Operation Tree (Tree -> Tree -> Tree) Tree

-- I'd like something along the lines of this
data Tree a = Leaf a | Operation Tree (Tree -> Tree -> Tree) Tree

这不一定很实用，但我想看看是否可行。到目前为止，我所管理的最接近的要求我摸索了一些 GADT 的概念：

{-# LANGUAGE GADTs #-}

data Tree l where
  Leaf :: l -> Tree l
  Operation :: Tree a -> (a -> b -> c) -> Tree b -> Tree c

let fivePlus2 = Operation (Leaf 5) (+) (Leaf 2)

eval (Leaf l) = l
eval (Operation left op right) = op (eval left) (eval right)

我的想法是我可以运行 eval fivePlus2，并得到 7。但是，为操作（最后一行）定义的 eval 导致以下非常模糊的错误：

<interactive>:187:38: error:
    • Couldn't match type ‘a’ with ‘p’
      ‘a’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree a -> a
        Actual type: Tree p -> p
    • In the first argument of ‘op’, namely ‘(eval left)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        op :: a -> b -> p (bound at <interactive>:187:22)
        left :: Tree a (bound at <interactive>:187:17)
        eval :: Tree p -> p (bound at <interactive>:187:1)

<interactive>:187:50: error:
    • Couldn't match type ‘b’ with ‘p’
      ‘b’ is a rigid type variable bound by
        a pattern with constructor:
          Operation :: forall a b c.
                       Tree a -> (a -> b -> c) -> Tree b -> Tree c,
        in an equation for ‘eval’
        at <interactive>:187:7-29
      ‘p’ is a rigid type variable bound by
        the inferred type of eval :: Tree p -> p
        at <interactive>:187:1-60
      Expected type: Tree b -> b
        Actual type: Tree p -> p
    • In the second argument of ‘op’, namely ‘(eval right)’
      In the expression: op (eval left) (eval right)
      In an equation for ‘eval’:
          eval (Operation left op right) = op (eval left) (eval right)
    • Relevant bindings include
        right :: Tree b (bound at <interactive>:187:25)
        op :: a -> b -> p (bound at <interactive>:187:22)
        eval :: Tree p -> p (bound at <interactive>:187:1)

老实说，我完全不确定这意味着什么，而且我在这里已经超出了我的理解范围，最初是在 F# 中尝试过的，但发现它的表现力不够。我已经有一段时间没有进行函数式编程了，并且是 Haskell 的初学者，所以如果答案像我 5 岁时那样解释，我将不胜感激。

如果事实证明无法评估这样一棵树，那很好，但我非常想知道它背后的逻辑是什么。谢谢！

Answer 1

向 top-level 函数添加类型签名：

eval :: Tree l -> l

这通常被认为是好的做法，但这对于 GADT 尤其重要，因为否则无法推断出该类型。

如何评估Haskell中的这种通用抽象语法树？

How to evaluate this generic abstract syntax tree in Haskell?

haskell

functional-programming

tree

abstract-syntax-tree

gadt