Ограничение типа Haskell

Question

Я борюсь с системой типа haskell. В основном то, что я пытаюсь сделать, это определить структуру данных (cf Ast тип данных в образце кода), который представляет собой монаду (это может быть что-то другое). Этот тип параметризуется a, и на нем нет ограничений. Мой вопрос, когда я хочу вникать этот тип, мне может понадобиться некоторые ограничения на параметр типа, например:

{-# LANGUAGE GADTs #-} 

import Control.Monad 

data Ast a where 
    Bind :: Ast a -> (a -> Ast b) -> Ast b 
    Return :: a -> Ast a 

instance Functor Ast where 
    fmap = liftM 

instance Applicative Ast where 
    pure = Return 
    (<*>) = ap 

instance Monad Ast where 
    (>>=) = Bind 

instance Show a => Show (Ast a) where 
    show (Bind x y) = "bind " ++ {- begin error -} show x {- end error -} 
    show (Return y) = "return " ++ show y 

Это дает следующее сообщение об ошибке:

Could not deduce (Show a1) arising from a use of ‘show’ 
from the context (Show a) 
    bound by the instance declaration at src/Main.hs:21:10-31 
Possible fix: 
    add (Show a1) to the context of the data constructor ‘Bind’ 
In the second argument of ‘(++)’, namely ‘show x’ 
In the expression: "bind " ++ show x 
In an equation for ‘show’: show (Bind x y) = "bind " ++ show x 

И это имеет смысл, то компилятор не знает, что x является примером Показать. Мой вопрос: могу ли я выразить это ограничение? В идеале я хотел бы иметь ограничение только на моем Show инстанции, но я также пытался добавить Показать ограничение в Аст конструктор:

data Ast a where 
    Bind :: (Show a, Show b) => Ast a -> (a -> Ast b) -> Ast b 
    Return :: a -> Ast a 

И я получаю эту ошибку:

No instance for (Show a) arising from a use of ‘Bind’ 
Possible fix: 
    add (Show a) to the context of 
    the type signature for (>>=) :: Ast a -> (a -> Ast b) -> Ast b 
In the expression: Bind 
In an equation for ‘>>=’: (>>=) = Bind 
In the instance declaration for ‘Monad Ast’ 

Я понимаю Показать ограничение должно быть добавлено в монады уровне определения типа в класса.

Любая идея, как это сделать?

Спасибо.

Answer 1

Вы не можете иметь это в обоих направлениях.

Класс Functor, из которых Monad является подклассом, настаивает на полном полиморфизме (fmap может применяться к функциям с произвольными типами возврата). Таким образом, вы не можете ограничивать вещи с этой целью. Вы также не можете ограничивать их в пределах Bind, потому что >>= должен принимать произвольные левые операнды.

Альтернативой является использование различных понятий функтора и монады (поиск «индексированной монады»). Следующий код полностью не протестирован.

{-# Language DataKinds, Gadts, KindSignatures #-} 

-- (type-level) free magma 
data FM a = Leaf | Bin (FM a) a (FM a) 

data Ast :: FM * -> * -> * where 
    Return :: a -> Ast 'Leaf a 
    Bind :: Ast ts a -> (a -> Ast us b) -> Ast ('Bin ts a us) b 

class Showy (mag :: FM *) where 
    showy :: Show a => Ast mag a -> String 

instance Showy 'Nil where 
    showy (Return a) = "Return " ++ show a 

instance (Showy as, Show b) => Showy ('Bin as b cs) where 
    showy (Bind m f) = "Bind " ++ showy m 

instance (Showy as, Show b) => Show (Ast as b) where 
    show = showy