[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]
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
More information about the Haskell-Cafe
mailing list