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

Я пытаюсь реализовать оболочку Parsec Stream, которая будет помнить последний токен uncons, чтобы обеспечить некоторую возможность просмотра назад. Я хочу, чтобы оболочка работала с любым экземпляром 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

functional-dependencies haskell parsec
person pat    schedule 16.07.2015    source источник
comment
Я попытался создать StreamDep s t | s -> t суперкласс Stream и использовать его: data MStream s = forall t. StreamDep s t => MStream (Maybe t) (m ()) s. Также data MStream s = forall m t. Stream s m t => MStream (Maybe t) (m ()) s. Я бы сказал, не стоит боли.   -  person phadej    schedule 17.07.2015

Ответы (2)


arrow_upward
1
arrow_downward

С участием

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

person phadej    schedule 16.07.2015

arrow_upward
0
arrow_downward

Итак, я решил это, переместив стойки ворот (несколько):

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

person pat    schedule 17.07.2015