可折叠的IntSet

Question

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

我的目的是用上find一个IntSet.我该如何实现find 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可以实例(和我们实际上在我们的图书馆这样做,这一点我们已经在做了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不是多态容器.它只包含Ints.所以你可以实现的最大值是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