Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Categories:

build/foldr fusion, catamorphisms and algebras

Продолжаю описание зоопарка списков в Хаскеле. Бессистемно - сначала хотя бы описать все, а таксономию потом наведём.
-- toChurch l k z = foldr k z l
-- fromChurch g = g (:) []
Катаморфизмы кодировки Чёрча можно записать в "модной" форме через алгебры. Она более удобна, потому что вместо переменного количества аргументов (по одному на конструктор) у нас всегда один аргумент-алгебра:
toAlgebraicChurch l algebra = cata algebra l
fromAlgebraicChurch g = g embed
toAlgebraicChurch . fromAlgebraicChurch = id
Любопытно, что а) сразу получилось обобщение фьюжена на произвольные типы; б) стал понятен физический смысл embed - это выделенная алгебра, декодирующая нашу кодировку Чёрча.

Из любопытства заинлайнил from/to, чтобы получить правило фьюжена в форме cata/build', близкой к foldr/build:
toAlgebraicChurch . fromAlgebraicChurch = id
toAlgebraicChurch (fromAlgebraicChurch g) = g
toAlgebraicChurch (g embed) = g
(\algebra -> cata algebra (g embed)) = g
cata algebra (g embed) = g algebra
cata algebra (build' g) = g algebra
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.
  • 0 comments