For the past couple weeks I’ve been practicing Haskell by working through Project Euler’s problems. I just finished problem 78, which asks you to compute the number of ways to partition a collection of n coins, where n is large. In a way, I feel like I was forced to cheat on this one because I couldn’t do it without looking up the pentagonal number theorem. I hope that future Euler problems do not all degrade into a Google search, because although I learned some math trivia, it’s not a fun way to solve a problem.
In addition to brushing up on number theory, the puzzles have taught me a lot about programming in Haskell. My biggest takeaway is how to memoize. Typically this involves using a data structure such as a Map, constructed from a list of calls to a function that refers back to the data structure. For example:
How many routes are there through a 2020 grid? > import Data.List > import qualified Data.Map as Map > import Data.Map (Map, (!)) > mbound = 1000 > routes = Map.fromList [ ((x,y), route (x,y)) | x <- [0..mbound], y <- [0..mbound] ] > route (0, 0) = 0 > route (0, b) = 1 > route (a, b) | a > b = route (b, a) > | otherwise = (routes ! ((a - 1), b)) + (routes ! (a, (b - 1))) > main = do > print $ route (20,20)
Notice how ‘route’ refers to the ‘routes’ Map, which in turn refers to ‘route’. This works because of the Haskell’s lazy functional evaluation. How cool is that?
Another lesson is the frequent syntactic idiom of multiple function composition. For example, to create a sorted list of unique items from a list, you can write:
> mynub = map head . > group . > sort . > $ [1,2,5,3,3,1,3,2,4,5,2]
Notice how clean it looks to put each function on its own line, followed by (.). Then you always have to put a dollar sign before the final argument. This is surely obvious to Haskell pros, but it took me a bit to figure this out.
Haskell continues to delight me in its terse elegance. It’s laughable how short nearly every solution is. Now I’m on to Problem 79.
