F # iterating over a collection and assembly list
I am a .Net developer but new to F # and functional programming in general. Can anyone point me in the right direction on the following problem:
I am trying to iterate through a sequence of data that I read from a CSV and create a sort of pivot list. Pseudocode
type record = { Name:string; Time:DateTime;}
type summary = {Name:String; Start:DateTime; End:DateTime}
Sample data: (Name time)
- A 10:01
- A 10:02
- A 10:03
- B 11:15
- B 11:25
- B 11:30
- From 12:00
- A 13:01
- A 13:05
I am trying to iterate through a sequence and build a second sequence:
Seq<Summary>
(Title starts at the end)
- A 10:01 10:03
- B 11:15 11:30
- From 12:00 to 12:00
- A 13:01 13:05
Should I rewrite seq<record>
into a function that repeats, albeit in style foreach
, or is there a better way to do this? I have sorted the data in F # so that the data is in temporary order. I donโt need to worry about them being out of order.
If it were C # I would probably do something like (Pseudocode):
List<Summary> summaryData
foreach(var r in records)
{
Summary last = summaryData.LastOrDefault()
if(last == null)
{
summaryData.add( new Summary from r)
}
else
{
if(last.Name = r.Name)
{
last.End = r.Time
}
else
{
summaryData.add( new Summary from r)
}
}
Any help is greatly appreciated!
source to share
Beyond declarative programming, functional programming includes the ability to abstract the fundamental requirements of specific types, that is, general programming. Your algorithms will apply in general terms if the requirements (F # calls them constraints) are met independently of the specific data structures.
As stated in the problem description, you can have a sequence (the most common data structure for an ordered set of objects) of anything from which to extract a key. These keys are tested for inequality, so there is an equality constraint. Based on the order of the sequence, any things are unlimited. Represented as an F # signature, your input is described source:seq<'T>
by the key mapping function as projection:('T -> 'Key) when 'Key : equality
.
As a complete function signature, I would like to suggest projection:('T -> 'Key) -> source:seq<'T> -> seq<'T * 'T> when 'Key : equality
. Returning a sequence of pairs avoids introducing an additional type parameter. It matches the input except for some selective rearrangement. Here it is possible to perform this function without claims to be efficient or even correct. Note that the equality constraint 'Key
is not inferred, never explicitly specified.
let whenKeyChanges (projection : 'T -> 'Key) (source : seq<'T>) =
// Wrap in option to mark start and end of sequence
// and compute value of every key once
seq{ yield None
yield! Seq.map (fun x -> Some(x, projection x)) source
yield None }
// Create tuples of adjacent elements in order to
// test their keys for inequality
|> Seq.pairwise
// Project to singleton in case of the first and the
// last element of the sequence, or to a two-element
// sequence if keys are not equal; concatenate the
// results to obtain a flat sequence again
|> Seq.collect (function
| None, Some x | Some x, None -> [x]
| Some(_, kx as x), Some(_, ky as y)
when kx <> ky -> [x; y]
| _ -> [] )
// Create tuples of adjacent elements a second time.
|> Seq.pairwise
// Only the first and then every other pair will contain
// indentical keys
|> Seq.choose (fun ((x, kx), (y, ky)) ->
if kx = ky then Some(x, y) else None )
An example application on a specific (X * string) list
, key is X. It works just as well on yours seq<record>
when the key is retrieved (fun r -> r.Name)
.
type X = A | B | C
[ A, "10:01"
A, "10:02"
A, "10:03"
B, "11:15"
B, "11:25"
B, "11:30"
C, "12:00"
A, "13:01"
A, "13:05" ] |> whenKeyChanges fst
// val it : seq<(X * string) * (X * string)> =
// seq
// [((A, "10:01"), (A, "10:03")); ((B, "11:15"), (B, "11:30"));
// ((C, "12:00"), (C, "12:00")); ((A, "13:01"), (A, "13:05"))]
source to share
Functional programming is (among other nice things) declarative. Your problem can be formulated like this: group a sequence of lines and times by lines, and then extract the minimum time and maximum time for each group.
This can be translated to F #:
sequenceOfRecords
|> Seq.groupBy (fun r -> r.Name)
|> Seq.map (fun (name, records) ->
let times = Seq.map snd records
{ Name = name; Start = Seq.min times; End = Seq.max times })
You can also return a tuple (name, min, max) if you want.
source to share
For a problem like this, when you need to iterate over a collection that retains some state, while iterating over the usual approach would be to use fold or recursion. However, I tend to use a reversal here.
open System
type Record = { Name : string; Time : DateTime }
type Summary = { Name : String; Start : DateTime; End : DateTime }
let records = [ { Name = "A"; Time = DateTime(2015, 7, 24, 10, 1, 0) }
{ Name = "A"; Time = DateTime(2015, 7, 24, 10, 2, 0) }
{ Name = "A"; Time = DateTime(2015, 7, 24, 10, 3, 0) }
{ Name = "B"; Time = DateTime(2015, 7, 24, 11, 15, 0) }
{ Name = "B"; Time = DateTime(2015, 7, 24, 11, 25, 0) }
{ Name = "B"; Time = DateTime(2015, 7, 24, 11, 30, 0) }
{ Name = "C"; Time = DateTime(2015, 7, 24, 12, 0, 0) }
{ Name = "A"; Time = DateTime(2015, 7, 24, 13, 1, 0) }
{ Name = "A"; Time = DateTime(2015, 7, 24, 13, 5, 0) } ]
let createSummary records =
let times = records |> Seq.map (fun r -> r.Time)
{ Name = (Seq.head records).Name
Start = Seq.min times
End = Seq.max times }
let summarize records =
records
|> Seq.unfold (fun (restOfRecords : seq<Record>) ->
if Seq.isEmpty restOfRecords then None
else
let firstRecord = Seq.head restOfRecords
let belongsToSameGroup (r : Record) = firstRecord.Name = r.Name
let thisGroup = restOfRecords |> Seq.takeWhile belongsToSameGroup
let newRest = restOfRecords |> Seq.skipWhile belongsToSameGroup
Some (createSummary thisGroup, newRest) )
summarize records
|> Seq.iter (fun s -> printfn "Name: %s, Start: %s, End: %s" s.Name (s.Start.ToString()) (s.End.ToString()))
source to share