Какие бифункторы, используемые для этого, не могут быть достигнуты составлением функторов?

Question

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

В качестве примера я наткнулся на этот код в "Сущности шаблона итератора " Джереми Гиббонса и Бруно К. д. С. Оливейра:

import Data.Bifunctor

data Fix s a = In {out::s a (Fix s a) }

map' :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b
map' f = In . bimap f (map' f) . out

fold' :: Bifunctor s => (s a b -> b) -> Fix s a -> b
fold' f = f . bimap id (fold' f) . out

unfold' :: Bifunctor s => (b -> s a b) -> b -> Fix s a
unfold' f = In . bimap id (unfold' f) . f

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

Answer 1

Я думаю, что вы немного обдумываете это. Бифунктор похож на двухпараметрический функтор. Идея Гиббона и Оливейры - это лишь одно применение бифункторов, точно так же, как стандартный зоопарк рекурсивных схем - это всего лишь одно применение функторов.

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d

Bifunctorс какой-то * -> * -> * и оба параметра могут быть ковариантно отображены. Сравните это с обычным Functors, которые имеют только один параметр (f :: * -> *), который может быть ковариантно нанесен на карту.

Например, подумайте о Eitherобычный Functor пример. Это позволяет только fmap по параметру второго типа - Right значения отображаются, Left ценности остаются такими, какие они есть.

instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right y) = Right (f y)

Тем не менее, его Bifunctor Экземпляр позволяет отобразить обе половины суммы.

instance Bifunctor Either where
    bimap f g (Left x) = Left (f x)
    bimap f g (Right y) = Right (g y)

Аналогично для кортежей: (,)"s Functor экземпляр позволяет сопоставить только второй компонент, но Bifunctor позволяет отображать обе части.

instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

Обратите внимание, что Maybe, который вы упомянули, не вписывается в рамки бифункторов, поскольку имеет только один параметр.

---

По вопросу о Fixфиксированная точка бифунктора позволяет вам охарактеризовать рекурсивные типы, которые имеют параметр типа функтора, такой как большинство контейнероподобных структур. Давайте использовать списки в качестве примера.

newtype Fix f = Fix { unFix :: f (Fix f) }

data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

Использование стандартного функториала Fixкак я уже говорил выше, нет общего деривации экземпляра Functor за List, так как Fix ничего не знает о List"s a параметр. То есть я не могу написать ничего подобного instance Something f => Functor (Fix f) так как Fix имеет неправильный вид. Я должен провернуть map для списков, возможно, используя cata:

map :: (a -> b) -> List a -> List b
map f = cata phi
    where phi Nil_ = Fix Nil_
          phi Cons_ x r = Fix $ Cons_ (f x) r

Бифункциональная версия Fix разрешает ли экземпляр Functor, Fix использует один из параметров бифунктора, чтобы подключить рекурсивное вхождение Fix f a и другой, чтобы заменить функториальный параметр результирующего типа данных.

newtype Fix f a = Fix { unFix :: f a (Fix f a) }

instance Bifunctor f => Functor (Fix f) where
    fmap f = Fix . bimap f (fmap f) . unFix

Итак, мы можем написать:

deriveBifunctor ''ListF

type List = Fix ListF

и получить Functor экземпляр бесплатно:

map :: (a -> b) -> List a -> List b
map = fmap

Конечно, если вы хотите работать в общем случае с рекурсивными структурами с более чем одним параметром, то вам нужно обобщить на три-функторы, квад-функторы и т. Д. Это явно не устойчиво и требует много работы (в более сложных программах языки) был заложен в разработку более гибких систем для характеристики типов.