Back to Questions
1.5k
views6
comments
General programming question : combining static and dynamic features
f#

Hi,

I have a very general programming question. It basically contains a few functions which transfom some input data into output values (the transforms consist in smoothing etc.)

These transform functions ought to be used in either a static environment (for instance, when doing some backtesting), but also in a dynamic (or real-time, so to speak) environment (for instance, when receiving data from whatever data provider you use).

The functions are currently of the type : [ 

1

val foo : input data -> arguments -> output * update function

](where the basic structure of the input data is ResizeArray<_>, and the output is either a ResizeArray<_> or a tuple of those.

The <update function>, when called, performs computations from where the initial call to the transformation function left on (using the initial arguments). That is, say you have 20 observations to start with, and then add 10 more observations to your input data, then update() performs the transform (adding values to the output data structure) for those 10 values only (it doesn't recompute from scratch).

The issue wih returning both an output AND an update function, is that you can't compose functions that easily. Indeed, you can't simply have [

1

 let foo data args = result, update and bar = foo >> foo >> foo

]which you could have if foo only returned result.

I thought about using the ObservableCollection from WPF (where, basically, I would use something (very) roughly like : input.OnAddValue.Add (fun _ -> update()) . However, this means that every update of the input data causes an update of the transformed values collection, which you might not want (that is, it doesn't seem stupid to only want to compute the update every n (milli)seconds instead to save CPU / do other stuff in the mean time).

I had also thought on recomputing the whole output from scratch on every update, but this should probably be overkill.

My question is therefore : is there a preferred/common way to deal with the dynamic aspect?

Any insight/advice would be appreciated.

Cheers,

Julien

.

If you really don't want to do this the purely functional way (carrying all state), e.g. if it is for a GUI, then you might want to mimic a mutable data structure and trigger events upon mutation.

Cheers,
Jon.

By on 4/27/2007 7:33 AM ()

Is the transform function point-wise? I.e., does an element in the output array only depend on its corresponding element in the input array? If so you might be able to do something simple with IEnumerables where your transform function is something like Seq.map.

To get around the performance problem you identified with ObservableCollection you can, instead of computing updates when input it written, compute updates when output is read. So when input it added it just adds it to a data structure and triggers no events. Then when output is retrieved it first checks if new input has been added and does an update if necessary.

Hope this helps.

- Greg

By on 4/25/2007 10:21 PM ()

Hi,

Thanks for the reply. I had thought about using container structures at first, like having

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 

type foo =
  class

    //x.update computes marginally-needed output values
    //x.can_compute returns true if : arguments are valid AND there is enough data to perform computations
  
    member x.output = 
      match x._output with
      | Some x -> Some x
      | None -> if x.can_compute() then x.update() ; x.output else None

  end

However, the disadvantage is that the <update> and <can_compute> functions should be hidden from the end-user (i.e. they should be "protected"), which is possible if you define your base class in the same file as the implementation of the classes, but it prevents later extension (adding new functions in other classes).

Did you have something different in mind ?

I have included a few examples below. I am not sure how you could use a map to define an output function that references itself.

Thanks again for your kind help !

Julien

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

 

#light

module Transform 

 

module ResizeArray = 
    begin        
        let is_empty (arr:ResizeArray<'a>) = arr.Count = 0
        let empty () = new ResizeArray<_>()              
        let fill_f (arr:ResizeArray<'a>) start len f = for i in start .. start + len - 1 do arr.[i] <- f i    
        let add (arr:ResizeArray<'a>) value = arr.Add value
        let clear (arr:ResizeArray<'a>) = arr.Clear()
        
        //taken from the FSLib/ResizeArray.fs source file        
        let to_array (arr:ResizeArray<'a>) = Seq.to_array arr
        let of_array (arr:array<'a>) = new ResizeArray<_>(Seq.of_array arr)   
    end

 


(*******************************************************************************************************************************)
(*******************************************************************************************************************************)

// Example of a simple function that could be used used with a "map input f" but that is a little more rapid this way


//Minimum

let minimum data periods = 
    //input verification
    let check_errors() =
        if data = null then invalid_arg "<min> : data is null" 
        if periods <= 0 then invalid_arg "<min> : periods<=0" 
    
    //output structure    
    let result = new ResizeArray<float>()    
    
    //computation helpers
    let data_length() = ResizeArray.length data
    let enough_data() = data_length() >= periods
    let start_index() = ResizeArray.length result + periods - 1
    
    let current_min_idx = ref 0
    
    let find_min_idx end_idx =
        let mutable idx = end_idx
        for i in (end_idx - periods + 1) .. (end_idx-1) do
            if data.[i] < data.[idx] then idx <- i  
        idx 
    
    let compute data_idx = 
        if data_idx - periods >= !current_min_idx 
        then
            current_min_idx := find_min_idx data_idx 
        else        
            if data.[data_idx] < data.[!current_min_idx] then current_min_idx := data_idx
        data.[!current_min_idx]
    
    
    //update function
    let update() =
        check_errors()
        if enough_data() then
            for data_idx in start_index() to data_length() - 1 do                 
                ResizeArray.add result (compute data_idx)
                
    update()
    result, update


(*******************************************************************************************************************************)
(*******************************************************************************************************************************)


//Example of a function that outputs values which depend on the previously output values

 

//Exponential Moving Average

let ema data periods =
    //input verification
    let check_errors() =
        if data = null then invalid_arg "<ema> : data is null" 
        if periods <= 0 then invalid_arg "<ema> : periods<=0" 
    
    //output structure    
    let result = new ResizeArray<float>()    
    
    //computation helpers
    let data_length() = ResizeArray.length data
    let enough_data() = data_length() >= periods
    let start_index() = ResizeArray.length result + periods - 1
    
    let periods_f = float_of_int periods
    let k = 2.0 / (1.0 + periods_f)
    let compute data_idx = 
        let offset = data_idx - periods
        result.[offset] + (k * (data.[data_idx] - result.[offset]))
    
    
    //update function
    let update() =
        check_errors()
        if enough_data() then
            if ResizeArray.length result = 0 then
                ResizeArray.add result 0.0
                for data_idx in 0 .. periods-1 do
                    result.[0] <- result.[0] + (data.[data_idx]/periods_f)
            
            for data_idx in start_index() to data_length() - 1 do
                ResizeArray.add result (compute data_idx)
    
    update()
    result, update


(*******************************************************************************************************************************)
(*******************************************************************************************************************************)

//Example of the current composition issue
//
//I start by defining a function <gema>
//I then use it in another function which could be defined as let bar = gd >> gd >> gd
//it could... if we didn't return an <update> function


//Generalized Double Exponential Moving Average

let gdema data periods factor =  
    try
        //component of the transform
        let ema_, update_ema = ema data periods
        let ema_of_ema, update_ema_of_ema = ema ema_ periods
    
        //output structure    
        let result = new ResizeArray<float>()     
    
        //computation helpers
        let data_length() = ResizeArray.length data
        let enough_data() = data_length() >= periods + periods - 1
        let start_index() = ResizeArray.length result + 2 *(periods - 1)
    
        let one_plus_factor = 1.0 + factor
        
        let compute data_idx =
            let offset_ema = data_idx - periods + 1
            let offset_ema_of_ema = offset_ema - periods + 1
            (ema_.[offset_ema] * one_plus_factor) - (ema_of_ema.[offset_ema_of_ema] * factor)
    
        //update function
        let update() =
            update_ema()
            update_ema_of_ema()
            if enough_data() then
                for data_idx in start_index() to data_length() - 1 do
                    ResizeArray.add result (compute data_idx)
        
        update()
        result, update
            
    with e -> invalid_arg ("<gdema> -> " ^ e.Message)
    

//Composed function

//T3

let t3 data periods volume_factor =
    try   
        
        //computation helpers
        let gd, update_gd = gdema data periods volume_factor
        let gd_of_gd, update_gd_of_gd = gdema gd periods volume_factor
        let result, update_gd_of_gd_of_gd = gdema gd_of_gd periods volume_factor
        
        //update function
        let update() =
            update_gd()
            update_gd_of_gd()
            update_gd_of_gd_of_gd()
        
        update()
        result, update

    with e -> invalid_arg ("<t3> -> " ^ e.Message)
By on 4/26/2007 12:29 PM ()

Since to compute the next point of exponential moving average requires only the last output value and current input value you can write it as a transform function over seq's like this

1
2
3
4
5
6
7
8
9

let ema period (inp : #seq<double>) =
  let sum xs = fold (fun s x -> s + x) 0 xs
  let head = truncate period inp
  let tail = drop period inp
  let start = (sum head) / period
  let k = 2.0 / (1.0 + period)
  let update last_outp curr_inp = 
    last_outp + k * (curr_inp - last_outp)
  scan update start tail

Where 'drop' is the opposite to 'truncate': it drops the first n elements from a seq. Now you can compose 'ema n' with itself. You can do the same for minimum too but it's a bit harder because you need to carry more complex state between outputs.

Using seq to move data around is very convenient but it may not be suitable depending on how the data is generated and consumed in your application.

- Greg

By on 4/28/2007 12:22 AM ()

Thanks for your help. I'll probably go throgh the use of "static" seq.

I have a question however, regarding the following piece of code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let medprice (h :> seq<float>) (l :> seq<float>) =
    //input verification
    let check_errors() =
        if h = null || l = null then
            invalid_arg "<medprice> : at least one of h and l is null" 
        let len_h = Seq.length h
        if len_h <> Seq.length l 
            then invalid_arg "<medprice> : h and l don't have the same length"  
            else
                let i = ref (-1)
                let check h l = incr i ; if h < l then invalid_arg ("<medprice> : h and l are not consistent (h >= l), see for instance at position " ^ (string_of_int !i))
                Seq.iter2 check h l 
    
    check_errors()

    let compute h l = (h+l)/2.0
    Seq.map2 compute h l

When I send it to fsi, it refuses to accept float arrays as inputs, while float arrays should be constrainable to seq<float> (it does work with your ema function). Notwithstanding the signature shown in Intellisense is of type 

1

^a when  ^a : null and ^a :> seq<float>

.

Any idea?

Thanks a lot for your help !

FWIW (ie not much), here are a few fnuctions I used along the way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

 

(*******************************************************************************************************************************)
// Existing Modules Extensions
(*******************************************************************************************************************************)

module IEnumerator =
    begin
        
        open System.Collections.Generic
        
        let iter3 f (e1 :> IEnumerator<'a>) (e2 :> IEnumerator<'b>) (e3 :> IEnumerator<'c>) = 
            while 
                (   let n1 = e1.MoveNext()
                    let n2 = e2.MoveNext()
                    let n3 = e3.MoveNext()
                    if n1 <> n2 || n1 <> n3 then invalid_arg "Seq.iter3: the collections have different lengths";
                    n1
                ) do
                    f e1.Current e2.Current e3.Current
            done    
            
        let iter4 f (e1 :> IEnumerator<'a>) (e2 :> IEnumerator<'b>) (e3 :> IEnumerator<'c>) (e4 :> IEnumerator<'d>) = 
            while 
                (   let n1 = e1.MoveNext()
                    let n2 = e2.MoveNext()
                    let n3 = e3.MoveNext()
                    let n4 = e4.MoveNext()
                    if n1 <> n2 || n1 <> n3 || n1 <> n4 then invalid_arg "Seq.iter4: the collections have different lengths";
                    n1
                ) do
                    f e1.Current e2.Current e3.Current e4.Current
            done    
    end
    
    
module Seq =
    begin
        
        open System.Collections.Generic
        open Seq                          
        
        let drop n (x :> seq<'a>) = 
            assert (n >= 0)
            generate 
              ( fun () -> ref 0, x.GetEnumerator())
              ( fun (i, ie) -> 
                    let rec take() =
                        if not (ie.MoveNext()) then None
                        else 
                            if !i < n then 
                                incr i 
                                take()
                            else
                                Some ie.Current
                    take()
              )                            
              ( fun (_,ie) -> ie.Dispose() )
              

          
        let iter3 f (ie1 :> IEnumerable<'a>) (ie2 :> IEnumerable<'b>)  (ie3 :> IEnumerable<'c>) = 
            using (ie1.GetEnumerator()) (fun ie1 -> 
                using (ie2.GetEnumerator()) (fun ie2 ->             
                    using (ie3.GetEnumerator()) (fun ie3 -> 
                        IEnumerator.iter3 f ie1 ie2 ie3)))

          
        let iter4 f (ie1 :> IEnumerable<'a>) (ie2 :> IEnumerable<'b>)  (ie3 :> IEnumerable<'c>) (ie4 :> IEnumerable<'d>) = 
            using (ie1.GetEnumerator()) (fun ie1 -> 
                using (ie2.GetEnumerator()) (fun ie2 ->             
                    using (ie3.GetEnumerator()) (fun ie3 ->         
                        using (ie4.GetEnumerator()) (fun ie4 -> 
                            IEnumerator.iter4 f ie1 ie2 ie3 ie4)))) 


    end
By on 4/28/2007 7:47 AM ()

Hi Julien,

The first problem you mentioned relates to the use of "null" equality checks. When you mouse-hover over "medprice" you see the type

1
2
3
4

 

seq<float> -> seq<float> -> seq<float>

To be usable at mutliple types you would want to see:

1
2
3
4

 

#seq<float> -> #seq<float> -> seq<float>

Which you see if you delete the lines

1
2

        if h = null || l = null then
            invalid_arg "<medprice> : at least one of h and l is null"

Equality checking is not the recommended technique for checking for nulls, especially against polymorphic values. (The "#seq<_>" representa a polymorphic value with a constraint that it implements the seq<_> interface). Instead I recommend you use the following:

1
2
3
4
5
6
7
8
9
10
11

 

let isNull (x:'a) =
   match box x with null -> true | _ -> false

...

        if isNull h || isNull l then
            invalid_arg "<medprice> : at least one of h and l is null"

Your problem then goes away, because we're not requriing the the polymorphic input support "null", which was the cause of your loss of polymorphism.

I'll add this to the Expert F# book.

Don

By on 4/28/2007 1:38 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper