Могу ли я исключить использование UndecidableInstances в этом экземпляре Show для Free Monad?

Я только что пытался обернуть голову вокруг свободных монад; в качестве учебного пособия мне удалось написать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 даетэто сообщение в блоге Эдварда Кметтакоторый имеет в основном то же самоеShow определение класса, как я.

 Daniel Fischer04 июн. 2012 г., 03:05
UndecidableInstances это действительно не беспокоит. По сути, все, что он делает, это говорит компилятору "доверься мне, погоня за экземпляром прекратится". Если вы ошиблись, стек контекста все равно остановит компилятор в бесконечном цикле.

Ответы на вопрос(1)

Решение Вопроса

can устранить требование UndecidableInstance дляShow здесь, хотя вы не можете сделать то же самое для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 пакет - чтобы уменьшить потребность в неразрешимых случаях.

Ваш ответ на вопрос