Music, Computers and Deconstruction

Dynamic Programming in functional languages

A while ago I wrote a small article for a friends e-zine. The e-zine is open to almost any topic that focuses around technology or other aspects of geek life, so I chose a topic that was puzzling me at that time.

The article is about a way to implement dynamic programming algorithms in functional languages. When implemented in non-functional languages dynamic programming algorithms usually rely heavily on the use of mutable data structures. In a pure functional environment no such data structures are available. Thus these data structures have to be replaced with their pervasive and immutable counterparts. This leaves quite a few problems that concern the propagations of changes that are done on these data structures. The article describes ways to propagate the changes that use advanced functional idioms like y-combinators or monads.

The paper in .aware γ e-zine

(Note: There are a few small mistakes in the paper, that can be easily picked out by a thorough reader. I did the paper on a very short notice, about one weekend before the deadline, so some of those slipped my proof-reading. Please excuse the discourtesy)