Sat 29 Aug 2009

I've been transcoding a lot of Haskell to Scheme lately and one of the things that I found myself needing was a macro for dealing with Currying of functions in a way that handles partial and over-application cleanly.

Sat 29 Aug 2009

I've been transcoding a lot of Haskell to Scheme lately and one of the things that I found myself needing was a macro for dealing with Currying of functions in a way that handles partial and over-application cleanly.

Thu 20 Aug 2009

[5] Comments

I was asked to give two talks at the Boston Area Haskell User Group for this past Tuesday. The first was pitched at a more introductory level and the second was to go deeper into what I have been using monoids for lately.

The first talk covers an introduction to the mathematical notion of a monoid, introduces some of the features of my Haskell monoids library on hackage, and starts to motivate the use of monoidal parallel/incremental parsing, and the modification use of compression algorithms to recycle monoidal results.

The second talk covers a way to generate a locally-context sensitive parallel/incremental parser by modifying Iteratees to enable them to drive a Parsec 3 lexer, and then wrapping that in a monoid based on error productions in the grammar before recycling these techniques at a higher level to deal with parsing seemingly stateful structures, such as Haskell layout.

Due to a late start, I was unable to give the second talk. However, I did give a quick run through to a few die-hards who stayed late and came to the Cambridge Brewing Company afterwards. As I promised some people that I would post the slides after the talk, here they are.

The current plan is to possibly give the second talk in full at either the September or October Boston Haskell User Group sessions, depending on scheduling and availability.

[ Iteratee.hs ]

Sat 15 Aug 2009

[7] Comments

I have updated the reflection package on hackage to use an idea for avoiding dummy arguments posted to the Haskell cafe mailing list by Bertram Felgenhauer, which adapts nicely to the case of handling Reflection. The reflection package implements the ideas from the Functional Pearl: Implicit Configurations paper by Oleg Kiselyov and Chung-chieh Shan.

Now, you no longer need to use big scary undefineds throughout your code and can instead program with implicit configurations more naturally, using Applicative and Monad sugar.

Fri 31 Jul 2009

[10] Comments

Some people have requested my slides from the short talk I gave about monoids and monoidal parsing at Hac Phi. So, here they are.

There will be more to come at the next Boston Haskell User Group in August, where it looks like I'll be giving two short talks covering monoids. I may use the monoidal parsing engine from Kata as an example for the advanced talk if I have time and will start to cover parsing larger classes of grammars in general (regular languages, CFGs/TIGs, TAGs, PEGs, LALR, attribute-grammars, etc.)

Thu 11 Jun 2009

[16] Comments

About a year back I posted a field guide of recursion schemes on this blog and then lost it a few months later when I lost a couple of months of blog entries to a crash. I recently recovered the table of recursion schemes from the original post thanks to Google Reader's long memory and the help of Jeff Cutsinger.

The following recursion schemes can be found in category-extras, along with variations on the underlying themes, so this should work as a punch-list.

Folds | ||
---|---|---|

Scheme | Code | Description |

catamorphism† | Cata | tears down a structure level by level |

paramorphism*† | Para | tears down a structure with primitive recursion |

zygomorphism*† | Zygo | tears down a structure with the aid of a helper function |

histomorphism† | Histo | tears down a structure with the aid of the previous answers it has given. |

prepromorphism*† | Prepro | tears down a structure after repeatedly applying a natural transformation |

Unfolds | ||

Scheme | Code | Description |

anamorphism† | Ana | builds up a structure level by level |

apomorphism*† | Apo | builds up a structure opting to return a single level or an entire branch at each point |

futumorphism† | Futu | builds up a structure multiple levels at a time |

postpromorphism*† | Postpro | builds up a structure and repeatedly transforms it with a natural transformation |

Refolds | ||

Scheme | Code | Description |

hylomorphism† | Hylo | builds up and tears down a virtual structure |

chronomorphism† | Chrono | builds up a virtual structure with a futumorphism and tears it down with a histomorphism |

synchromorphism | Synchro | a high level transformation between data structures using a third data structure to queue intermediate results |

exomorphism | Exo | a high level transformation between data structures from a trialgebra to a bialgebraga |

metamorphism | Erwig | a hylomorphism expressed in terms of bialgebras |

metamorphism | Gibbons | A fold followed by an unfold; change of representation |

dynamorphism† | Dyna | builds up a virtual structure with an anamorphism and tears it down with a histomorphism |

Elgot algebra | Elgot | builds up a structure and tears it down but may shortcircuit the process during construction |

Elgot coalgebra | Elgot | builds up a structure and tears it down but may shortcircuit the process during deconstruction |

* This gives rise to a family of related recursion schemes, modeled in category-extras with distributive law combinators

† The scheme can be generalized to accept one or more F-distributive (co)monads.

Tue 31 Mar 2009

[3] Comments

Recently, Sean Leather took up the idea of incremental folds. [1] [2]. At the end of his first article on the topic he made a comment on how this was a useful design pattern and sagely noted the advice of Jeremy Gibbons that design patterns are more effective as programs, while complaining of cut and paste coding issues.

The following attempts to address these concerns.

Thu 4 Dec 2008

[3] Comments

Last night, Chung-Chieh Shan posted an example of a pointed-set monad on his blog, which happens to be isomorphic to a non-empty stream monad with a different emphasis.

But, I thought I should point out that the pointed set that he posted also has a comonadic structure, which may be exploited since it is just a variation on the "zipper comonad," a structure that is perhaps more correctly called a "pointing comonad."

Sat 8 Nov 2008

To those that have asked, I'm still alive.

I had to restore the blog database from a backup and so I lost a few posts, including the index for the various recursion schemes entries. Fortunately, before that happened I had replicated the catamorphism post as a knol.

