可折叠 IntSet

Question

对我来说，整数集似乎是一种可折叠的数据结构。为什么 Data.IntSet 不是 Foldable 的实例？

我的实际意图是在 IntSet 上使用 find。如何为 Data.IntSet 执行查找？

Answer 1

IntSet 不能来自 base 包 Foldable 因为它没有类型 * -> *.

ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
ghci> :k Foldable
Foldable :: (* -> *) -> Constraint
ghci> import Data.IntSet (IntSet)
ghci> :k IntSet
IntSet :: *

简单来说，要成为 base 中 Foldable 的实例，您的数据类型应该由某个类型变量参数化。如果你想在 IntSet 上使用一些操作，你应该使用 Data.IntSet 模块中的一些函数，其中实现了所有专用版本。

但我想补充一点，存在 Foldable 版本，IntSet 可以实例化（和 we actually did this in our library and this was done earlier with MonoFoldable）。你只需要正确地实现你的抽象：

{-# LANGUAGE TypeFamilies #-}

type family Element t
type instance Element (f a)  = a
type instance Element Text   = Char
type instance Element IntSet = Int

class ProperFoldable t where
    foldr :: (Element t -> b -> b) -> b -> t -> b

更新（按要求添加find）：

由于 a 类型变量，您无法实现 find :: (a -> Bool) -> IntSet -> Maybe a。你能回答“a 是什么？”这个问题吗？ IntSet 不是多态容器。它只包含 Ints。因此，您可以实施的最大值是 find :: (Int -> Bool) -> IntSet -> Maybe Int。而且这个功能也没有高效的实现方式，只能将IntSet转成这样的list：

import           Data.Foldable (find)
import           Data.IntSet (IntSet)
import qualified Data.IntSet as IS

intSetFind :: (Int -> Bool) -> IntSet -> Maybe Int
intSetFind predicate = find predicate . IS.elems

可折叠 IntSet

Foldable IntSet

haskell

set

foldable