And is this Haskell?
June 30th, 2009 by Conor
> {-# OPTIONS_GHC -F -pgmF she #-}
> {-# LANGUAGE TypeOperators #-}
> module Fix where
> data Fix f = In (f (Fix f))
> newtype (:+:) f g x = Plus (Either (f x) (g x))
> newtype (:*:) f g x = Times (f x, g x)
> newtype K a x = K a
> newtype I x = I x
> type ListF x = K () :+: (K x :*: I)
> type List x = Fix (ListF x)
> pattern NilF = Plus (Left (K ()))
> pattern ConsF x xs = Plus (Right (Times (K x, I xs)))
> pattern Nil = In NilF
> pattern Cons x xs = In (ConsF x xs)
> foldFix :: Functor f => (f t -> t) -> Fix f -> t
> foldFix phi (In xs) = phi (fmap (foldFix phi) xs)
> (+++) :: List x -> List x -> List x
> xs +++ ys = foldFix phi xs where
> phi NilF = ys
> phi (ConsF x xs) = Cons x xs
> blat :: List x -> [x]
> blat = foldFix phi where
> phi NilF = []
> phi (ConsF x xs) = x : xs
> talb :: [x] -> List x
> talb = foldr Cons Nil
> instance (Functor f, Functor g) => Functor (f :+: g) where
> fmap p (Plus (Left fx)) = Plus (Left (fmap p fx))
> fmap p (Plus (Right gx)) = Plus (Right (fmap p gx))
> instance (Functor f, Functor g) => Functor (f :*: g) where
> fmap p (Times (fx, gx)) = Times (fmap p fx, fmap p gx)
> instance Functor (K a) where
> fmap p (K a) = K a
> instance Functor I where
> fmap p (I a) = I (p a)
I’ve pushed some patches, and now it is!