排序和运行查询示例

Question

我想获得一些关于如何使用F#/functional编程在列表中搜索重复值的指针和/or示例代码。

考虑以下用例:给定每个日期的日期和最高温度的列表/数组/序列，我想提取出连续n天温度大于给定阈值的初始日期。

这种类型的查询的另一示例将是搜索股票价格历史表/列表，以查找在指定间隔(例如，至少30天)内保持在那里的给定阈值以上的价格。在这种情况下，我要查找第一次超过阈值的初始日期。

提亚

Answer 1

虽然我喜欢Tomas代码的简洁性，但我不禁认为他暗示的更有效的版本在这里确实是强制性的，特别是如果实际的比较逻辑比简单的整数比较更昂贵的话。我提交以下摘要：

let findWindowBeginnings predicate minWindowSize data =
    if minWindowSize < 2 then
        invalidArg "minWindowSize" "minWindowSize must be greater than 1"

    ((None, []), data)
    ||> Seq.fold (fun (window, acc) x ->
        if predicate x then
            match window with
            | Some (start, size) -> let size' = size + 1
                                    let acc' = if size' = minWindowSize
                                               then start::acc
                                               else acc
                                    Some (start, size'), acc'
            | _                  -> Some (x, 1), acc
        else None, acc)
    |> snd
    |> List.rev

date+temperature元组序列的用例如下所示：

let findHeatwaveBeginnings tempThreshold consecutiveDays data =
    (consecutiveDays, data)
    ||> findWindowBeginnings (snd >> (<) tempThreshold)
    // alternatively, if you're not a fan of point-free style code:
    //  findWindowBeginnings (fun (_, maxTemp) -> maxTemp > tempThreshold)
    |> List.map fst

因为findWindowBeginnings是由Seq.fold驱动的，所以它当然可以自然地与数组和列表一起工作。此外，findWindowBeginnings对于要检查的数据类型是完全不可知的，因为您传入的谓词执行数据外省，并且谓词当然可以作用于您喜欢的任何数据类型(元组、记录、适当的类/结构等)。唯一的要求是对输入数据进行逻辑排序。

F#代码片段链接：http://fssnip.net/3u

Answer 2

我可能会从一个效率较低但优雅的函数解决方案开始，它使用Seq.windowed函数(它将序列转换为指定大小的连续组的序列)：

source
// Create groups of specified size
|> Seq.windowed requiredLength
// Add starting indices to the sequence
|> Seq.mapi (fun i v -> i, v)
// Find all groups that contain only numbers larger than treshold
|> Seq.filter (fun (i, v) -> v |> Seq.forall ((<) treshold))
// Get indices of such groups
|> Seq.map fst

这将返回所有这样的组的索引，所以如果有多个重叠的组(即匹配条件的更大的序列)，那么您将获得所有起始索引。您可能只需要从结果中过滤连续的数字，从而只获得一个组的第一个索引(使用Seq.fold)。

为了获得更有效的版本，您需要编写一个递归函数来迭代数组或列表。您可能需要记住(在函数参数中)何时在treshold上找到最后一个值。(这本质上与命令式循环相同，除了在参数中使用递归函数和保持状态)。