Функторы и неиндуктивные типы

Question

Я работаю через раздел о функторах в Typeclassopedia.

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

ХОРОШО. Таким образом, функторы выглядят довольно естественно для индуктивных типов, таких как списки или деревья.

Функторы также выглядят довольно просто, если число элементов установлено на меньшее число. Например, с Возможно, вы просто должны быть обеспокоены "Ничто" или "Просто" - две вещи.

Итак, как бы вы сделали что-то вроде графа, который потенциально мог бы иметь циклы, экземпляр Functor? Я думаю, что более обобщенный способ сформулировать это так: как неиндуктивные типы "вписываются" в функторы?

---

Чем больше я думаю об этом, тем больше понимаю, что индуктивный / неиндуктивный не имеет значения. Индуктивные типы просто определить проще fmap за...

Если бы я хотел сделать граф экземпляром Functor, мне пришлось бы реализовать алгоритм обхода графа внутри fmap; например, ему, вероятно, придется использовать вспомогательную функцию, которая будет отслеживать посещенные узлы. На данный момент, я теперь задаюсь вопросом, зачем беспокоиться о том, чтобы определить его как Functor, а не просто написать это как саму функцию? Например, карта против fmap для списков...?

Я надеюсь, что кто-то с опытом, военными историями и шрамами сможет пролить свет. Спасибо!

Answer 1

Хорошо, давайте предположим, что вы определили график как это

data Graph a = Node a [Graph a]

затем fmap определяется точно так, как вы ожидаете

instance Functor Graph where
  fmap f (Node a ns) = Node (f a) (map (fmap f) ns)

Теперь, если есть петля, то мы должны были бы сделать что-то вроде

foo = Node 1 [bar]
bar = Node 2 [foo]

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

В общем, это хитрость: fmap ленив, так что вы можете рассматривать его результаты так же, как и любые неиндуктивные значения в Haskell (осторожно).

Кроме того, вы должны определить fmap против случайных других функций, так как

1. fmap хороший, хорошо известный API с правилами
2. Ваш контейнер теперь хорошо помещается с вещами, ожидающими Functors
3. Вы можете абстрагироваться от других частей вашей программы, чтобы они зависели от Functor, а не ваш график

Вообще, когда я вижу что-то, это функтор, я думаю: "Ах, замечательно, я знаю, как это использовать", и когда я вижу,

superAwesomeTraversal :: (a -> b) -> Foo a -> Foo b

Я немного волнуюсь, что это будет делать неожиданные вещи..