1

所以我有一些我想在其中使用的 Haskell 代码Data.Set。基本上是因为我没有过多地研究替代方案，并且需要一个结构来存储 Ord 的元素而不会重复。

我现在遇到了一种情况，我想为 Data.Set 使用类似 mapM 的东西，这样我就可以对集合的各个元素执行单子操作。我已经在Hayoo上搜索过类似的类型，(a -> m b) -> Set a -> m (Set b)但没有找到任何有用的东西。

我还调查了Data.Traversable一下，发现它有 []、Maybe 和 (Map k) 的实例，但没有 Set。

所以我的问题是：

  1. 为什么Data.Set中没有Set的mapM？
  2. 是否已经有一个包可以提供我错过的 mapM 之类的东西？
  3. 想要在 Sets 上映射 M 是否气馁？（为什么以及有什么替代方案？）
4

2 回答 2

8

主要问题是Traversable需要Functor和 集合不能是函子，因为它们需要Ord约束，而函子必须不受约束。

但是，集合是可折叠的，因此如果您不需要收集结果，可以使用mapM_from Data.Foldable。

如果您确实需要结果，您可以通过列表，例如

fromList <$> mapM f (toList s)
于 2012-12-05T19:13:49.083 回答
4

您可能对镜头包感兴趣。它为遍历（以及许多其他事物）提供了更通用的抽象。虽然它没有解决高效mapMfor Sets 的问题，但它允许表达对受限数据类型的遍历：

import Control.Lens.Traversal
import Data.Traversable (traverse)
import Data.Set (Set)
import qualified Data.Set as Set

-- forall f. Applicative f => (a -> f b) -> Set a -> f (Set b)
setTraversal :: (Ord b) => Traversal (Set a) (Set b) a b
setTraversal f = (fmap Set.fromList) . traverse f . Set.toList

main = do
    print $ mapMOf setTraversal (\x -> [x+1, x-1]) $ Set.fromList [0, 10, 20]

请注意，文档Set.toList说它需要进行列表融合。运气好的话（取决于所讨论的应用程序），中间列表可能会被融合掉。

于 2012-12-05T21:00:00.647 回答