Пример Foldable, который не является Functor (или не Traversable)?

A Foldable экземпляр, скорее всего, будет своего рода контейнером, и, скорее всего, это будет Functor. Действительно, это говорит

A Foldable type также является контейнером (хотя класс технически не требует Functor, интересным Foldable являются все Functor s).

Итак, есть пример Foldable, который, естественно, не является Functor или Traversable? (который, возможно, пропустил вики-страница Haskell:-))

Ответ 1

Здесь полностью параметрический пример:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird не является Functor, потому что a происходит в отрицательном положении.

Ответ 2

Вот простой пример: Data.Set.Set. Посмотрите сами.

Причина этого должна быть очевидна, если вы исследуете типы специализированных функций fold и map, определенных для Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

Поскольку структура данных основывается на двоичном дереве поиска внутри, для элементов требуется ограничение Ord. Functor экземпляры должны допускать любой тип элемента, поэтому он не является жизнеспособным, увы.

Складка, с другой стороны, всегда разрушает дерево для получения суммарного значения, поэтому нет необходимости сортировать промежуточные результаты складки. Даже если складка фактически создает новый Set, ответственность за удовлетворение ограничения Ord лежит на функции накопления, переданной в складку, а не самой складки.

То же самое, вероятно, применимо к любому типу контейнера, который не является полностью параметрическим. И учитывая полезность Data.Set, это делает замечание, которое вы цитируете о "интересном" Foldable, кажется немного подозрительным, я думаю!

Ответ 3

Чтение Красивая складка Я понял, что любой Foldable можно сделать Functor, обернув его в

data Store f a b = Store (f a) (a -> b)

с простым интеллектуальным конструктором:

store :: f a -> Store f a a
store x = Store x id

(Это всего лишь вариант типа Store comonad.)

Теперь мы можем определить

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

Таким образом, мы можем сделать как Data.Set.Set, так и Sjoerd Visscher Weird функтором. (Тем не менее, поскольку структура не запоминает свои значения, многократно складывающиеся над ней могут быть очень неэффективными, если функция, которую мы использовали в fmap, является сложной.)

Обновление: Это также дает пример структуры, которая является функтором, сгибаемой, но не проходящей. Чтобы сделать Store доступным, нам нужно сделать (->) r доступным. Поэтому нам нужно реализовать

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

Возьмем Either b для f. Тогда нам нужно будет реализовать

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

Ясно, что такой функции нет (вы можете проверить с помощью Djinn). Поэтому мы не можем реализовать sequenceA.