F#迭代集合并构建列表

Question

F#迭代集合并构建列表

4

我是一名 .Net 开发人员，但对 F# 和函数式编程都比较新。请问有没有人能为我指点以下问题：

我正在尝试遍历从 CSV 中读取的数据序列并构建一种汇总列表。伪代码如下：

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

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

示例数据：（名称时间）

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

我想要遍历这个序列并建立第二个序列：

Seq<Summary>

(开始时间结束时间)

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

我应该将 seq<record> 管道传递给一个以 foreach 方式迭代的函数，还是有更好的方法可以完成？我已经在 F# 中对数据进行了排序，所以数据按时间顺序排列。我不必担心它们会乱序。

如果是 C#，我可能会执行以下伪代码:

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)
     }

}

非常感谢您的帮助！

- user2179721

3个回答

4

除了具有声明性外，函数式编程还包括抽象出具体类型的基本要求，即“泛型”编程。只要满足要求（F#称之为约束），您的算法就可以以一般方式应用于任何数据结构，而与具体的数据结构无关。

根据您的问题描述，您可能拥有一个序列（有序对象集合的最常见数据结构），其中包含各种任意对象，可以从中提取键值。这些键值需要进行不等比较，因此存在相等约束。根据序列的顺序，任何对象都没有限制。在 F# 签名中，输入数据的描述为：source:seq<'T>，键投影函数为：projection:('T -> 'Key) when 'Key : equality。

作为完整函数签名，我建议使用 projection:('T -> 'Key) -> source:seq<'T> -> seq<'T * 'T> when 'Key : equality。返回一对序列避免了引入附加的类型参数。它与输入匹配，除了一些有选择的重新排列之外。以下是该函数的一个可能实现，对效率甚至正确性不做任何保证。请注意，在 'Key 上的相等约束是被推断出来的，从未明确说明。

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 )

这是一个关于具体 (X * string) 列表 的样例应用程序，其中 X 是关键字。当关键字通过 (fun r -> r.Name) 获取时，它同样适用于您的 seq<record>。

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"))]

- kaefer

2

对于这种需要在迭代过程中保持一些状态的集合迭代问题，通常的做法是使用fold或递归。然而，在这里我倾向于使用unfold。

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()))

- hvester

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bartek Kobyłecki · Accepted Answer

函数式编程（Functional programming）是一种声明式的编程范式，它有很多优点。

您的问题可以描述为：将一系列字符串和时间按字符串分组，然后为每个组检索最小时间和最大时间。

这可以在 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 })

如果你愿意，你也可以返回一个元组（名字、最小值、最大值）。