Should I find myself with a copious glut of free time, I shall happily re-scribe and finish the rest, but I've been very busy.

Thu 5 Jun 2008

As you may recall, every functor in Haskell is strong, in the sense that if you provided an instance of Monad for that functor the following definition would satisfy the requirements mentioned here:

strength :: Functor f => a -> f b -> f (a,b) strength = fmap . (,)

In an earlier post about the cofree comonad and the expression problem, I used a typeclass defining a form of duality that enables you to let two functors annihilate each other, letting one select the path whenever the other offered up multiple options. To have a shared set of conventions with the material in Zipping and Unzipping Functors, I have since remodeled that class slightly:

Thu 5 Jun 2008

I've had a few people ask me questions about Adjunctions since my recent post and a request for some more introductory material, so I figured I would take a couple of short posts to tie Adjunctions to some other concepts.

**Representable Functors**

A covariant functor is said to be representable by an object if it is naturally isomorphic to .

We can translate that into Haskell, letting play the role of with:

Tue 3 Jun 2008

This post is a bit of a departure from my recent norm. It contains no category theory whatsoever. None. I promise.

Now that I've bored away the math folks, I'll point out that this also isn't a guide to better horticulture. Great, there goes the rest of you.

Instead, I want to talk about Bloom filters, Bloom joins for distributed databases and some novel extensions to them that let you trade in resources that we have in abundance for ones that are scarce, which I've been using for the last few months and which I have never before seen before in print. Primarily because I guess they have little to do with the strengths of Bloom filters.

Mon 26 May 2008

[15] Comments

Grant B. asked me to post the derivation for the right and left Kan extension formula used in previous Kan Extension posts (1,2). For that we can turn to the definition of Kan extensions in terms of ends, but first we need to take a couple of steps back to find a way to represent (co)ends in Haskell.

Thu 22 May 2008

[6] Comments

I want to spend some more time talking about Kan extensions, composition of Kan extensions, and the relationship between a monad and the monad generated by a monad.

But first, I want to take a moment to recall adjunctions and show how they relate to some standard (co)monads, before tying them back to Kan extensions.

**Adjunctions 101**

An adjunction between categories and consists of a pair of functors , and and a natural isomorphism:

We call the left adjoint functor, and the right adjoint functor and an adjoint pair, and write this relationship as

Tue 20 May 2008

[9] Comments

I think I may spend a post or two talking about Kan extensions.

They appear to be black magic to Haskell programmers, but as Saunders Mac Lane said in Categories for the Working Mathematician:

All concepts are Kan extensions.

So what is a Kan extension? They come in two forms: right- and left- Kan extensions.

First I'll talk about right Kan extensions, since Haskell programmers have a better intuition for them.

Mon 19 May 2008

[4] Comments

> import Control.Arrow ((|||),(&&&),left) > newtype Mu f = InF { outF :: f (Mu f) }

I want to talk about a novel recursion scheme that hasn't received a lot of attention from the Haskell community and its even more obscure dual -- which is necessarily more obscure because I believe this is the first time anyone has talked about it.

Jiri Adámek, Stefan Milius and Jiri Velebil have done a lot of work on Elgot algebras. Here I'd like to translate them into Haskell, dualize them, observe that the dual can encode primitive recursion, and provide some observations.

You can kind of think an Elgot algebra as a hylomorphism that cheats.

> elgot :: Functor f => (f b -> b) -> (a -> Either b (f a)) -> a -> b > elgot phi psi = h where h = (id ||| phi . fmap h) . psi

Fri 16 May 2008

Wed 14 May 2008

[13] Comments

Ok, I decided to take a step back from my flawed approach in the last post and play with the idea of power series of functors from a different perspective.

I dusted off my copy of Herbert Wilf's generatingfunctionology and switched goals to try to see some well known recursive functors or species as formal power series. It appears that we can pick a few things out about the generating functions of polynomial functors.

As an example:

Maybe x = 1 + x

Ok. We're done. Thank you very much. I'll be here all week. Try the veal...

For a more serious example, the formal power series for the list [x] is just a geometric series:

Tue 13 May 2008

[12] Comments

Wed 7 May 2008

I did some digging and found the universal operations mentioned in the last couple of posts: unzip, unbizip and counzip were referenced as abide, abide and coabide -- actually, I was looking for something else, and this fell into my lap.

They were apparently named for a notion defined by Richard Bird back in:

R.S. Bird. Lecture notes on constructive functional programming. In M. Broy, editor, Constructive Methods in Computing Science. International Summer School directed by F.L. Bauer [et al.], Springer Verlag, 1989. NATO Advanced Science Institute Series (Series F: Computer and System Sciences Vol. 55).

The notion can be summed up by defining that two binary operations and **abide** if for all a, b, c, d:

.

There is a cute pictorial explanation of this idea in Maarten Fokkinga's remarkably readable Ph.D dissertation on p. 20.

The idea appears again on p.88 as part of the famous 'banana split' theorem, and then later on p90 the above names above are given along with the laws:

fmap f &&& fmap g = unfzip . fmap (f &&& g) bimap f g &&& bimap h j = unbizip . bimap (f &&& h) (g &&& j) fmap f ||| fmap g = fmap (f ||| g) . counfzip

That said the cases when the inverse operations exist do not appear to be mentioned in these sources.

Mon 5 May 2008

Twan van Laarhoven pointed out that fzip from the other day is a close cousin of applicative chosen to be an inverse of the universal construction 'unfzip'.

During that post I also put off talking about the dual of zipping, so I figured I'd bring up the notion of choosing a notion of 'cozipping' by defining it as an inverse to a universally definable notion of 'counzipping'.