Pointless Haskell

A library for point-free programming with recursion patterns defined as hylomorphisms. The syntax follows directly the theoretical one, with generic recursion patterns parameterized by the data type to which they should be applied. It builds on ideas previously presented in the PolyP library. Here are some possible definitions.

assocl :: (a,(b,c)) -> ((a,b),c)
assocl = id >< fst /\ snd . snd

length :: [a] -> Int
length = ana (_L::Int) ((id -|- snd) . out)

fact :: Int -> Int
fact = para (_L::Int) (one \/ (mult . (id >< succ)))

fib :: Int -> Int
fib = hylo (_L :: Mu (Const One :+: Id :*: Id)) f g
   where g = (bang -|- pred /\ pred . pred) . ((<=1)?)
         f = one \/ plus

It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature toghether with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions. For example the intermediate shape tree generated by fib 5 is the following.

Pasted Graphic 3

DrHylo

Tool for deriving point-free hylomorphisms from a restricted Haskell syntax. The hylomorphism derivation is based on the algorithm first presented in the paper Deriving Structural Hylomorphisms From Recursive Definitions by Hu, Iwasaki, and Takeichi (ICFP'96). The pointwise to point-free translation is based on the well-known equivalence between simply-typed lambda calculus and cartesian closed categories first suggested by Lambek. The result of the translation is very verbose, but can be simplified with the SimpliFree tool developed by José Proença. For example the pointwise definitions

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

data Nat = Zero | Succ Nat

len :: [a] -> Nat
len [] = Zero
len (h:t) = Succ (len t)

can be converted into the following point-free ones.

swap :: (a, b) -> (b, a)
swap = app . (((curry ((snd . snd) /\ (fst . snd))) . bang) /\ id)

len :: [a] -> Nat
len = hylo (_L :: Mu ((:+:) (Const One) Id))
   (app . (((curry (app . ((eithr . ((curry (inn . (inl . bang))) /\ (curry (inn . (inr . snd))))) /\ snd))) . bang) /\ id))
   (app . (((curry (app . ((eithr . ((curry (inl . bang)) /\ (curry (inr . (snd . snd))))) /\ (out . snd)))) . bang) /\ id))

Notice that these can be directly executed with Pointless Haskell.

Relevant Publications

Alcino Cunha, Jorge Sousa Pinto, and José Proença, A Framework for Point-free Program Transformation. To appear in the selected papers of the 17th International Workshop on Implementation and Application of Functional Languages. LNCS. Springer-Verlag, 2006.

Alcino Cunha, Point-free Program Calculation. PhD Thesis, Department of Informatics, University of Minho. June 2005.

Alcino Cunha, Jorge Sousa Pinto, and José Proença, Down with Variables. Technical Report DI-PURe-05.06.01, Department of Informatics, University of Minho. June 2005.

Alcino Cunha, Automatic Visualization of Recursion Trees: a Case Study on Generic Programming. Selected papers of the 12th International Workshop on Functional and (Constraint) Logic Programming. Volume 86(3) of ENTCS. Elsevier, 2003.

Download

Both Pointless Haskell and DrHylo are distributed in the UMinho Haskell Libraries, developed in the context of the PURe project.