使用函数依赖来消除类型参数

Question

我正在尝试实现一个 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

这可行，但我不喜欢必须在 MStream 类型构造函数中携带 t 参数。当然，只需要 s 参数就足够了，因为 t 可以从 s 派生，只要有 Stream s m t 的见证。我尝试过使用类型族和 GADT，但我一直运行陷入关于模棱两可的类型变量和不满足的函数依赖性的模糊错误。

有没有办法从 MStream 类型构造函数中删除 t 这样我就不必写：

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 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。

Answer 2

所以，我通过移动球门柱（稍微）解决了这个问题：

{-# 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。所以现在，只需将 Stream 上下文替换为 MStream 上下文，即可以更紧凑的方式编写 sillyParser 类型签名。

使用函数依赖来消除类型参数

Using functional dependency to eliminate type parameter

haskell

parsec

functional-dependencies