相互递归类型的最终无标签编码

Question

我试图在 final-tagless 编码中表达一对相互递归的数据类型。

我会写：

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE ExplicitForAll #-}
module Test where

  class ExprSYM repr where
    expr :: forall proc. (ProcSYM proc) => proc Int -> repr

  class ProcSYM repr where
    varProc :: forall a. String -> repr a
    intProc :: String -> repr Int
    subjectOf :: forall expr. (ExprSYM expr) => expr -> repr Int

  myProc = intProc "proc A."

然而，当我写：

myExpr = expr myProc

我收到以下错误：

Could not deduce (Test.ProcSYM proc0)
  arising from a use of ‘Test.expr’
from the context (Test.ExprSYM repr)
  bound by the inferred type of
           Test.myExpr :: Test.ExprSYM repr => repr
  at src/Test.hs:16:3-22
The type variable ‘proc0’ is ambiguous
In the expression: Test.expr Test.myProc
In an equation for ‘Test.myExpr’:
    Test.myExpr = Test.expr Test.myProc

任何此类编码是否需要使用函数依赖（或等效函数）来表达两种 representation 类型之间的约束？

如果是这样，我该怎么写？

Answer 1

让我们先看看myProc

的类型

myProc :: ProcSYM repr => repr Int
myProc = intProc "proc A."

这表示，forall 类型 repr 其中 ProcSYM repr，我是 repr Int 类型的值。如果我们有 ProcSYM 的多个实现，那么这是一个在所有实现中都是多态的值。例如，如果我们有一个对应的标记 GADT ProcSYM' 和 ProcSYM 实例，myProc 可以用作 ProcSYM'.[=59= 的值]

{-# LANGUAGE GADTs #-}

data ProcSYM' a where
    VarProc :: String -> ProcSYM' a
    IntProc :: String -> ProcSYM' a

instance ProcSYM ProcSYM' where
    varProc = VarProc
    intProc = IntProc

myProc' :: ProcSYM' Int
myProc' = myProc

myProc :: ProcSYM repr => repr Int 中的 ProcSym repr 约束提供了一种构造 repr 的方法，这正是 myProc做。不管你要哪个ProcSym repr，它都能构造一个repr Int.

expr :: forall proc. (ProcSYM proc) => proc Int -> repr 类型中的 ProcSYM proc 约束有点没有意义。约束 ProcSYM proc 再次提供了构造 proc 的方法。它无法帮助我们向内看或解构一个proc Int。如果没有办法查看 proc Int 的内部，我们还不如没有 proc Int 参数，而是阅读 expr :: repr.

类型forall proc. ProcSYM proc => proc Int（myProc的类型）承诺，无论你如何构造proc，我都可以提供该类型的值。您想将 myProc 作为第一个参数传递给 expr，

证明了这一点

myExpr = expr myProc

在不选择具体的情况下传入此类型的多态值 proc 需要 RankNTypes.

class ExprSYM repr where
    expr :: (forall proc. ProcSYM proc => proc Int) -> repr

ExprSYM 的实例可以选择 ProcSYM 字典传递给第一个参数。这允许 expr 的实现解构 proc Int。我们将通过使用 GADTs 完成示例来演示这一点，以查看它在做什么。我们还将对 subjectOf.

的类型进行相同的更改

{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE GADTs #-}
module Test where

class ExprSYM repr where
    expr :: (forall proc. ProcSYM proc => proc Int) -> repr

class ProcSYM repr where
    varProc :: forall a. String -> repr a
    intProc :: String -> repr Int
    subjectOf :: (forall expr. ExprSYM expr => expr) -> repr Int

-- Tagged representation for ExprSYM
data ExprSYM' where
    Expr :: ProcSYM' Int -> ExprSYM'
deriving instance Show ExprSYM'

instance ExprSYM ExprSYM' where
    expr x = Expr x  -- chooses that the ProcSYM proc => proc Int must be ProcSYM' Int

-- Tagged representation for ProcSYM
data ProcSYM' a where
    VarProc :: String -> ProcSYM' a
    IntProc :: String -> ProcSYM' a
    SubjectOf :: ExprSYM' -> ProcSYM' Int

deriving instance Show (ProcSYM' a)

instance ProcSYM ProcSYM' where
    varProc = VarProc
    intProc = IntProc
    subjectOf x = SubjectOf x  -- chooses that the ExprSYM repr => repr must be ExprSYM'

-- myProc and myExpr with explicit type signatures
myProc :: ProcSYM repr => repr Int
myProc = intProc "proc A."

myExpr :: ExprSYM repr => repr
myExpr = expr myProc

main = print (myExpr :: ExprSYM')

这会输出 myExpr 的抽象语法树。我们可以看到，如果 expr 的实现想要解构 ProcSYM proc => proc Int 值，它可以（在本例中确实）提供一个 ProcSYM 字典来构建它知道如何解构的值。我们可以在显示值的 IntProc 构造函数中看到这一点。

Expr (IntProc "proc A.")

相互递归类型的最终无标签编码

Final-tagless encoding of mutually recursive types

haskell

typeclass

functional-dependencies