Использование функциональной зависимости для исключения параметра типа

Question

Я пытаюсь реализовать оболочку Parsec Stream, которая будет запоминать последний токен uncons 'd, чтобы обеспечить некоторую возможность поиска. Я хочу, чтобы обертка работала с любым экземпляром Stream. Вот то, что я до сих пор:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-} 
module MStream where 

import Text.Parsec 
import Control.Monad (liftM) 

data MStream s t = MStream (Maybe t) s 

instance Stream s m t => Stream (MStream s t) m t where 
    uncons (MStream _ s) = fmap (\(t, s') -> (t, MStream (Just t) s')) `liftM` uncons s 

getPrevToken :: Stream s m t => ParsecT (MStream s t) u m (Maybe t) 
getPrevToken = (\(MStream t _) -> t) `liftM` getInput 

mstream :: s -> MStream s t 
mstream = MStream Nothing 

Это работает, но я не люблю носить параметр t в конструкторе MStream типа. Разумеется, этого должно быть достаточно, чтобы требовать только параметр s, поскольку t может быть получен из s, пока есть свидетель для Stream s m t. Я пробовал использовать семейства типов и GADT, но я все время сталкиваюсь с неясными ошибками в отношении неоднозначных переменных типа и неудовлетворенных функциональных зависимостей.

Есть ли способ, чтобы удалить t из конструктора по MStream типа, так что я не должен писать:

sillyParser :: Stream s m Char => ParsecT (MStream s Char) u m String 
sillyParser = do 
    t <- getPrevToken 
    maybe (string "first") (\c -> string $ "last" ++ [c]) t 

Answer 1

Итак, я решил это, двигаясь по ходу игры (несколько):

{-# LANGUAGE FlexibleContexts, FlexibleInstances, 
      MultiParamTypeClasses, FunctionalDependencies #-} 

module MStream where 

import Text.Parsec 
import Control.Monad (liftM) 

class Stream s m t => MStream s m t | s -> t where 
    getPrevToken :: ParsecT s u m (Maybe t) 

data MStreamImpl s t = MStreamImpl (Maybe t) s 

instance Stream s m t => MStream (MStreamImpl s t) m t where 
    getPrevToken = (\(MStreamImpl t _) -> t) `liftM` getInput 

instance Stream s m t => Stream (MStreamImpl s t) m t where 
    uncons (MStreamImpl _ s) = fmap (\(t, s') -> (t, MStreamImpl (Just t) s')) `liftM` uncons s 

mstream :: s -> MStreamImpl s t 
mstream = MStreamImpl Nothing 

sillyParser :: MStream s m Char => ParsecT s u m String 
sillyParser = do 
    t <- getPrevToken 
    maybe (string "first") (\c -> string $ "last" ++ [c]) t 

Вместо того, чтобы пытаться удалить параметр типа из MStream, я повернулся MStream в класс типов, с каноническим например MStreamImpl. Итак, подпись типа sillyParser может быть записана более компактно, просто заменив контекст Stream на контекст MStream.

Answer 2

С

{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE ExistentialQuantification #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE UndecidableInstances #-} 

module MStream where 

import Control.Monad (liftM) 

-- Class so we don't need to carry `m` in `MStream` definition. 
class StreamDep s t | s -> t where 
class StreamDep s t => Stream s m t where 
    uncons :: s -> m (Maybe (t, s)) 

data MStream s = forall t. StreamDep s t => MStream (Maybe t) s 

data ParsecT s u m a = ParsecT s u (m a) 
instance Monad m => Monad (ParsecT s u m) where 

getInput :: ParsecT s u m s 
getInput = undefined 

instance StreamDep s t => StreamDep (MStream s) t where 

instance (Monad m, Stream s m t) => Stream (MStream s) m t where 
    uncons (MStream _ s) = fmap (\(t, s') -> (t, MStream (Just t) s')) `liftM` uncons s 

getPrevToken :: (Monad m, Stream s m t) => ParsecT (MStream s) u m (Maybe t) 
getPrevToken = (\(MStream t _) -> t) `liftM` getInput 

mstream :: StreamDep s t => s -> MStream s 

я получаю довольно близко, но получаю сообщение об ошибке:

Pars.hs:28:35: 
    Could not deduce (t1 ~ t) 
    from the context (Monad m, Stream s m t) 
     bound by the type signature for 
       getPrevToken :: (Monad m, Stream s m t) => 
           ParsecT (MStream s) u m (Maybe t) 
     at Pars.hs:27:17-76 
    or from (StreamDep s t1) 
     bound by a pattern with constructor 
       MStream :: forall s t. StreamDep s t => Maybe t -> s -> MStream s, 
       in a lambda abstraction 

С помощью обоих контекстов Stream s m t и StreamDep s t1 должно быть очевидно, что (t ~ t1).

С помощью артиллерии, мы можем сделать его компиляции:

getPrevToken :: (Monad m, Stream s m t) => ParsecT (MStream s) u m (Maybe t) 
getPrevToken = (\(MStream t _) -> unsafeCoerce t) `liftM` getInput 

Но я не могу попробовать это, так как это требует изменения в parsec.