Search code examples
haskellmonadsmoving-averagestate-monadrecurrence

Implementing recurrence relations on State monads (in Haskell or Scala)

I am working on a new implementation of the operators in http://www.thalesians.com/archive/public/academic/finance/papers/Zumbach_2000.pdf EDIT: clearer explanation here: https://www.olseninvest.com/customer/pdf/paper/001207-emaOfEma.pdf

Briefly, it's a whole bunch of cool time series operators based on the recurrence relation of the exponential moving average, where each application of the ema() operator takes the new value and the previous result of the ema. I can't seem to do latex on this stack exchange, but anyway my problem now is a software problem.

I implemented this in Scala by hiding a var deep inside the thunks that create EMA functions. This all works, but it's super tricky, because calling ema(5) and then ema(5) again will naturally lead to a different result. I'd like to try redoing all of this using State Monads, but I'm quickly getting lost in the weeds.

For example, I have the following simplified EMA State monad in Haskell:

import Control.Monad.State

type EMAState = Double
type Tau = Double

ema :: Tau -> Double -> State EMAState Double
ema tau x = state $ \y ->
  let alpha = 1 / tau
      mu = exp(-alpha)
      mu' = 1 - mu
      y' = (mu * y) + (mu' * x)
  in (y', y')

which I can readily test in GHCI:

*Main Control.Monad.State> runState (ema 5 10) 0
(1.8126924692201818,1.8126924692201818)

applying the input 10 to a 5-period EMA initialized to 0. This is all well and good, using forM I can apply multiple input values etc. Now, the next step is to implement an "iterated EMA", which is an EMA applied to itself N times. 

iEMA[n](x) = EMA(iEMA[n-1](x))

Each of these intermediate EMAs will need to have their own state, aka previous result, to correctly calculate the vector of iterated EMAs. So, what I am looking for, is something which like this, (I think):

iema :: Int -> Tau -> Double -> State [EMAState] [Double]

Which is essentially a daisy chain of EMAs:

iEMA[3](x) = EMA(EMA(EMA(x,s1),s2),s3) = (x, [s1,s2,s3]) -> ([y1,y2,y3], [s1',s2',s3'])

And if all I care about is the 3rd iterated EMA ... 

... -> (y3, [s1', s2', s3'])

The paper moves on from there, creating ever more complex operators built on iterated EMAs and averages of them etc, so I want to be able to functionally and purely compose these stateful operators building ever more complex states, but still quite simple input and output.

I really feel like this is what functional programming is good at, but I don't yet have the expertise to see how to put together these State monads in the correct way. Could someone please point me in the right direction with these iterated recurrence operators?

EDIT:

A couple of helpful folks have suggested repeated application of the same ema operator to the input data, but this is not sufficient. Each ema operator needs to maintain it's own previous value. Here's an example:

tau 5               
mu  0.818730753             
muprime 0.181269247             
        ema1    ema2    ema3     
    x   0       0       0       <- States_0
    1   0.1812  0.03285 0.00595 <- States_1
    5   1.0547  0.21809 0.04441 <- States_2

The x column is the raw input, ema1 uses its left for input and it's up for recurrence/state. ema2 uses its left for input (not x!) and it's up for state. It's an ema (ema (x) ). Ditto ema3 = ema (ema (ema (x) ) ). What I would like to do, which I think must be possible, is given an ema state monad, compose the ema3 state monad, or even better, the [ema] state monad with each each subsequent ema operating on the output of the previous.

Solution

  • Updated answer...

    Define:

    combine :: [ a -> State s a ] -> a -> State [s] a
combine fs a = state $ \ys ->
  let zs = zipWith (\f y a -> runState (f a) y) fs ys
      pairs = chain a zs
      as' = map fst pairs
      a' = last as'         -- we are only returning one result in this case
      ys' = map snd pairs
  in (a', ys')

chain :: a -> [ a -> (a,s) ] -> [ (a,s) ]
chain a [] = []
chain a (f:fs) = let (a',s) = f a
                 in (a',s) : chain a' fs

ema3 t = combine $ replicate 3 (ema t)

ghci> runState (ema3 5 1) [0,0,0]
(5.956242778945897e-3,[0.18126924692201818,3.2858539879675595e-2,5.956242778945897e-3])

ghci> runState (do ema3 5 1; ema3 5 5) [0,0,0]
(4.441089130249448e-2,[1.0547569416524334,0.21809729359983737,4.441089130249448e-2])

    The combine is easily modified to return all of the results - just return as' instead of a'.

    Original answer:

     combine :: (a -> State s b) -> (b -> State t c) -> (a -> State (s,t) c)
 combine f g a = state $ \(s,t) ->
   let (b,s') = runState (f a) s
       (c,t') = runState (g b) t
   in (c,(s',t'))

    Then:

    ema3 tau = ema tau `combine` ema tau `combine` ema tau

    and em3 has type:

    ema3 :: Tau -> Double -> State ((EMAState, EMAState), EMAState) Double

    For instance:

    ghci> runState (ema3 5 1) ((0,0),0)
(5.956242778945897e-3,((0.18126924692201818,3.2858539879675595e-2),5.956242778945897e-3))

    Note that the state type of ema3 is ((Double,Double),Double) and not a 3-tuple or list.

    In your example you run (ema3 5) first with input x = 1 and then with input x = 5 with initial state ((0,0),0):

    ghci> runState (do ema3 5 1; ema3 5 5) ((0,0),0)
(4.441089130249448e-2,((1.0547569416524334,0.21809729359983737),4.441089130249448e-2))

    and that gives you the second row in the table.