f# sequence of running total

Question

Ok, this looks like it should be easy, but I'm just not getting it. If I have a sequence of numbers, how do I generate a new sequence made up of the running totals? eg for a sequence [1;2;3;4], I want to map it to [1;3;6;10]. In a suitably functional way.

ildjarn · Accepted Answer · 2017-08-05T08:32:31.467

16

Use List.scan:

let runningTotal = List.scan (+) 0 >> List.tail

[1; 2; 3; 4]
|> runningTotal
|> printfn "%A"

Seq.scan-based implementation:

let runningTotal seq' = (Seq.head seq', Seq.skip 1 seq') ||> Seq.scan (+)

{ 1..4 }
|> runningTotal
|> printfn "%A"

edited Aug 05 '17 at 08:32

answered Mar 29 '11 at 21:23

ildjarn

62,044
9
127
211

This is very cool, however I was hoping to do this for a Sequence rather than a list. – Aidan Mar 29 '11 at 21:33
@Aidan : Edited to add proper Seq.scan implementation. – ildjarn Mar 29 '11 at 21:37
Cool, that's the one. Thank you. – Aidan Mar 29 '11 at 21:47

score 14 · Answer 2 · answered Mar 29 '11 at 21:45

14

Another variation using Seq.scan (Seq.skip 1 gets rid of the leading zero):

> {1..4} |> Seq.scan (+) 0 |> Seq.skip 1;;
val it : seq<int> = seq [1; 3; 6; 10]

answered Mar 29 '11 at 21:45

Stephen Swensen

22,107
9
81
136

2

Thanks Daniel, F# feeds my sickness for succinct, elegant solutions. – Stephen Swensen Mar 29 '11 at 21:54
1

Me too. I fear my fate as a programmer is intertwined with F#. – Daniel Mar 29 '11 at 21:58

Laurent · Answer 3 · 2011-03-29T21:36:00.997

5

> Seq.scan (fun acc n -> acc + n) 0 [1;2;3;4];;
val it : seq<int> = seq [0; 1; 3; 6; ...]

With lists:

> [1;2;3;4] |> List.scan (fun acc n -> acc + n) 0 |> List.tail;;
val it : int list = [1; 3; 6; 10]

Edit: Another way with sequences:

let sum s = seq {
    let x = ref 0
    for i in s do
        x := !x + i
        yield !x
}

Yes, there's a mutable variable, but I find it more readable (if you want to get rid of the leading 0).

edited Mar 29 '11 at 21:36

answered Mar 29 '11 at 21:22

Laurent

2,951
16
19

cool, thank you. However it seems to generate a larger sequence, with an initial 0, do it doesn't feel like a true map. – Aidan Mar 29 '11 at 21:27

score 1 · Answer 4 · answered Jan 24 '19 at 13:29

Figured it was worthwhile to share how to do this with Record Types in case that's also what you came here looking for.

Below is a fictitious example demonstrating the concept using runner laps around a track.

type Split = double
type Lap = { Num : int; Split : Split }
type RunnerLap = { Lap : Lap; TotalTime : double }

let lap1 = { Num = 1; Split = 1.23 } 
let lap2 = { Num = 2; Split = 1.13 } 
let lap3 = { Num = 3; Split = 1.03 } 
let laps = [lap1;lap2;lap3]

let runnerLapsAccumulator =  
  Seq.scan 
    (fun rl l -> { rl with Lap = l; TotalTime = rl.TotalTime + l.Split }) // acumulator
    { Lap = { Num = 0; Split = 0.0 }; TotalTime = 0.0 } // initial state

let runnerLaps = laps |> runnerLapsAccumulator
printfn "%A" runnerLaps

score 0 · Answer 5 · answered Mar 29 '11 at 21:24

Not sure this is the best way but it should do the trick

  let input = [1; 2; 3; 4]
  let runningTotal = 
    (input, 0) 
    |> Seq.unfold (fun (list, total) ->
      match list with
      | [] -> 
        None
      | h::t -> 
        let total = total + h
        total, (t, total) |> Some)
    |> List.ofSeq

f# sequence of running total

5 Answers5

Linked