haskell - "Data Types a la carte"- 注入(inject)正确的问题

Question

我正在查看本文中指定的代码:http://www.staff.science.uu.nl/~swier004/publications/2008-jfp.pdf ，数据类型点菜。

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE ScopedTypeVariables #-}


data Expr f = In (f (Expr f))

data Val e = Val Int
data Add e = Add e e 
data Mul x = Mul x x

type IntExpr = Expr Val

type AddExpr = Expr Add


data ( f:+:g ) e = Inl (f e)| Inr (g e)

class (Functor sub, Functor sup) => sub :<: sup where
  inj :: sub a -> sup a

instance Functor sym => sym :<: sym where
  inj = id

instance {-# OVERLAPPING #-} (Functor f, Functor g) => (f :<: (f :+: g)) where 
  inj = Inl

instance {-# OVERLAPPING #-} (Functor f, Functor g, Functor h, f :<: g) => (f :<: (h :+: g)) where
  inj l = Inr (inj l)

addExample::Expr ( Val :+: Add )
addExample= In( 
               Inr( 
                   Add
                   (In (Inl (Val 118)  ) ) 
                   (In (Inl (Val 1219) ) ) 
                  ) 
               )
instance Functor Val where
  fmap f (Val x)=Val x

instance Functor Add where
  fmap f (Add e1 e2) = Add (f e1) (f e2)

instance Functor Mul where
  fmap f (Mul e1 e2) = Mul (f e1) (f e2)


instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap f (Inl e1) = Inl (fmap f e1)
  fmap f (Inr e2) = Inr (fmap f e2)

foldExpr::Functor f => (f a -> a) -> Expr f -> a 
foldExpr f (In t) = f (fmap (foldExpr f) t)

class Functor f => Eval f where
  evalAlgebra ::f Int -> Int

instance Eval Val where
  evalAlgebra (Val x) = x

instance Eval Add where
  evalAlgebra (Add e1 e2) = e1 + e2

instance Eval Mul where
  evalAlgebra (Mul e1 e2) = e1 * e2

instance (Eval f, Eval g) => Eval (f :+: g) where
  evalAlgebra (Inl x) = evalAlgebra x
  evalAlgebra (Inr y) = evalAlgebra y


eval::Eval f => Expr f -> Int
eval expr = foldExpr evalAlgebra expr

inject::(g :<: f) => g (Expr f) -> Expr f
inject = In . inj

val::(Val :<: f) => Int -> Expr f
val x = inject (Val x)

infixl 6 ⊕
(⊕):: (Add :<: f) => Expr f -> Expr f -> Expr f
x ⊕ y = inject (Add x y) 

infixl 7 ⊗
(⊗):: (Mul :<: f) => Expr f -> Expr f -> Expr f
x ⊗ y = inject (Mul x y)

xxx :: Int -> Expr (Val :+: (Mul :+: Add) ) 
xxx x = val 100 ⊗ val 5

我很难将头绕到右侧的注入(inject)处。两个问题:

• 为什么不这样声明:instance {-# OVERLAPPING #-} => (f :<: (g :+: f)) where ...与左侧的注入(inject)类似。

• 第二个问题是inj = Inr . inj递归调用自身？

Answer 1

Why is not declared like this: instance {-# OVERLAPPING #-} => (f :<: (g :+: f)) where ... similar to the injection to the left.

原始代码使用的方式使实例头比其他实例头更加具体。即:f :<: (f :+: g)比 f :<: (h :+: g) 更具体，因为第一个仅匹配案例的(严格)子集。后者。

这让编译器很高兴:可以尝试第一个实例。如果匹配，那就太好了。如果它不匹配，并且不统一，我们可以提交第二个更通用的实例。 (如果它不匹配但统一，那么我们就会陷入困境，并且无法提交到任何一个实例。)

按您的方式进行会增加约束求解陷入困境的可能性，因为在解析 F :<: (F :+: F) 时两种情况都适用。在原始代码中，将应用第一个，因为它更具体。

Second question, is the inj = Inr . inj calling itself recursively?

没有。最后inj是由 f :<: g 的实例定义的，所以它是一个不同的函数。这种情况经常发生，例如

-- pseudocode
instance Show a => Show (Maybe a) where
   show Nothing = "Nothing"
   show (Just x) = "Just " ++ show x

最后一行调用 Show a方法，并且不递归。