Как компилятор определяет фиксированную точку функтора и как работает cata на уровне листьев?

Question

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

Например, если я определю,согласно книге «Теория категорий для программистов» - стр. 359, следующая алгебра

-- (Int, LiftF e Int -> Int)

data ListF e a = NilF | ConsF e a

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) -> n + 1
lenAlg NilF = 0

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

cata lenAlg :: [e] -> Int
cata lenAlg = lenAlg . fmap (cata lenAlg) . unFix

У меня есть две путаницы.Во-первых, как компилятор Haskell узнает, что List является THE фиксированной точкой ListF?Концептуально я знаю, что это так, но как узнает компилятор, то есть что, если мы определим другой List, который будет таким же, как List, могу поспорить, что компилятор автоматически не делает вывод, что List 'тоже является фиксированной точкой ListF, или делаетЭто?(Я был бы удивлен).

Во-вторых, из-за рекурсивной природы cata lenAlg, он всегда пытается разблокировать внешний слой конструктора данных, чтобы показать внутренний слой функтора (это моя интерпретация дажеправильно кстати?).Но что, если мы уже находимся на листе, как мы можем вызвать этот вызов функции?

fmap (cata lenAlg) Nil

В качестве примера, может ли кто-нибудь помочь написать трассировку выполнения для пояснения вызова ниже функции?

cata lenAlg Cons 1 (Cons 2 Nil)

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

---

Краткое содержание ответа

---

@ nm ответил на мой первый вопрос, указав, что для того, чтобы компилятор Haskell выяснил, что Functor A является фиксированной точкой Functor B, нам нужно быть явными.В этом случае это

type List e = Fix (ListF e)

@ luqui и @Will Ness указали, что вызов fmap (cata lenAlg) на листе, который в данном случае является NilF, вернет NilF назад, из-за определенияof fmap.

-- f :: a -> b
fmap f (ConsF e a) = ConsF e (f b)
fmap f NilF        = NilF

Я бы принял ответ @ nm, так как он непосредственно касался моего первого (большего) вопроса, но мне нравятся все три ответа.Большое спасибо за вашу помощь!

Answer 1

Единственный способ, которым компилятор может узнать об отношениях между ListF e и [e], - это если вы скажете это.Вы не предоставили достаточно контекста, чтобы ответить, как именно, но я могу сделать вывод, что unFix имеет тип

unFix :: [e] -> ListF e [e]

, то есть он развертывает верхний слой.unFix может быть более общим, например, в recursion-schemes семейство типов используется для связи типов данных с их основными функторами.Но это то, где оба типа связаны.

---

Что касается вашего второго вопроса, вам нужно прояснить, когда у вас есть список и когда у вас есть ListF.Они совершенно разные.

fmap (cata lenAlg) Nil

Здесь функтор, который вы отображаете, это ListF e для того, что вам нравится e.То есть, это fmap:

fmap :: (a -> b) -> ListF e a -> ListF e b

Если вы реализуете instance Functor (ListF e) самостоятельно (всегда хорошее упражнение) и получаете его для компиляции, вы обнаружите, что Nil должен отображаться на Nilтак что cata lenAlg не имело значения вообще.

---

Давайте посмотрим на тип Cons 1 (Cons 2 Nil):

Nil                 :: ListF e a
Cons 2 Nil          :: ListF Int (ListF e a)
Cons 1 (Cons 2 Nil) :: ListF Int (ListF Int (ListF e a))

Что-то здесь не так.Проблема в том, что мы забываем сделать обратное unFix, чтобы свернуть ListF обратно в обычный список.Я назову эту функцию

roll :: ListF e [e] -> [e]

Теперь у нас есть

Nil                                      :: ListF e a
roll Nil                                 :: [e]
Cons 2 (roll Nil)                        :: ListF Int [Int]
roll (Cons 2 (roll Nil))                 :: [Int]
Cons 1 (roll (Cons 2 (roll Nil)))        :: ListF Int [Int]
roll (Cons 1 (roll (Cons 2 (roll Nil)))) :: [Int]

Типы остаются хорошими и маленькими, это хороший знак.Для трассировки выполнения отметим unFix . roll = id, однако они работают.Здесь важно отметить, что

fmap f (Cons a b) = Cons a (f b)
fmap f Nil        = Nil

То есть fmap на ListF просто применяет функцию к "рекурсивной части" типа.

Я собираюсьпереключите случай Cons на lenAlg (ConsF e n) = 1 + n, чтобы сделать трассировку чуть более читабельной.Все еще какая-то путаница, удачи.

