Haskell中Tagless Final样板代码优化及相关技术问题咨询

背景 #

最初的Tagless Final风格Lambda类型类及求值实例存在大量Identity/runIdentity样板代码：

class Lambda (repr :: * -> *) where
    int :: Int -> repr Int
    add :: repr Int -> repr Int -> repr Int
    lambda :: forall a b. (repr a -> repr b) -> repr (a -> b)
    apply :: forall a b. repr (a -> b) -> repr a -> repr b

-- eval
instance Lambda Identity where
    int = Identity
    add x y = Identity $ runIdentity x + runIdentity y
    lambda f = Identity $ \x -> runIdentity (f (Identity x))
    apply (Identity f) (Identity x) = Identity $ f x

为消除样板代码，尝试用类型族重构：

{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE TypeFamilies #-}

class Lambda f where
    type Repr f a
    int :: Int -> Repr f Int
    add :: Repr f Int -> Repr f Int -> Repr f Int
    lambda :: forall a b. (Repr f a -> Repr f b) -> Repr f (a -> b)
    apply :: forall a b. Repr f (a -> b) -> Repr f a -> Repr f b
    
data Eval
instance Lambda Eval where
    type Repr Eval a = a
    int = id
    add = (+)
    lambda = id
    apply f = f

问题1：为何exp1声明触发类型错误？ #

错误代码 #

exp1 :: Lambda f => Repr f Int
exp1 = int 1

错误信息 #

app/Main.hs:63:8: error:
    • Couldn't match expected type: Repr f Int
                  with actual type: Repr f0 Int
      NB: ‘Repr’ is a non-injective type family
      The type variable ‘f0’ is ambiguous
    • In the expression: int 1
      In an equation for ‘exp1’: exp1 = int 1
    • Relevant bindings include
        exp1 :: Repr f Int (bound at app/Main.hs:63:1)
   |
63 | exp1 = int 1
   |        ^^^^^

解答 #

核心原因是类型族Repr不具备内射性：Haskell编译器无法从Repr f Int的结果反推出唯一的f类型。

当你写int 1时，int的类型是Lambda f0 => Int -> Repr f0 Int，这里的f0是一个未绑定的模糊类型变量。而exp1的类型要求是Repr f Int，由于Repr不是内射的，编译器无法证明f0和f是同一个类型——完全可能存在两个不同的类型f1和f2，使得Repr f1 Int = Repr f2 Int。

解决方法有两种：

1. 使用可见类型应用（需开启TypeApplications扩展）：

   {-# LANGUAGE TypeApplications #-}
   exp1 :: Lambda f => Repr f Int
   exp1 = int @f 1
   

   显式指定int使用的类型参数f，消除模糊性。
2. 声明内射类型族（需开启InjectiveTypeFamilies扩展）：

   {-# LANGUAGE InjectiveTypeFamilies #-}
   class Lambda f where
       type Repr f a = r | r -> f a  -- 声明Repr是内射的，从结果能反推f和a
       -- 其余方法不变
   

   告诉编译器Repr f a的结果唯一对应f和a，从而能从Repr f Int反推出f。

问题2：用类型族实现Tagless Final是否属于良好实践？ #

解答 #

这取决于具体场景，但通常不是Tagless Final的首选实现方式，原因如下：

• 破坏Tagless Final核心优势：原始Tagless Final的repr是统一的类型构造器（* -> *），天然支持多态解释器且类型安全。用类型族拆分后，破坏了这种统一接口，降低了代码灵活性。
• 类型模糊性问题频发：如问题1所示，非内射类型族会频繁引发模糊类型错误，需要额外扩展（TypeApplications/InjectiveTypeFamilies）解决，增加了复杂度。
• 有更优的样板消除方案：如果只是想消除Identity的样板，更简单的方式是利用GeneralizedNewtypeDeriving或coerce：

  {-# LANGUAGE GeneralizedNewtypeDeriving #-}
  newtype Eval a = Eval a deriving (Functor, Applicative, Num)
  
  instance Lambda Eval where
      int = Eval
      add = (+)
      lambda f = Eval $ \x -> let Eval y = f (Eval x) in y
      apply (Eval f) x = f <$> x
  

  或者直接复用Identity的现有实例，避免手动编写样板代码。

当然，在某些特殊场景（比如需要Repr返回非构造器类型、或需要更灵活的类型映射）下，类型族的方式可能有用，但这已经偏离了Tagless Final的经典设计意图，属于小众用法。

内容的提问来源于stack exchange，提问作者Jw C