3

我有 function smallStep :: Command -> Data -> Either StepError Data，我想bigStep :: [Command] -> Data -> Either StepError Data使用它，具有以下语义：

bigStep []   data   = Right data
bigStep c:cs data   = do
               data' <- bigStep cs data
               smallStep c data'

这并不复杂，但如果smallStep有 type Command -> Data -> Data，我会bigStep简单地实现 as bigStep commands data = foldr data smallStep commands。

当然，我也想在foldr这里使用。我该怎么做呢？foldM被提升了foldl，并且反转列表听起来不是一个非常好的主意。

4

1 回答 1

8

一般来说，就资源使用而言，左折叠不会比右折叠更好或更差。但是，我认为这[Command]应该是一个序列命令列表，旨在按照提供的顺序一个接一个地执行。如果是这种情况，从一开始就向后构建这些列表可能是最简单的（而不是颠倒它们 - 对于长列表来说，这确实是一项代价高昂的操作）。如果你不想这样做，这里有一个一般的单子右弃牌：

foldrM :: Monad m => (a -> b -> m b) -> b -> [a] -> m b
foldrM f d []     = return d
foldrM f d (x:xs) = (\z -> f x z) =<< foldrM f d xs

请注意以下所有类型：

foldl :: (a -> b -> a) -> a -> [b] -> a
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a

foldr :: (a -> b -> b) -> b -> [a] -> b
foldrM :: Monad m => (a -> b -> m b) -> b -> [a] -> m b

我们可以推断这foldrM确实是一个正确的折叠。

但是，如果您需要fold一个非常大的列表，那么上面的两个单子折叠都是惰性的，并且只有在对最后一个函数应用程序进行排序后才会开始评估。

于 2013-06-12T02:50:05.300 回答