Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Очередное прозрение

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

Алгебры бывают двух типов - обычные и в кодировке Чёрча. Алгебра натуральных чисел в кодировке Чёрча - это a -> (a -> a) -> a. Обычная алгебра натуральных чисел - это Maybe a -> a.

Прозрение заключается в том, что все функции, принимающие a -> (a -> a) можно отрефакторить в функции, принимающие Maybe a и наоборот. Более того, из a -> (a -> a) -> b всегда можно получить Maybe a -> b и наоборот (т.е. выходной тип не обязан быть a)

Ну и это работает для всех Х. Т.е. списочные алгебры аналогично обобщаются. Функции принимающие (a -> b -> b) эквивалентны функциям принимающим ListF a b = Cons a b | Nil (нерекурсивный базовый функтор списков)

Upd: тут подумалось что катаморфизмы не при чём. Просто тип Maybe a взаимозаменяем со своей "недочёрч-кодировкой" (b, a -> b). Аналогично тип ListF a b взаимозаменяем c (b, a -> b -> b). Ну и чёрч-кодировки нерекурсивных типов встречаются очень часто, и части тапла могут быть не рядом в списке аргументов.

Ну и море разливанное.

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

Здесь у нас затесалось data Tree = Node Tree Tree | Leaf, а точнее его базовый функтор.

Любопытное обнаружилось объяснение единственности id: это черч-кодировка бесконечного стрима юнитов, который всего один. А разные функции a -> a - это разные свёртки этого бесконечного стрима. Т.е. разные термы cata phi $ replicate () :) Как-то неправдоподобно, неужели правда
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 7 comments