可折叠的IntSet [英] Foldable IntSet

问题描述

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

For me, an integer set seems to be a foldable data structure. Why is Data.IntSet not an instance of Foldable?

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

My actual intention is to use find on an IntSet. How can I implement find for Data.IntSet?

推荐答案

IntSet不能从base包中作为Foldable，因为它没有种类* -> *.

IntSet can't be Foldable from base package because it doesn't have 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 :: *

简单来说，要成为base中Foldable的实例，您的数据类型应通过某种类型变量进行参数设置.如果要对IntSet使用某些操作，则应使用实现了所有专用版本的Data.IntSet模块中的某些功能.

In simple words, to be instance of Foldable from base you data type should be parametrized by some type variable. If you want to use some operation on IntSet you should use some function from Data.IntSet module where all specialized versions implemented.

但是我想补充一下，存在Foldable的版本，它可以实例化IntSet(和

But I want to add that there exist version of Foldable which IntSet can instantiate (and we actually did this in our library and this was done earlier with MonoFoldable). You just need to implement your abstractions properly:

{-# 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不是多态容器.它仅包含Int.因此，您可以实现的最大值是find :: (Int -> Bool) -> IntSet -> Maybe Int.而且，仅通过将IntSet转换为这样的列表，就没有有效的方法来实现此功能:

You can't implement find :: (a -> Bool) -> IntSet -> Maybe a because of a type variable. Can you answer question «What is a?»? IntSet is not polymorphic container. It contains only Ints. So maximum you can implement is find :: (Int -> Bool) -> IntSet -> Maybe Int. And there's no efficient way to implement this function, only by converting IntSet to list like this:

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！