cata lenAlg (roll (Cons 1 (roll (Cons 2 (roll Nil)))))
(lenAlg . fmap (cata lenAlg) . unFix) (roll (Cons 1 (roll (Cons 2 (roll Nil)))))
lenAlg (fmap (cata lenAlg) (unFix (roll (Cons 1 (roll (Cons 2 (roll Nil)))))))
lenAlg (fmap (cata lenAlg) (Cons 1 (roll (Cons 2 (roll Nil)))))
lenAlg (Cons 1 (cata lenAlg (roll (Cons 2 (roll Nil)))))
1 + cata lenAlg (roll (Cons 2 (roll Nil)))
1 + (lenAlg . fmap (cata lenAlg) . unFix) (roll (Cons 2 (roll Nil)))
1 + lenAlg (fmap (cata lenAlg) (unFix (roll (Cons 2 (roll Nil)))))
1 + lenAlg (fmap (cata lenAlg) (Cons 2 (roll Nil)))
1 + lenAlg (Cons 2 (cata lenAlg (roll Nil)))
1 + 1 + cata lenAlg (roll Nil)
1 + 1 + (lenAlg . fmap (cata lenAlg) . unFix) (roll Nil)
1 + 1 + lenAlg (fmap (cata lenAlg) (unFix (roll Nil)))
1 + 1 + lenAlg (fmap (cata lenAlg Nil))
1 + 1 + lenAlg Nil
1 + 1 + 0
2

См. Также мой другой ответ о катаморфизмах.

Answer 2

«Список - это фиксированная точка ListF» - это быстрое и свободное выражение речи.В то время как быстрые и беспристрастные рассуждения морально верны , вам всегда нужно помнить скучную правильную вещь.Что выглядит следующим образом:

любая минимальная точка фиксирования ListF e изоморфна [e].

Теперь «компилятор» (это быстро и свободно)Слово «язык Хаскеля», кстати) не знает об изоморфизмах такого рода.Вы можете писать изоморфные типы весь день

data []    x = []   | (:)   x ([]    x)    -- the imaginary built-in definition of []
data ListA x = NilA | ConsA x (ListA x)
data ListB x = NilB | ConsB x (ListB x)
data ListC x = NilC | ConsC x (ListC x)

, и компилятор никогда не будет обрабатывать их как "один и тот же тип".Также он не будет знать, что точка фиксации ListF e такая же, как [e], или, действительно, точка фиксации.Если вы хотите использовать эти изоморфизмы, вам нужно рассказать о них компилятору, написав некоторый код (например, определив экземпляры Data.Types.Isomorphic), а затем явно указав изоморфизм каждый раз, когда вы захотите его использовать!

Имея это в виду, давайте посмотрим на cata вы определили.Первое, что бросается в глаза, это то, что попытка определить сигнатуру типа является синтаксической ошибкой.Давайте удалим его и просто определим функцию в GHCi (я изменил имя параметра на f, чтобы избежать путаницы, и исправил несколько опечаток в определении ListF)

Main> data ListF e a = NilF | ConsF e a
Main> let lenAlg :: ListF e Int -> Int
Main|     lenAlg (ConsF e n) = n + 1
Main|     lenAlg NilF = 0
Main|
Main>
Main> :m + Data.Fix
Main Data.Fix> cata f = f . fmap (cata f) . unFix
Main Data.Fix> :t cata
cata :: Functor f => (f b -> b) -> Fix f -> b
Main Data.Fix> :t cata lenAlg
cata lenAlg :: Functor (ListF e) => Fix (ListF e) -> Int

Это говорит о том, что вЧтобы использовать lenAlg, вам необходимо:

• определить экземпляр Functor для ListF e
• использовать Fix (ListF e) (то есть a Fixpoint ListF) явно.Желание «фиксированной точки ListF» к существованию просто не работает.В этом нет никакой магии.

Итак, давайте сделаем это:

Main Data.Fix> instance Functor (ListF e) where
Main Data.Fix|     fmap f NilF = NilF
Main Data.Fix|     fmap f (ConsF e a) = ConsF e (f a)
Main Data.Fix>
Main Data.Fix> :t cata lenAlg
cata lenAlg :: Fix (ListF e) -> Int

Отлично, теперь мы можем вычислить длину списка, основанного на FixF, на основе ListF.Но давайте сначала определим несколько определений помощников.

Main Data.Fix> type List e = Fix (ListF e)
Main Data.Fix> nil = Fix (NilF)
Main Data.Fix> let infixr 7 ~~                   -- using an infix operator for cons
Main Data.Fix|     h ~~ t = Fix (ConsF h t)
Main Data.Fix|
Main Data.Fix>
Main Data.Fix> myList = (1::Int) ~~ 2 ~~ 3 ~~ 4 ~~ nil
Main Data.Fix> :t myList
myList :: Fix (ListF Int)

Вот наш «список» (точнее, член типа, изоморфного [Int]).Давайте cata lenAlg это:

Main Data.Fix> cata lenAlg myList
4

Успех!

Итог: компилятор ничего не знает, вам нужно все это объяснить.

Answer 3

