如何断言内部函数的类型取决于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))

即拉出队列状态,运行f以获得更多状态并将它们放回队列,使用a 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))