Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Дальнейшая кметтификация кода Кметта

Легко видеть™, что алгебра в катаморфизме из recursion-schemes - это в точности профунктор Сostar из profunctors. Коалгебра в анаморфизме - соответственно Star.

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

Интересно отрезать хаки с project/embed/Base и посмотреть, что ещё интересного профункторность нам готовит.
{-# LANGUAGE LambdaCase, FlexibleContexts, NoMonomorphismRestriction #-}
module Main where

import Data.Profunctor
import Data.Functor.Foldable

type Coalgebra t a = Star (Base t) a a
type Algebra t a = Costar (Base t) a a

class Functor (Base t) => R t where
    projectR :: Coalgebra t t

type CataR t a = Algebra t a -> t -> a

cataR :: R t => CataR t a
cataR f = c where c = runCostar (lmap c f) . runStar projectR

instance R [a] where
    projectR = Star $ \case
        a : b -> Cons a b
        [] -> Nil

sumR = Costar $ \case
    Cons a b -> a + b
    Nil -> 0

main = print $ (42::Int) == cataR sumR [40, 2]
Tags: fp, haskell, 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.
  • 21 comments