CODEWITHSUNDEEP
f#
CH Ben
CH Ben

Reputation: 1723

F#, loop control until n-2

I am currently learning functional programming and F#, and I want to do a loop control until n-2. For example:

Given a list of doubles, find the pairwise average,
e.g. pairwiseAverage [1.0; 2.0; 3.0; 4.0; 5.0] will give [1.5; 2.5; 3.5; 4.5]

After doing some experimenting and searching, I have a few ways to do it:

Method 1: 

let pairwiseAverage (data: List<double>) = 
        [for j in 0 .. data.Length-2 do  
            yield (data.[j]+data.[j+1])/2.0]

Method 2: 

let pairwiseAverage (data: List<double>) =
        let averageWithNone acc next =
            match acc with
            | (_,None)           -> ([],Some(next))
            | (result,Some prev) -> ((prev+next)/2.0)::result,Some(next))

        let resultTuple = List.fold averageWithNone ([],None) data

        match resultTuple with
        | (x,_) -> List.rev x

Method 3:

let pairwiseAverage (data: List<double>) =
        // Get elements from 1 .. n-1
        let after = List.tail data

        // Get elements from 0 .. n-2
        let before = 
            data    |> List.rev 
                    |> List.tail
                    |> List.rev

        List.map2 (fun x y -> (x+y)/2.0) before after

I just like to know if there are other ways to approach this problem. Thank you.

Upvotes: 3

Views: 162

Answers (4)

Soldalma
Soldalma

Reputation: 4758

The approaches suggested above are appropriate for short windows, like the one in the question. For windows with a length greater than 2 one cannot use pairwise. The answer by hlo generalizes to wider windows and is a clean and fast approach if window length is not too large. For very wide windows the code below runs faster, as it only adds one number and subtracts another one from the value obtained for the previous window. Notice that Seq.map2 (and Seq.map) automatically deal with sequences of different lengths.

let movingAverage (n: int) (xs: float List) =
    let init = xs |> (Seq.take n) |> Seq.sum
    let additions = Seq.map2 (fun x y -> x - y) (Seq.skip n xs) xs
    Seq.fold (fun m x -> ((List.head m) + x)::m) [init] additions
    |> List.rev
    |> List.map (fun (x: float) -> x/(float n))
xs = [1.0..1000000.0]
movingAverage 1000 xs
// Real: 00:00:00.265, CPU: 00:00:00.265, GC gen0: 10, gen1: 10, gen2: 0

For comparison, the function above performs the calculation above about 60 times faster than the windowed equivalent:

let windowedAverage (n: int) (xs: float List) =
    xs 
    |> Seq.windowed n 
    |> Seq.map Array.average
    |> Seq.toList
windowedAverage 1000 xs
// Real: 00:00:15.634, CPU: 00:00:15.500, GC gen0: 74, gen1: 74, gen2: 71

I tried to eliminate List.rev using foldBack but did not succeed.

Upvotes: 3

hlo
hlo

Reputation: 359

Using only built-ins:

list |> Seq.windowed 2 |> Seq.map Array.average

Seq.windowed n gives you sliding windows of n elements each.

Upvotes: 9

ildjarn
ildjarn

Reputation: 62985

A point-free approach:

let pairwiseAverage = List.pairwise >> List.map ((<||) (+) >> (*) 0.5)

Online Demo

Usually not a better way, but another way regardless... ;-]

Upvotes: 2

John Palmer
John Palmer

Reputation: 25516

One simple other way is to use Seq.pairwise

something like 

list |> Seq.pairwise |> Seq.map (fun (a,b) -> (a+b)/2.0)

Upvotes: 7

Related Questions