haskell - 我可以在 Free Monad 的 Show 实例中消除 UndecidableInstances 的使用吗？

Question

我一直在尝试了解免费的 monad；作为学习辅助工具，我成功地为以下 Free 类型编写了一个 Show 实例:

{-# 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 产生的所有结果是 this blog post by Edward Kmett ，令人欣慰的是，它具有与我基本相同的 Show 类定义。

Answer 1

您实际上可以消除 Show 的 UndecidableInstance 要求在这里，尽管您不能对 Read 执行相同的操作或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 的需要，但是您也可以通过编写几个额外的类层来消除它 - 如果您确实需要 Haskell 98 兼容性。

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