Складной 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 может создать экземпляр (и мы фактически сделали это в нашей библиотеке, и это было сделано ранее с 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