haskell - Catamorphisms for Church-encoded lists -

i want able use cata recursion-schemes package lists in church encoding.

type list1 = forall b . (a -> b -> b) -> b -> b 

i used second rank type convenience, don't care. feel free add newtype, use gadts etc if feel necessary.

the idea of church encoding known , simple:

three :: -> -> -> list1  3 b c = \cons nil -> cons $ cons b $ cons c nil 

basically "abstract unspecified" cons , nil used instead of "normal" constructors. believe can encoded way (maybe, trees etc)

it's easy show list1 indeed isomorphic normal lists:

tolist :: list1 -> [a] tolist f = f (:) []  fromlist :: [a] -> list1 fromlist l = \cons nil -> foldr cons nil l 

so it's base functor same of lists, , should possible implement project , use machinery recursion-schemes.

but couldn't, question "how do that?"

since cannot pattern-match, have use fold deconstruct top level. write fold-based project normal lists:

decons2 :: [a] -> prim [a] [a] decons2 l = foldr f nil l     f h nil = cons h []     f h (cons hh t) = cons h $ hh : t 

however failed adapt church-encoded lists:

-- decons3 :: list1 -> prim [a] (list1 a) decons3 ff = ff f nil     f h nil = cons h $ \cons nil -> nil     f h (cons hh t) = cons h $ \cons nil -> cons hh (t cons nil) 

cata has following signature:

cata :: foldable f => (base f -> a) -> f -> 

to use lists, need:

1. to declare base functor type list using type family instance base (list1 a) = prim [a]
2. to implement instance foldable (list a) project = ...

i fail @ both steps

the newtype wrapper turned out crucial step missed. here code along sample catamorphism recursion-schemes.

{-# language typefamilies, rank2types #-}  import prelude hiding (foldable) import data.functor.foldable  3 :: -> -> -> list1 3 b c = list1 $ \cons nil -> cons $ cons b $ cons c nil  tolist f = f (:) []  fromlist :: [a] -> list1 fromlist l = list1 $ \cons nil -> foldr cons nil l  newtype list1 = list1 { unlist1 :: forall b . (a -> b -> b) -> b -> b }  type instance base (list1 a) = prim [a]  instance foldable (list1 a)     project ff = unlist1 ff f nil         f h nil = cons h $ list1 $ \cons nil -> nil         f h (cons hh t) = cons h $ list1 $ \cons nil -> cons hh (unlist1 t cons nil)  len x = cata phi x     phi nil = 0     phi (cons _ b) = b + 1