2009
Yearly Archive
Tue 15 Sep 2009
I'll be giving a talk tomorrow, Wednesday, September 16th, 2009 at the Boston Haskell User Group in the MIT CSAIL Reading Room (on the 8th floor of the William H. Gates tower of the Stata center) about mixing Oleg's iteratees with parsec and monoids to build practical parallel parsers and to cheaply reparse after local modifications are made to source code.
Ravi is trying to organize some time before hand during which people can get together and work on Haskell projects, or spend some time learning Haskell, so its not all scary academic stuff.
The meeting is scheduled from 79pm, and an ever growing number of us have been wandering down to the Cambridge Brewing Company afterwards to hang out and talk.
If you are curious about Haskell, or even an expert, or just happen to be interested in parallel programming and find yourself in the area, come on by.
Tue 15 Sep 2009
Posted by Edward Kmett under
Mathematics [9] Comments
Two concepts come up when talking about information retrieval in most standard documentation, Precision and Recall. Precision is a measure that tells you if your result set contains only results that are relevant to the query, and recall tells you if your result set contains everything that is relevant to the query.
The formula for classical precision is:
However, I would argue that the classical notion of Precision is flawed, in that it doesn't model anything we tend to care about. Rarely are we interested in binary classification, instead we want a ranked classification of relevance.
(more...)
Sat 29 Aug 2009
Posted by Edward Kmett under
Macros ,
Scheme [10] Comments
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 overapplication cleanly.
(more...)
Thu 20 Aug 2009
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 locallycontext 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.
 Introduction To Monoids (PDF)
 Iteratees, Parsec and Monoids: A Parsing Trifecta (PDF)
Due to a late start, I was unable to give the second talk. However, I did give a quick run through to a few diehards 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
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 Chungchieh 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.
(more...)
Fri 31 Jul 2009
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, attributegrammars, etc.)
Thu 11 Jun 2009
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 categoryextras, along with variations on the underlying themes, so this should work as a punchlist.
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 categoryextras with distributive law combinators
† The scheme can be generalized to accept one or more Fdistributive (co)monads.
Tue 31 Mar 2009
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.
(more...)