[Haskell-cafe] Fun with type functions

Hugo Pacheco hpacheco at gmail.com
Fri Dec 5 18:18:37 EST 2008

Pointless Haskell a library for point-free programming with recursion
patterns that uses type synonym families to provide a view of data types as
the fixed points of  functors.
It defines two type functions

type family PF a :: * -> *             -- returns the pattern functor for a
data type
type family Rep (f :: * -> *) x :: *  -- returns the result type of applying
a functor to a type argument

that can be combined to derive the structurally equivalent sum of products
for some type:

type F a x = Rep (PF a) x

class Mu a where
    inn :: F a a -> a
    out :: a -> F a a

For Haskell polymorphic lists, we need to define:

type instance PF [a] = Const One :+: Const a :*: Id

instance Mu [a] where
    inn (Left _) = []
    inn (Right (x,xs)) = x:xs
    out [] = Left _L
    out (x:xs) = Right (x,xs)

Some of the typical recursion patterns are:

hylo :: Functor (PF b) => b -> (F b c -> c) -> (a -> F b a) -> a -> c
cata :: (Mu a,Functor (PF a)) => a -> (F a b -> b) -> a -> b
ana :: (Mu b,Functor (PF b)) => b -> (a -> F b a) -> a -> b

One simple example is the foldr (catamorphism) for calculating the lenght of
a list:

length :: [a] -> Int
length = cata (_L::[a]) f
    where f = zero \/ succ . snd

> length [1,2,3,4]

I have promoted the library into a cabal package (pointless-haskell) today
and am creating an homepage (
http://haskell.di.uminho.pt/wiki/Pointless+Haskell) with examples.


On Thu, Nov 27, 2008 at 9:29 AM, Simon Peyton-Jones
<simonpj at microsoft.com>wrote:

> Friends
> GHC has embodied data type families since 6.8, and now type synonym
> families (aka type functions) in 6.10.  However, apart from our initial
> papers there isn't much published material about how to *use* type families.
>  But that hasn't stopped you: quite a few people are using them already, and
> of course there is a rich seam of work on using functional dependencies to
> express type-level computation.
> Ken Shan and Oleg Kiselyov and I are collaborating to write a paper for an
> upcoming workshop, under the general rubric of "Fun with type functions" (in
> homage to Thomas Hallgren's paper "Fun with functional dependencies" and
> Ralf Hinze's paper "Fun with phantom types").
> So this message is to ask you:
>        can you tell us about the most persuasive, fun application
>        you've encountered, for type families or functional dependencies?
> Simple is good.  It doesn't have to be elaborate: just something that does
> something useful you could not have done otherwise.  Pointers to email
> threads are fine.  Don't assume we already know about them (even if we
> participated in the thread :-)  Part of what we're interested in is that
> *you* found the example compelling.
> Many thanks
> Simon, Ken, Oleg
> PS: I'm broadcasting this message to GHC-users and Haskell-cafe, but to
> avoid deluging ghc-users, please reply just to us and Haskell cafe.
>  (Interested ghc-users can follow the threads there from the archives if
> they want.)
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081205/8b572235/attachment.htm

More information about the Haskell-Cafe mailing list