Pointless Haskell&nbsp;<span class="Apple-style-span" style="font-family: -webkit-sans-serif; line-height: 19px; ">a library for point-free&nbsp;programming with recursion patterns that&nbsp;</span>uses type synonym families to provide a view of data types as the fixed points of &nbsp;functors.<div>
<br></div><div>It defines two type functions</div><div><br></div><div>type family PF a :: * -&gt; * &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; -- returns the pattern functor for a data type</div><div>type family Rep (f :: * -&gt; *) x :: * &nbsp;-- returns the result type of applying a functor to a type argument<br>
</div><div><br></div><div>that can be combined to derive the structurally equivalent sum of products for some type:</div><div><br></div><div>type F a x = Rep (PF a) x</div><div><br></div><div><div>class Mu a where</div><div>
&nbsp;&nbsp; &nbsp;inn :: F a a -&gt; a</div><div>&nbsp;&nbsp; &nbsp;out :: a -&gt; F a a</div></div><div><br></div><div>For Haskell polymorphic lists, we need to define:</div><div><br></div><div><div>type instance PF [a] = Const One :+: Const a :*: Id</div>
<div><br></div><div>instance Mu [a] where</div><div>&nbsp;&nbsp; &nbsp;inn (Left _) = []</div><div>&nbsp;&nbsp; &nbsp;inn (Right (x,xs)) = x:xs</div><div>&nbsp;&nbsp; &nbsp;out [] = Left _L</div><div>&nbsp;&nbsp; &nbsp;out (x:xs) = Right (x,xs)</div></div><div><br></div><div>Some of the typical recursion patterns are:</div>
<div><br></div><div>hylo :: Functor (PF b) =&gt; b -&gt; (F b c -&gt; c) -&gt; (a -&gt; F b a) -&gt; a -&gt; c<br></div><div>cata :: (Mu a,Functor (PF a)) =&gt; a -&gt; (F a b -&gt; b) -&gt; a -&gt; b<br></div><div>ana :: (Mu b,Functor (PF b)) =&gt; b -&gt; (a -&gt; F b a) -&gt; a -&gt; b<br>
</div><div><br></div><div>One simple example is the foldr (catamorphism) for calculating the lenght of a list:</div><div><br></div><div><div>length :: [a] -&gt; Int</div><div>length = cata (_L::[a]) f</div><div>&nbsp;&nbsp; &nbsp;where f = zero \/ succ . snd</div>
<div><br></div><div>&gt; length [1,2,3,4]</div><div>4</div></div><div><br></div><div><div><br></div><div>I have promoted the library into a cabal package (pointless-haskell) today and am creating an homepage (<a href="http://haskell.di.uminho.pt/wiki/Pointless+Haskell">http://haskell.di.uminho.pt/wiki/Pointless+Haskell</a>) with examples.</div>
<div><br></div><div>cheers,</div><div>hugo<br><br><div class="gmail_quote">On Thu, Nov 27, 2008 at 9:29 AM, Simon Peyton-Jones <span dir="ltr">&lt;<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Friends<br>
<br>
GHC has embodied data type families since 6.8, and now type synonym families (aka type functions) in 6.10. &nbsp;However, apart from our initial papers there isn&#39;t much published material about how to *use* type families. &nbsp;But that hasn&#39;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.<br>

<br>
Ken Shan and Oleg Kiselyov and I are collaborating to write a paper for an upcoming workshop, under the general rubric of &quot;Fun with type functions&quot; (in homage to Thomas Hallgren&#39;s paper &quot;Fun with functional dependencies&quot; and Ralf Hinze&#39;s paper &quot;Fun with phantom types&quot;).<br>

<br>
So this message is to ask you:<br>
<br>
 &nbsp; &nbsp; &nbsp; &nbsp;can you tell us about the most persuasive, fun application<br>
 &nbsp; &nbsp; &nbsp; &nbsp;you&#39;ve encountered, for type families or functional dependencies?<br>
<br>
Simple is good. &nbsp;It doesn&#39;t have to be elaborate: just something that does something useful you could not have done otherwise. &nbsp;Pointers to email threads are fine. &nbsp;Don&#39;t assume we already know about them (even if we participated in the thread :-) &nbsp;Part of what we&#39;re interested in is that *you* found the example compelling.<br>

<br>
Many thanks<br>
<br>
Simon, Ken, Oleg<br>
<br>
PS: I&#39;m broadcasting this message to GHC-users and Haskell-cafe, but to avoid deluging ghc-users, please reply just to us and Haskell cafe. &nbsp;(Interested ghc-users can follow the threads there from the archives if they want.)<br>

_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br><br clear="all"><br>-- <br><a href="http://www.di.uminho.pt/~hpacheco">www.di.uminho.pt/~hpacheco</a><br>
</div></div>