时间戳

首页 > 解决方案 > “点菜数据类型” - 注入正确的问题

haskell - “点菜数据类型” - 注入正确的问题

问题描述

我正在查看本文中指定的代码：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

我很难把头绕在右边的注射处。两个问题：

标签： haskell

解决方案

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

原始代码使用的方式使实例头比另一个更具体。也就是说：f :<: (f :+: g)比 更具体f :<: (h :+: g)，因为第一个仅匹配后者的（严格）案例子集。

这让编译器很高兴：可以尝试第一个实例。如果匹配，那就太好了。如果它不匹配，并且不统一，我们可以提交第二个更一般的实例。（如果它不匹配但统一，那么我们就被卡住了，我们不能提交到任何一个实例。）

以自己的方式进行操作会增加约束求解卡住的可能性，因为在求解F :<: (F :+: F)两个实例时都适用。在原始代码中，将应用第一个，因为它更具体。

第二个问题，inj = Inr . inj调用本身是递归的吗？

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

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

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

推荐阅读