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

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

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

Ваш Ответ

1   ответ
11

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

Похожие вопросы