Showing posts from May, 2015

Memoization in Haskell

When I was first learning Haskell, there were some imperative design patterns that I had trouble converting to functional style Haskell. Memoization is the first thing that comes to mind. I use memoization so much that it was pretty much trivial do in an imperative language like Java. However, I could not figure out how to do it in Haskell. In this blog post, I will discuss how you can memoize your functions in Haskell to boost performance in case you're ever in a situation where you want to use it. It turns out that memoization in Haskell is just as easy, if not easier, than memoization in an imperative language.

Before I talk about memoization in Haskell, I will discuss the traditional approach to memoizing a recursive function in an imperative language. It essentially boils down to these steps:
Query lookup table to see if result is computed; If so, return itCompute result recursivelyStore result in lookup tableReturn result For example, consider the numbers in Catalan's tri…