haskell - 可折叠的 IntSet

Question

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

我的实际意图是find在IntSet. 如何实现 find for Data.IntSet？

Answer 1

IntSet不能Foldable来自basepackage 因为它没有 kind * -> *。

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