Well, yesterday was either a very productive day or a very lucky day for me. I read up on monads – I found that khinsen's tutorials and Jim Duey's tutorials complemented each other nicely. Then I went for a long run (about 18 miles I think) and let the ideas sink in. When I got home, I found state-m and m-seq and the job was almost done.

Just as a reminder, yesterday's task was to build a time-series framework where a function \(f\) accepts the previous \(n\) outputs of \(f\) as input to generate a new output. Here is my solution, edited for clarity (the actual solution is in a github repository):

(defn time-series [f init-state n num-iterations]
 (let [call-f (fn [state]
                (let [retval (f state)
                      num (count state)
                      new-state (vec (if (= num n) (drop 1 (conj state retval)) (conj state retval)))]
                  [retval new-state]))]
   ((with-monad state-m
      (m-seq (repeat num-iterations call-f)))
    (vector init-state))))

As you can see, the heavy lifting is done by the state monad and by m-seq. What do they do? Well, m-seq can be thought of as taking a list of functions and calling them in order, returning a list of their return values. The list of functions in this case is the same function (call-f) over and over. All call-f does is call \(f\) and change the state.

It might appear that call-f is an \(O(n)\) function. After all, we call count on the state, which is a vector of at most \(n\) elements. However, almost all the behind-the-scenes data structures that Clojure uses (including the vector data structure) are guaranteed to have \(O(1)\) performance for calling count. So that's nice, and call-f has the performance characteristics that I desired.

They're still a slightly confusing and magical-seeming thing to me, but monads have some obvious utility. I guess the way to think about them is that if you put your input and output in a common format, then they aid you in stringing functions together very easily. I used them in this case to encapsulate state, and that is probably the most common use of them in Clojure (judging by the number of state functions in the Clojure monads library). However, I think I should probably try to understand all the monads in the library and know how to combine them.

I could have written the function above without monads, but the code would not have been nearly as concise, and there probably would have been many more edge-cases to consider.

I also wrote some stuff to make debugging easier, and used incanter to compare multiple time series. However, neither required me to bend my brain as much as monads, so I won't talk about them very much. In fact, not at all, because that is the end of my post.