haskell - 可折叠的 IntSet

Question

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

我的实际意图是使用 find在 IntSet .
如何实现 Data.IntSet 的查找?

Answer 1

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

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 :: *

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

但我想补充一点， Foldable 的存在版本其中 IntSet可以实例化(和 we actually did this in our library 并且之前使用 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):

你不能实现 find :: (a -> Bool) -> IntSet -> Maybe a因为 a类型变量。你能回答问题«什么是 a ?»? IntSet不是多态容器。它仅包含 Int s。所以你可以实现的最大值是 find :: (Int -> Bool) -> IntSet -> Maybe Int .并且没有有效的方法来实现这个功能，只能通过转换 IntSet像这样列出:

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