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

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

50 голосов
/ 02 декабря 2011
Экземпляр

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

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

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

Ответы [ 3 ]

52 голосов
/ 02 декабря 2011

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

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

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

Weird не является Functor, поскольку a находится в отрицательной позиции.

49 голосов
/ 02 декабря 2011

Вот простой пример: 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, кажется немного подозрительным, я думаю!

24 голосов
/ 15 октября 2012

Чтение Красивое складывание Я понял, что любой 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's 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.

...