5

我一直在试图将我的头包裹在免费的单子上；作为学习帮助，我设法Show为以下Free类型编写了一个实例：

{-# LANGUAGE FlexibleContexts, UndecidableInstances #-}

-- Free monad datatype
data Free f a = Return a | Roll (f (Free f a))

instance Functor f => Monad (Free f) where
    return = Return
    Return a >>= f = f a
    Roll ffa >>= f = Roll $ fmap (>>= f) ffa

-- Show instance for Free; requires FlexibleContexts and
-- UndecidableInstances
instance (Show (f (Free f a)), Show a) => Show (Free f a) where
    show (Return x) = "Return (" ++ show x ++ ")"
    show (Roll ffx) = "Roll (" ++ show ffx ++ ")"


-- Identity functor with Show instance
newtype Identity a = Id a deriving (Eq, Ord)

instance Show a => Show (Identity a) where
    show (Id x) = "Id (" ++ show x ++ ")"

instance Functor (Identity) where
    fmap f (Id x)= Id (f x)


-- Example computation in the Free monad
example1 :: Free Identity String
example1 = do x <- return "Hello"
              y <- return "World"
              return (x ++ " " ++ y)

的使用UndecidableInstances让我有些困扰；没有它有办法吗？Google提供的只是Edward Kmett 的这篇博文Show，令人欣慰的是，它与我的类定义基本相同。

4

1 回答 1

11

您实际上可以消除此处的 UndecidableInstance 要求Show，尽管您不能为Reador做同样的事情Eq。

诀窍是用你可以更直接地展示的东西替换你的仿函数的内容，但你不会告诉其他任何人。因此，我们将出口限制为：

{-# LANGUAGE FlexibleContexts #-}

module Free (Free(..)) where

并为我们只能做的事情敲出一个数据类型show。

newtype Showable = Showable (Int -> ShowS)

showable :: Show a => a -> Showable
showable a = Showable $ \d -> showsPrec d a

instance Show Showable where
    showsPrec d (Showable f) = f d

现在，如果我们从不告诉任何人Showable， 的唯一实例Show (f Showable)将是在 的参数中具有多态性的实例，a最多限制为 Show 实例。只要最终用户没有主动尝试使用其他扩展来破坏您的代码，这就是合理的推理。通过添加功能依赖和/或重叠/不可判定的实例，可能会出现一些问题，但只有那些会破坏意图的东西，没有任何东西会导致你崩溃。

这样我们就可以构建一个可判定的Show实例。

data Free f a = Pure a | Free (f (Free f a))

instance (Functor f, Show (f Showable), Show a) => Show (Free f a) where
  showsPrec d (Pure a)  = showParen (d > 10) $ showString "Pure " . showsPrec 10 a
  showsPrec d (Free as) = showParen (d > 10) $ showString "Free " . showsPrec 10 (fmap showable as)

这里给出的实现并没有消除对FlexibleContexts.

我在几个包中使用了这个技巧——包括我的ad包——来减少对不确定实例的需求。

于 2012-06-04T02:39:33.873 回答