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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- www.di.uminho.pt/~hpacheco