Skip to content

Instantly share code, notes, and snippets.

@nvanderw
Last active August 29, 2015 14:00
Show Gist options
  • Save nvanderw/11004767 to your computer and use it in GitHub Desktop.
Save nvanderw/11004767 to your computer and use it in GitHub Desktop.
Something catamorphism-like?
newtype Fix f = Fix (f (Fix f))
-- Define List as the fixed point of a type operator
data ListR a t = Nil | Cons a t
type List a = Fix (ListR a)
-- The type operator ListR represents "one layer" of the structure
-- of List. We can do something fold-like with it.
-- My question is, is there a name for f? It's like a catamorphism
-- but doesn't recurse into the data.
f :: ListR a t -> b -> (a -> t -> b) -> b
f Nil n _ = n
f (Cons x xs) _ c = c x xs
-- We can use f to define an actual catamorphism.
fold :: List a -> b -> (a -> b -> b) -> b
fold (Fix xs) n c = f xs n $ \y ys -> c y $ fold ys n c
-- Misc. utilities for playing with the "List" type
---------------------------------------------------
(<<<=) = (.) . (.)
fromList :: [a] -> List a
fromList = foldr (Fix <<<= Cons) (Fix Nil)
toList :: List a -> [a]
toList xs = fold xs [] (:)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment