I’ve been getting into Haskell recently. Its a pretty theoretical language, which can be a barrier to entry. In fact, just writing your app/library’s types will probably make you flesh out the flow of your application. The type system is amazing though, and once you understand monads, you can do anything with a simple API.

I just uploaded my first package to Hackage, haskell-spsa. I haven’t fleshed out the documentation yet, so please forgive that transgression until I do. But like my previously written library, golang-spsa; haskell-spsa implements the optimzation algorithm SPSA. I wanted to walk a little bit through the code and my thought process.

The first thing to do when designing a haskell package is establish the types to be used. Nothing fancy here (no typeclasses or monads to define). Essentially, here, we are saying the prototype for a loss function and constraint function, as well as defining the parameters to actually run an iteration of SPSA. Note that the perturbation distribution and gain sequences (ak and ck) are infinite lists.

Here, the implementation of the standard gain sequence for ak is a lazy map over an infinite sequence [1..]. Note that \var -> func var is an anonymous function definition.

Here, the meat of the package lies in this one function. First note the definition optimize :: SPSA -> Int -> Vector Double -> Vector Double. This implies that an SPSA and an Int will be use to optimize a Vector Double. This is exactly what is happening, where the Int refers to the number of iterations or rounds to optimize over.

Internally, we notice the where clause, where constrainF and lossF are just extracting parameters from the record syntax defined above. opt is a function defined locally within the optimize’s function scope which performs a single round of optimization. The top line of the function performs a foldl (also called a reduction or reduce in other languages) which accumulates a single value from a list, in this case a zip of three lists, the ak, ck, and delta (perturbation vector). The fold will take an input of the original estimated answer t0 and output the final estimated answer (tN if you will). The actual definition of opt is taken almost directly from golang-spsa, so thats not too interesting in a haskell sense.

I’ve written this library 3 times now. As for the speed of the library, it does run pretty fast, but I can’t make direct comparisons to the other fast libaries out there. But one thing it maintains is a mathematical simplicity that few other languages can match. The Go version didn’t maintain any of the niceness that my python version had, but the haskell version has speed and simplicity going for it, which is great.