Sunday, September 19, 2010

QOTD

I consider it extremely important–perhaps vital, even–to spend time engaging others intelligently who have diverging views from one’s own. I think that this is, on the whole, one of the most valuable uses of one’s time that exists. Whether it’s consulting a disagreeable book or a person, somehow at the intersection of intelligence and difference lies a “something” that is mind-expanding.

From Sealed Abstract - Why I stopped reading HN via @conal

Thursday, September 16, 2010

Single exponential smoothing and foldl

Recently I looked at simple techniques for time series smoothing and forecasting. One such primitive method is the single exponentially weighted moving average (SEWMA), defined as

\begin{align*}<br />S_{t+1} & = \alpha y_t + \left(1-\alpha \right ) S_t \quad \quad 0 \leq \alpha \leq 1 \quad \quad t \geq 2 \\<br />S_2 & = y_1<br />\end{align*}

where the sequences are indexed from 1. y_i denotes an observed value of the time series and S_i a SEWMA value. In words, this recursive definition expresses that the next SEWMA value is a weighted average of the curent observed and SEWMA values.

If I pose the question "What is the predicted value for the next time series observation?" we just apply the formula.


A typical imperative implementation

sewma <- function (alp, y) {
S <- y[1]
for (t in 2:length(y)) { S <- alp * y[t] + (1-alp) * S }
S
}
This is R code, but it should look familiar enough to anyone who has written Java, C#, etc.


Haskell implementation
In Haskell, a fold is a way of recursively iterating a data structure, accumulating a return value. The left fold has type
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f s y = ...
Denote one of the values from the conceptual sequence of accumulator values as S_i. The function f maps from the current accumulator and list values to the next accumulator value

S_{t+1} = f\left(S_t, y_t \right)

which is the form of the SEWMA equation above. The foldl1 function is a specialisation of foldl that uses the first value of the list as the initial accumulator value, yielding the implementation
sewma alp = foldl1 (\s y -> alp * y + (1-alp) * s)


Revisiting R
R has the Reduce function for performing folds.
sewma <- function (alp, ys) {
Reduce(function (S, y) { S <- alp * y + (1-alp) * S }, ys[2:length(ys)], ys[1])
}


Summary
If accumulating a value over a data structure can be represented with a step function of the form

S_{t+1} = f\left(S_t, y_t \right)

then a left fold captures the recursive implementation.

Monday, September 6, 2010

Haskell mode in MacVim

I set up Haskell mode (haskellmode-20100622.vba) in MacVim 7.3 (53). As a Vim newbie I found this page useful, even though it says pretty much the same thing as the Haskell mode project page.

I followed the instructions and created $HOME/.vimrc with these contents.

" use ghc functionality for haskell files
au Bufenter *.hs compiler ghc

" switch on syntax highlighting
set syntax on

" enable filetype detection, plus loading of filetype plugins
set filetype plugin on

" Configure browser for haskell_doc.vim
let g:haddock_browser = "open"
let g:haddock_browser_callformat = "%s %s"
Unfortunately when I edited a Haskell file none of the Haddock integration was working. I assume the haskell_doc.vim filetype plugin wasn't being loaded because the :DocSettings command failed with E492: Not an editor command.

After some hours I changed the line set filetype plugin on to :filetype plugin on and Haddock integration now works (don't know why). I am using the Haskell Platform which includes the documentation.

After reading A minimal Vim configuration I have switched from $HOME/.vimrc to $HOME/.gvimrc with these contents.
" line numbers
set number

" show the cursor line and column number
set ruler

" turn off blinking cursor in normal mode
set gcr=n:blinkon0

" hide the toolbar
set go-=T

" switch on syntax highlighting
set syntax

" highlight matches in a search (hls)
" show the current matching pattern as you search (is),
" ignore case (ic) unless you are searching for both upper and lowercase letters (scs)
set hls is ic scs

" use ghc functionality for haskell files
au Bufenter *.hs compiler ghc

" enable filetype detection, plus loading of filetype plugins
:filetype plugin indent on

" Configure browser for haskell_doc.vim
let g:haddock_browser = "open"
let g:haddock_browser_callformat = "%s %s"