CODEWITHSUNDEEP
f#functional-programming
professor bigglesworth
professor bigglesworth

Reputation: 570

Idiomatic approach to filtering

I am looking for an idiomatic approach to programming filters in F#. For clarity, I refer to a filter as a function that uses a series of measurements over time and produces evolving estimates. This implies that the function be able to maintain state. For example, in Python one could use coroutines to maintain state in a very clean way.

What I'm looking for is an idiomatic approach to programming filters in F#. Given that my mind is thoroughly polluted with OOP and procedural principles, naturally I came up with classes to express them. Is there a more idiomatic approach to filtering in F#, one that could perhaps open up other benefits of the functional paradigm?

open System
open MathNet.Numerics.LinearAlgebra
open MathNet.Numerics.Random
open MathNet.Numerics.Distributions
open MathNet.Numerics.Statistics
open FSharp.Charting

type ScalarKalman (A : float, H : float, Q : float, R : float) = class

    let mutable A = A
    let mutable H = H
    let mutable Q = Q
    let mutable R = R

    let mutable p = 0.
    let mutable x = 0.
    let mutable k = 0.

    let mutable result = 0.

    member this.X
        with get() = x
        and set(value) = x <- value

    member this.P
        with get() = p
        and set(value) = p <- value

    member this.K
        with get() = k
        and set(value) = k <- value

    member this.update(newVal : float) =
        let xp = A * this.X
        let Pp = A * this.P * A + Q
        this.K <- Pp * H / (H * Pp * H + R)
        this.X <- xp + this.K * (newVal - H * xp)
        this.P <- Pp - this.K * H * Pp

end

let n = 100
let obsv = [|for i in 0 .. n do yield 0.|]
let smv = [|for i in 0 .. n do yield 0.|]
let kal = new ScalarKalman(1., 1., 0., 5.)
kal.P <- 4.
kal.X <- 6.
for i in 0 .. n do
    obsv.[i] <- Normal.Sample(10., 5.)
    kal.update(obsv.[i])
    smv.[i] <- kal.X

Chart.Combine([obsv |> Chart.FastLine
               smv |> Chart.FastLine]) |> Chart.Show

Upvotes: 3

Views: 153

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80744

In your case, the terms "functional" and "F# idiomatic" would consist of two things: immutable data and separation of data from code.

Immutable data: you would have one data structure representing the filter parameters (i.e. A, H, Q, and R), and another structure representing the filter's current state (i.e. X, K, and P). Both immutable. Instead of mutating the state, you would produce a new one.

Separation of data from code: the filter itself would consist of a single function that takes parameters, current state, next observation value, and produces next state. This next state will then be fed back into the function along with the next observation value, thus producing next+1 state, and so on. The parameters always stay constant, so they can be passed in just once, using partial application (see below).

Once you have such function, you can "apply" it to the list of observations as a "rolling projection", - as described above, - taking each observation and feeding it into the function along with the last state, producing the next state. This "rolling projection" operation is a very common thing in functional programming, and is usually called scan. F# does provide implementations of scan for all standard collections - list, seq, etc.

As a result of scan, you will have a list of filter's successive states. Now all that's left to do is to fish the X value out of each state.

Here is the complete solution:

module ScalarKalman =

   type Parameters = { A : float; H : float; Q : float; R : float }
   type State = { K: float; X: float; P: float }

   let initState (s: State) = s

   let getX s = s.X

   let update parms state newVal =
      let xp = parms.A * state.X
      let Pp = parms.A * state.P * parms.A + parms.Q
      let newK = Pp * parms.H / (parms.H * Pp * parms.H + parms.R)
      { K = newK
        X = xp + newK * (newVal - parms.H * xp)
        P = Pp - newK * parms.H * Pp }


let n = 100
let obsv = [for i in 0 .. n -> Normal.Sample(10., 5.)]
let kal = ScalarKalman.update { A = 1.; H = 1.; Q = 0.; R = 5. }
let initialState = ScalarKalman.initState { X = 6.; P = 4.; K = 0. }

let smv = 
  obsv 
  |> List.scan kal initialState 
  |> List.map ScalarKalman.getX

A note on design
Note the initState function declared in the module. This function may seem silly on the surface, but it has important meaning: it lets me specify state fields by name without opening the module, thus avoiding namespace pollution. Plus, the consuming code now looks more readable: it says what it does, no comments required.

Another common approach to this is to declare a "base" state in the module, which consuming code could then amend via the with syntax:

module ScalarKalman = 
    ...
    let zeroState = { K = 0.; X = 0.; P = 0. }

...
let initialState = { ScalarKalman.zeroState with X = 6.; P = 4. }

A note on collections
F# lists are fine on small amounts of data and small processing pipelines, but become expensive as these two dimensions grow. If you're working with a lot of streaming data, and/or if you're applying multiple filters in succession, you might be better off using lazy sequences - seq. To do so, simply replace List.scan and List.map with Seq.scan and Seq.map respectively. If you do, you will get a lazy sequence as the ultimate result, which you will then need to somehow consume - either convert it to a list, print it out, send it to the next component, or whatever your larger context implies.

Upvotes: 8

Related Questions