haskell - 如何断言内部函数的类型取决于 Haskell 中外部函数的类型？

Question

所以，我正在编写一个小辅助函数来进行广度优先搜索(只是一个爱好项目):

import Control.Monad.State
import qualified Data.Set as S

breadthFirst :: (Monad m, Ord a) => (a -> m [a]) -> [a] -> m ()                                                                                                   
breadthFirst f init = evalStateT (go init) S.empty                                                                                                                
  where                                                                                                                                                            
    go :: [a] -> StateT (S.Set a) m ()                                                                                                                             
    go [] = return ()                                                                                                                                              
    go (x:xs) = do                                                                                                                                                 
      visited <- gets (S.member x)                                                                                                                                       
      if visited then (go xs) else do                                                                                                                                      
        modify (S.insert x)                                                                                                                                        
        lift (f x) >>= (\n -> go (xs++n))

IE。从队列中拉出状态，运行 f要获得更多状态并将它们放回队列中，请使用 Set跟踪访问的状态，以及任何副作用 m提供。

除非它不编译: Couldn't match type ‘m’ with ‘m1’等等等等好吧编译器不认为内部 a和 m与外 a相同和 m因此它不认为 f x调用将编译...

但是如果我删除 go 的类型断言我收到 Non-type variable argument in the constraint因为它推断 go 的类型太宽泛:

go :: forall (t :: (* -> *) -> * -> *).
          (MonadTrans t, MonadState (S.Set a) (t m)) =>
          [a] -> t m ()

我可以用 FlexibleContexts 解决这个问题但我知道 go 的类型，这不是随意的 MonadState例如，它只是 StateT .如果我更换 return ()与 StateT $ (\s -> ((), s))那么这为编译器提供了它需要的额外信息，但这也有点令人反感。

有没有办法只告诉编译器 go 的类型签名，包括类型变量与外部函数中的类型变量相同的事实？

Answer 1

是的，它是通过 ScopedTypeVariables 完成的延期。您需要使用 forall 量化外部函数, 然后是 where 子句中定义的函数，除非它们有 forall他们自己将引用外部范围。当您没有作用域类型变量时，每个类型签名都被隐式量化，因此变量可能与编译器不同。

{-# LANGUAGE ScopedTypeVariables #-}

module SO where

import Control.Monad.State
import qualified Data.Set as S

breadthFirst :: forall m a. (Monad m, Ord a) => (a -> m [a]) -> [a] -> m ()
breadthFirst f init = evalStateT (go init) S.empty
  where
    go :: [a] -> StateT (S.Set a) m ()
    go [] = return ()
    go (x:xs) = do
      visited <- gets (S.member x)
      if visited then (go xs) else do
        modify (S.insert x)
        lift (f x) >>= (\n -> go (xs++n))