[Haskell-cafe] Fun with type functions

[Hugo Pacheco]

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]
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.

cheers,
hugo

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
>



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