haskell - 可折叠的IntSet

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

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

最佳答案

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

UPDATE（通过请求添加find）：

由于find :: (a -> Bool) -> IntSet -> Maybe a类型变量，您无法实现a。您能否回答“什么是a？”问题？ IntSet不是多态容器。它仅包含Int。因此，您可以实现的最大值是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