Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Churches all the way down

Увидел, как выглядит алгебра в кодировке чёрча для списка в кодировке Чёрча.
{-# LANGUAGE TypeFamilies, Rank2Types, DeriveFunctor #-}

import Prelude hiding (Foldable)
import Data.Functor.Foldable

three :: a -> a -> a -> List1 a
three a b c = List1 $ \cons nil -> cons a $ cons b $ cons c nil

toList f = f (:) []

fromList :: [a] -> List1 a
fromList l = List1 $ \cons nil -> foldr cons nil l

newtype List1 a = List1 { unList1 :: forall b . (a -> b -> b) -> b -> b }

newtype List1B a c = List1B { unList1B :: forall b . (a -> c -> b) -> b -> b } deriving Functor

type instance Base (List1 a) = List1B a

instance Foldable (List1 a) where
	project ff = unList1 ff f bNil where
		f h t = bCons h $ unList1B t lCons lNil

bNil = List1B $ \cons nil -> nil
bCons a b = List1B $ \cons nil -> cons a b

lNil = List1 $ \ cons nil -> nil
lCons h t = List1 $ \cons nil -> cons h (unList1 t cons nil)

len x = cata phi x where
	phi x = unList1B x (\_ b -> b + 1) 0
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