F# iterate over collection and build list

Question

I'm a .Net developer but new to F# and functional programming in general. Could someone point me in the right direction on the following problem:

I'm trying to iterate through a sequence of data I've read from CSV and build a sort of summary list. Pseudo-code is

type record = { Name:string; Time:DateTime;}

type summary = {Name:String; Start:DateTime; End:DateTime}

Example data: (Name Time)

• 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

I'm trying to iterate through the sequence and build a second sequence:

Seq<Summary>

(Name Start End)

• A 10:01 10:03
• B 11:15 11:30
• C 12:00 12:00
• A 13:01 13:05

Should I be piping the seq<record> to a function which iterates though in a foreach style, or is there a better way to do it? I have sorted the data in F# so the data is in time order. I don't have to worry about them being out of order.

If it were C# I'd probably do something like (Pseudo-code):

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 greatly appreciated!

Answer 1

Besides being declarative, functional programming encompasses the ability to abstract fundamental requirements of concrete types, that is, generic programming. Your algorithms will be applicable in a general way as long as the requirements (F# calls them constraints) are met, independent of concrete data structures.

As stated in your problem description, you might have a sequence (the most general data structure for an ordered collection of objects) of anything, from which the key can be extracted. Those keys shall be tested for inequality, so there's an equality constraint. Relying on the order of the sequence, the anythings are unconstrained. Represented as a F# signature, your input data is described by source:seq<'T> and the key projection 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's a possible implementation of this function, with no claims on efficiency or even correctness. Note that the equality constraint on 'Key is inferred, never explicitly spelled out.

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 )

Sample application on a concrete (X * string) list, the key being X. It works just as well on your seq<record> when the key is fetched by (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"))]

Answer 2

Functional programming is (among other nice things) declarative. Your problem could be stated as: group a sequence of string and times by strings, then retrieve for each group min time and max time.

That can translate 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 })

If you want you can also return a tuple of (name, min, max).