Как использовать экземпляры Functor с типами Fix

Question

Допустим, я хочу иметь очень общий ListF тип данных:

{-# LANGUAGE GADTs, DataKinds #-}

data ListF :: * -> * -> * where
  Nil  ::           List a b
  Cons :: a -> b -> List a b

Теперь я могу использовать этот тип данных с Data.Fix построить F-алгебру

import qualified Data.Fix as Fx

instance Functor (ListF a :: * -> *) where
  fmap f (Cons x y) = Cons x (f y)
  fmap _ Nil        = Nil

sumOfNums = Fx.cata f (Fx.Fix $ Cons 2 (Fx.Fix $ Cons 3 (Fx.Fix $ Cons 5 (Fx.Fix Nil))))
  where
    f (Cons x y) = x + y
    f Nil        = 0

Но как я могу использовать этот очень общий тип данных ListF создать то, что я считаю по умолчанию Functor экземпляр для рекурсивных списков (отображение каждого значения в списке)

Я думаю, что я мог бы использовать Bifunctor (отображение на первое значение, обход второго), но я не знаю, как это могло бы работать с Data.Fix.Fix?

Answer 1

Совершенно верно построить рекурсивный функтор, взяв точку фиксирования бифунктора, потому что 1 + 1 = 2. Структура узла списка задается в виде контейнера с 2 видами подструктуры: "элементы" и "подсписки".

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

type p -:> q = forall i. p i -> q i

class FunctorIx (f :: (i -> *) -> (o -> *)) where
  mapIx :: (p -:> q) -> f p -:> f q

Это функторы на индексированных множествах, поэтому имена - это не просто дань уважения Госчинному и Удерзо. Вы можете думать о o как "виды структуры" и i как "виды субструктуры". Вот пример, основанный на том факте, что 1 + 1 = 2.

data ListF :: (Either () () -> *) -> (() -> *) where
  Nil  :: ListF p '()
  Cons :: p (Left '()) -> p (Right '()) -> ListF p '()

instance FunctorIx ListF where
  mapIx f Nil        = Nil
  mapIx f (Cons a b) = Cons (f a) (f b)

Чтобы использовать выбор сортировки по подструктурам, нам понадобится своего рода анализ случаев на уровне типов. Мы не можем уйти с функцией типа, как

1. нам нужно, чтобы это было применено частично, а это не разрешено;
2. нам нужно немного во время выполнения, чтобы сказать нам, какой сорт присутствует.

data Case :: (i -> *) -> (j -> *) -> (Either i j -> *)  where
  CaseL :: p i -> Case p q (Left i)
  CaseR :: q j -> Case p q (Right j)

caseMap :: (p -:> p') -> (q -:> q') -> Case p q -:> Case p' q'
caseMap f g (CaseL p) = CaseL (f p)
caseMap f g (CaseR q) = CaseR (g q)

И теперь мы можем взять точку исправления:

data Mu :: ((Either i j -> *) -> (j -> *)) ->
           ((i -> *) -> (j -> *)) where
  In :: f (Case p (Mu f p)) j -> Mu f p j

В каждой позиции подструктуры мы делаем разделение случая, чтобы увидеть, должны ли мы иметь p-элемент или Mu f p подструктуры. И мы получаем его функционал.

instance FunctorIx f => FunctorIx (Mu f) where
  mapIx f (In fpr) = In (mapIx (caseMap f (mapIx f)) fpr)

Чтобы построить списки из этих вещей, нам нужно переключаться между * а также () -> *,

newtype K a i = K {unK :: a}

type List a = Mu ListF (K a) '()
pattern NilP :: List a
pattern NilP       = In Nil
pattern ConsP :: a -> List a -> List a
pattern ConsP a as = In (Cons (CaseL (K a)) (CaseR as))

Теперь для списков мы получаем

map' :: (a -> b) -> List a -> List b
map' f = mapIx (K . f . unK)

Answer 2

Я думаю, я мог бы использовать Bifunctor (отображение первого значения, обход второго), но я не знаю, как это могло бы работать с Data.Fix.Fix?

В точку.

bifunctors пакет содержит Fix -for-bifunctors", который выглядит следующим образом:

newtype Fix f a = In { out :: f (Fix f a) a }

Fix f это Functor всякий раз, когда f это Bifunctor, fmap рекурсивно fmaps fПервый параметр и отображение второго.

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

Так что ваши List Пример будет выглядеть так:

data ListF r a = Nil | Cons r a

type List = Fix ListF

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