Если карта может быть определена с помощью Foldable, почему Functor не упоминается в определении Foldable

Question

Я прочитал это, map можно определить с помощью foldrэто примитивно рекурсивная функция. По крайней мере, для списков.

Теперь мой вопрос: почему Functor не является подтипом класса Foldable? И если fmap можно определить только с точки зрения foldr для списков, что делает их особенными?

Глядя на определение map со складкой:

myMap f xs = foldr step [] xs
    where step x ys = f x : ys

Я мог бы использовать моноиды, чтобы добраться до:

myMap f xs = foldr step mempty xs
    where step x ys = f x : ys

Но, к сожалению, мне не хватает волшебника на Хаскеле, чтобы сойти с рук cons,

Answer 1

Но, к сожалению, мне не хватает волшебника из Хаскелла, чтобы сойти с минусов.

Вы нашли фундаментальную проблему, которая не позволяет сделать каждый Foldable функтором; foldr отбрасывает сложенную структуру, сохраняя только (что составляет) список ее элементов. Вы не можете "сойти с минусов", потому что вы не можете знать, что структура данных дается только Foldable пример.

Учитывая это (типичное) определение дерева:

data Tree a = Bin a (Tree a) (Tree a) | Tip

instance Functor Tree where
  fmap f (Bin a l r) = Bin (f a) (fmap f l) (fmap f r)
  fmap _ Tip = Tip

instance Foldable Tree where
  foldMap f (Bin a l r) = foldMap f l <> f a <> foldMap f r
  foldMap _ Tip = mempty

Сравните эти два дерева:

let x = Bin 'b' (Bin 'a' Tip Tip) Tip
let y = Bin 'a' Tip (Bin 'b' Tip Tip)

Оба дерева имеют toList из "ab", но явно разные. Это означает, что процесс свертывания дерева теряет некоторую информацию (а именно, границу между левым поддеревом, правым поддеревом и элементом), которую вы не можете восстановить. Поскольку вы не можете различить х и у, используя результаты из Foldable Например, вы не можете написать fmap такой, что fmap id == id используя только эти методы. Нам пришлось прибегнуть к сопоставлению с образцом и использовать конструкторы для записи Functor пример.