foldlWithKey in monad

Question

我正在寻找一个像foldlWithKey一样的函数,但是封装在monad中.

我希望它有类型

Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a

但是Hoogle没有给我任何类型的东西.

Answer 1

foldlWithKey已经非常接近你想要的了.如果你专注a于m a你将有一些操作在monad中封装的值.

foldlWithKey :: (  a -> k -> b ->   a) ->   a -> Map k b ->   a
foldlWithKey :: (m a -> k -> b -> m a) -> m a -> Map k b -> m a
             {-  ^- you don't want these -^   -}

我们可以摆脱m a你不想要的两个>>=和return.

foldlWithKeyM :: Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a
foldlWithKeyM f acc = foldlWithKey f' (return acc) 
    where
        f' ma k b = ma >>= \a -> f a k b

Answer 2

@ Cirdec的解决方案当然有效,但它有一个可能的问题:它>>=深深地向左倾斜.对于许多(但不是全部!)monad,这可以使堆栈爆炸类似于使用非严格时foldl.所以我将提出一个不同的解决方案,>>=而不是向右.对于像IO这样的monad 应该允许在执行时从地图中懒惰地构造和消耗该动作.

这个解决方案可能有点棘手,因为它使用右折叠来构建最终消耗起始值的monadic函数.至少我在确保类型正确方面遇到了一些麻烦.

除了密钥处理之外,这与使用的方法基本相同Data.Foldable.foldlM.

-- Pragma needed only to give f' a type signature for sanity.  Getting it 
-- right almost took a piece of mine until I remembered typed holes.
{-# LANGUAGE ScopedTypeVariables #-}

import Data.Map

foldlWithKeyM
  :: forall m a k b. Monad m => (a -> k -> b -> m a) -> a -> Map k b -> m a
foldlWithKeyM f start m = foldrWithKey f' return m $ start
  where
    f' :: k -> b -> (a -> m a) -> (a -> m a)
    f' k b a2mb a = f a k b >>= a2mb