Нет, unFix предоставляет структуру, а затем fmap f применяет к ней функцию f.Если это лист, fmap f сделает то, что определено для листьев, то есть ничего.Это fmap, который «знает», т. Е. Определен для обработки каждого случая, как обычно в определениях на основе случая в Haskell.

Fix (ListF e) = ListF e (Fix (ListF e)) 
              = NilF | ConsF e (Fix (ListF e))

, поэтому переименование Fix (ListF e) в Listof e дает

Listof     e  = NilF | ConsF e (Listof e) 

Listof e рекурсивный тип.ListF e r нерекурсивный тип. Fix делает из него рекурсивный тип.ListF e, будучи Функтором, означает, что fmap работает с r "мясом", ListF e является "твердой внешней оболочкой" этого "фрукта".

data ListF e a = NilF | ConsF e a

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

-- unFix ::    Fix f          -> f       (Fix f        )
-- unFix (_ :: Fix (ListF e)) :: ListF e (Fix (ListF e))

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) = n + 1
lenAlg NilF        = 0

instance Functor (ListF e) where
    -- fmap :: (a -> b) -> (ListF e a) -> (ListF e b)
    fmap f NilF        = NilF
    fmap f (ConsF e r) = ConsF e (f r)

cata :: (ListF e Int -> Int) -> Fix (ListF e) -> Int
cata lenAlg x = (lenAlg . fmap (cata lenAlg) . unFix) x
              =  lenAlg ( fmap (cata lenAlg) ( unFix  x ))
--------
        x       ::       Fix (ListF e)
        unFix x ::            ListF e (Fix (ListF e))
        fmap (cata lenAlg) :: ListF e (Fix (ListF e)) -> ListF e (Int)
              cata lenAlg  ::          Fix (ListF e)  ->          Int

        fmap (cata lenAlg)   (unFix  x              ) :: ListF e  Int 
 lenAlg (_                                            :: ListF e  Int ) :: Int

Видите?Все провода идут на свои места.fmap преобразует внутреннюю часть r рекурсивно, а затем lenAlg алгебра применяет одно последнее преобразование, одно последнее шаг в разрушении структуры, где все ее внутренние части уже были свернуты в r ecursive r результат.Таким образом, получая окончательный результат r .

---

В качестве конкретного примера, для списка из двух чисел, 1 и 2 ,у нас есть

-- newtype Fix f  = X { unFix :: (f      (Fix f         )) }
--             _\_______       ____\____      _\________
onetwo :: Fix (ListF Int) -- ~ ListF Int (Fix (ListF Int))
onetwo = X (ConsF 1
                  (X (ConsF 2
                            (X NilF))))

cata lenAlg :: Fix (ListF e) -> Int
cata lenAlg    onetwo
  = {- definition of cata   -}
    lenAlg . fmap (cata lenAlg) . unFix  $ onetwo
  = {- definition of onetwo -}
    lenAlg . fmap (cata lenAlg) . unFix  $ 
                           X (ConsF 1 (X (ConsF 2 (X NilF))))
  = {- definition of unFix  -}
    lenAlg . fmap (cata lenAlg) $ 
                              ConsF 1 (X (ConsF 2 (X NilF)))
  = {- definition of fmap   -}
    lenAlg $ ConsF 1 (cata lenAlg     (X (ConsF 2 (X NilF))))
  = {- definition of lenAlg -}
    (+ 1)  $          cata lenAlg     (X (ConsF 2 (X NilF)))
  = {- definition of cata   -}
    (+ 1)  $ lenAlg . fmap (cata lenAlg) . unFix $ 
                                       X (ConsF 2 (X NilF))
  = {- definition of unFix  -}
    (+ 1) $ lenAlg . fmap (cata lenAlg) $ ConsF 2 (X NilF)
  = {- definition of fmap   -}
    (+ 1) $ lenAlg $ ConsF 2 $ cata lenAlg        (X NilF)
  = {- definition of lenAlg -}
    (+ 1) $ (+ 1)  $           cata lenAlg        (X NilF)
  = {- definition of cata   -}
    (+ 1) $ (+ 1)  $ lenAlg . fmap (cata lenAlg) . unFix $ 
                                                  (X NilF)
  = {- definition of unFix  -}
    (+ 1) $ (+ 1)  $ lenAlg . fmap (cata lenAlg) $   NilF
  = {- definition of fmap   -}
    (+ 1) $ (+ 1)  $ lenAlg $                        NilF
  = {- definition of lenAlg -}
    (+ 1) $ (+ 1)  $ 0
  = (+ 1) $ 1
  = 2

Также

squaringAlg :: ListF Int [Int] -> [Int]
squaringAlg (ConsF e r) = e*e : r
squaringAlg NilF        = []

filteringAlg :: (e -> Bool) -> ListF e [e] -> [e]
filteringAlg p (ConsF e r) | p e       = e : r
                           | otherwise = r
filteringAlg _ NilF                    = []

и т. д.