我可以在此Show实例中免除Monad的使用UndecidableInstances吗？ [英] Can I eliminate the use of UndecidableInstances in this Show instance for a Free Monad?

问题描述

我刚刚试图将自己的头围绕在免费的monads上;作为学习辅助工具，我为下面的 Free 类型写了一个 Show c>实例：

  { - ＃LANGUAGE FlexibleContexts，UndecidableInstances＃ - } 
 
  - 免费monad数据类型
 data Free fa =返回一个| Roll（f（Free f a））
 
 instance Functor f => Monad（Free f）其中
 return =返回
返回a>> = f = fa 
 Roll ffa>> = f = Roll $ fmap（>> = f ）ffa 
 
  - 显示Free的实例;需要FlexibleContexts和
  -  UndecidableInstances 
 instance（Show（f（Free f a）），Show a）=> Show（Free fa）其中
 show（Return x）=Return（++ show x ++）
 show（Roll ffx）=Roll（++ show ffx ++ ）
 
 
  - 显示实例的身份仿函数
 newtype身份a = Id a衍生（Eq，Ord）
 
实例显示a => ;显示（身份a）其中
显示（Id x）=Id（++ show x ++）
 
实例Functor（Identity）其中
 fmap f Id x）= Id（fx）
 
 
  -  Free monad 
中的计算示例example1 ::自由标识字符串
 example1 = do x<  -  return Hello
y<  -  returnWorld
 return（x ++++ y）
  

使用 UndecidableInstances 有点困扰我;有没有办法做到这一点？ Google产生的所有结果都是 Edward Kmett发布的这篇博文，它基本上已经基本上和我一样 can 在这里消除了 Show 的UndecidableInstance要求，尽管您不能对 Read 或 Eq 。



诀窍在于用你可以直接显示的东西替换函数的内容，但是不要告诉其他人。因此，我们只会限制我们的出口：



  { - ＃LANGUAGE FlexibleContexts＃ - } 
 
模块免费（免费（..）），其中
  

只有 show 。

  newtype Showable = Showable（Int  - > ShowS ）
 
 showable ::显示a => a  - >可显示
可显示a =可显示$ \d  - > showsPrec da 
 
 instance显示可显示的位置
显示的是可编程显示器d（可显示的f）= fd 
  

现在，如果我们从不告诉任何人关于 Showable ，则只有 Show（f Showable）将会是 a 参数中多态的实例，最多只限于一个Show实例。只要最终用户不积极尝试使用其他扩展来破坏您的代码，这就是合理的推理。有些狡猾可能是因为增加了函数依赖和/或重叠/不可判定的实例，但只是颠覆意图的东西，没有任何东西可以导致你崩溃。

我们可以构建一个可决定的 Show 实例。

  data Free fa =纯a | Free（f（Free f a））
 
 instance（Functor f，Show（f Showable），Show a）=> Show（Free f a）其中
显示Prec d（Pure a）= showParen（d> 10）$ showStringPure。显示预览10 a 
显示预订d（免费）= showParen（d> 10）$ showString免费。 showsPrec 10（fmap showable as）
  

这里给出的实现不会消除 FlexibleContexts ，但是你也可以通过编写一些附加的类层来消除它 - 如果你真的觉得需要兼容Haskell 98的话。

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

I've just been trying to wrap my head around free monads; as a learning aid, I've managed to write a Show instance for the following Free type:

{-# 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)

The use of UndecidableInstances bothers me somewhat; is there a way to do without it? All that Google yields is this blog post by Edward Kmett, which comfortingly has basically the same Show class definition as I do.

解决方案

You actually can eliminate the UndecidableInstance requirement for Show here, though you can't do the same thing for Read or Eq.

The trick is to replace the contents of your functor with something you can show more directly, but that you don't tell anyone else about. Consequently, we'll limit our exports to just:

{-# LANGUAGE FlexibleContexts #-}

module Free (Free(..)) where

and bang out a data type for things we can only 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

Now, if we never tell anyone about Showable, the only instances for Show (f Showable) will be instances that were polymorphic in the argument to a, constrained at most up to a Show instance. This is sound reasoning as long as the end user isn't actively trying to subvert your code using other extensions. Some hinkiness is possible with the addition of functional dependencies and/or overlapping/undecidable instances but only things that subvert intent, nothing that can cause you to crash.

With that out of the way we can build a decidable Show instance.

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)

The implementation given here doesn't eliminate the need for FlexibleContexts, but you can eliminate that too -- if you really feel the need for Haskell 98 compatibility -- by writing a couple of additional class layers.

I use this trick in a couple of packages -- including my ad package -- to reduce the need for undecidable instances.

这篇关于我可以在此Show实例中免除Monad的使用UndecidableInstances吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！