Thu 3 Nov 2011

## What Constraints Entail: Part 2

Posted by Edward Kmett under Constraint Kinds , Haskell , Logic , Monads , Type Hackery , Uncategorized[13] Comments

Thu 3 Nov 2011

[13] Comments

Thu 3 Nov 2011

[6] Comments

Max Bolingbroke has done a wonderful job on adding Constraint kinds to GHC.

Constraint Kinds adds a new kind `Constraint`

, such that `Eq :: * -> Constraint`

, `Monad :: (* -> *) -> Constraint`

, but since it is a kind, we can make type families for constraints, and even parameterize constraints *on* constraints.

So, let's play with them and see what we can come up with!

Thu 27 Oct 2011

No Comments

As requested, here are the slides from Dan Doel's excellent presentation on Homotopy and Directed Type Theory from this past Monday's Boston Haskell.

Tue 25 Oct 2011

I am very pleased to officially announce Hac Boston, a Haskell hackathon to be held January 20-22, 2012 at MIT in Cambridge, MA. The hackathon will officially kick off at 2:30 Friday afternoon, and go until 5pm on Sunday with the occasional break for sleep.

Everyone is welcome -- you do not have to be a Haskell guru to attend! Helping hack on someone else's project could be a great way to increase your Haskell skills.

If you plan on coming, please officially register, even if you already put your name on the wiki. Registration, travel, some information about lodging and many other details can now be found on the Hac Boston wiki.

We have confirmed space for about 30 people, so please register early! Beyond that we'll have to either seek additional space or close registration.

We're also looking for a few people interested in giving short (15-20 min.) talks, probably on Saturday afternoon. Anything of interest to the Haskell community is fair game---a project you've been working on, a paper, a quick tutorial. If you'd like to give a talk, add it on the wiki.

We look forward to seeing you at MIT!

Fri 23 Sep 2011

No Comments

Last time, I showed that we can build a small parsec clone with packrat support.

This time I intend to implement packrat directly on top of Parsec 3.

One of the main topics of discussion when it comes to packrat parsing since Bryan Ford's initial release of Pappy has been the fact that in general you shouldn't use packrat to memoize every rule, and that instead you should apply Amdahl's law to look for the cases where the lookup time is paid back in terms of repetitive evaluation, computation time and the hit rate. This is great news for us, since, we only want to memoize a handful of expensive combinators.

Fri 23 Sep 2011

[2] Comments

You never heard of the Millenium Falcon? It's the ship that made the Kessel Run in 12 parsecs.

I've been working on a parser combinator library called trifecta, and so I decided I'd share some thoughts on parsing.

Packrat parsing (as provided by frisby, pappy, rats! and the Scala parsing combinators) and more traditional recursive descent parsers (like Parsec) are often held up as somehow different.

Today I'll show that you can add monadic parsing to a packrat parser, sacrificing asymptotic guarantees in exchange for the convenient context sensitivity, and conversely how you can easily add packrat parsing to a traditional monadic parser combinator library.

Mon 11 Jul 2011

[9] Comments

Today I hope to start a new series of posts exploring constructive abstract algebra in Haskell.

In particular, I want to talk about a novel encoding of linear functionals, polynomials and linear maps in Haskell, but first we're going to have to build up some common terminology.

Having obtained the blessing of Wolfgang Jeltsch, I replaced the algebra package on hackage with something... bigger, although still very much a work in progress.

Thu 30 Jun 2011

No Comments

In the last few posts, I've been talking about how we can derive monads and monad transformers from comonads. Along the way we learned that there are more monads than comonads in Haskell.

The question I hope to answer this time, is whether or not we turn any Haskell `Comonad`

into a comonad transformer.

Thu 30 Jun 2011

[3] Comments

Last time in Monad Transformers from Comonads I showed that given any comonad we can derive the monad-transformer

newtype CoT w m a = CoT { runCoT :: w (a -> m r) -> m r

and so demonstrated that there are fewer comonads than monads in Haskell, because while every Comonad gives rise to a Monad transformer, there are Monads that do not like `IO`

, `ST s`

, and `STM`

.

I want to elaborate a bit more on this topic.

Tue 28 Jun 2011

1 Comment

Mon 27 Jun 2011

[9] Comments

Fri 24 Jun 2011

[9] Comments

Thu 23 Jun 2011

[3] Comments

Last time, I started exploring whether or not Codensity was necessary to improve the asymptotic performance of free monads.

This time I'll show that the answer is no; we can get by with something smaller.

Thu 23 Jun 2011

[10] Comments

A couple of years back Janis Voigtländer wrote a nice paper on how one can use the codensity monad to improve the asymptotic complexity of algorithms using the free monads. He didn't use the name Codensity in the paper, but this is essentially the meaning of his type `C`

.

I just returned from running a workshop on domain-specific languages at McMaster University with the more than able assistance of Wren Ng Thornton. Among the many topics covered, I spent a lot of time talking about how to use free monads to build up term languages for various DSLs with simple evaluators, and then made them efficient by using `Codensity`

.

This has been shown to be a sufficient tool for this task, but is it necessary?

Thu 22 Jul 2010

[11] Comments

A couple of days ago, I gave a talk at Boston Haskell about a shiny new speculative evaluation library, speculation on hackage, that I have implemented in Haskell. The implementation is based on the material presented as "Safe Programmable Speculative Parallelism" by Prakash Prabhu, G Ramalingam, and Kapil Vaswani at last month's PLDI.

I've uploaded a copy of my slides here:

* Introducing Speculation [PowerPoint | PDF]

Thu 20 May 2010

I've put together a poll about when folks would like to have the next meeting, if you're going to be in the area, please help us pick a date and time that works for you!

http://www.doodle.com/ux8mqaa9h2tngf6k

Thu 20 May 2010

I'm going to be out at Hac φ over the weekend cobbling together random bits and pieces of code, if you're going to be in the Philadelphia area, look us up!

In particular, I plan to spend my time working on my automatic differentiation library adding different directional traversals, and trying to combine them into a coherent framework.

Sat 15 May 2010

No Comments

I've uploaded a package named heaps to Hackage that provides Brodal-Okasaki bootstrapped skew-binomial heaps in Haskell.

(more...)

Sat 15 May 2010

1 Comment

I've uploaded a package named rad to Hackage for handling reverse-mode automatic differentiation in Haskell.

(more...)

Thu 29 Apr 2010

[2] Comments

I gave a talk last night at Boston Haskell on finger trees.

In particular I spent a lot of time focusing on how to derive the construction of Hinze and Paterson's 2-3 finger trees via an extended detour into a whole menagerie of tree types, and less on particular applications of the final resulting structure.