F#构建一个列表/值数组+连续重复

Question

我需要像这样打包数据:

let data = [1; 2; 2; 3; 2; 2; 2; 4]
let packed = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]

每个项目都说明它在下一个之前存在多少次。但是，它必须适用于不相邻的重复。

我可以使用经典的命令式代码来解决这个问题，但想知道如何在功能上做到这一点。

另外， Seq.countBy不起作用，因为它考虑了所有值

Answer 1

如果你已经有命令式版本，可以follow a set of small steps to refector to a recursive implementation .

递归

虽然我不知道您的命令式版本是什么样的，但这是一个递归版本:

let pack xs =
    let rec imp acc = function
    | [] -> acc
    | h::t ->
        match acc with
        | [] -> imp [(h, 1)] t
        | (i, count) :: ta ->
            if h = i
            then imp ((i, count + 1) :: ta) t
            else imp ((h, 1) :: (i, count) :: ta) t
    xs |> imp [] |> List.rev

该函数的类型为 'a list -> ('a * int) list when 'a : equality .它使用名为 imp 的私有(private)“实现函数”。做这项工作。这个函数是递归的，并且贯穿整个累加器(称为 acc)。这个累加器是结果列表，类型为 ('a * int) list .

如果累加器列表为空，则原始列表的头部( h )，以及计数 1 , 被创建为一个元组，作为更新累加器的唯一元素， imp使用更新的累加器递归调用函数。

如果累加器已经包含至少一个元素，则通过模式匹配提取该元素，并将该元组中的元素( i )与 h 进行比较.如果 h = i ，累加器被更新；否则，将在 acc 上创建一个新元组.然而，在这两种情况下， imp用新的累加器递归调用。

您可以使用与原始元组等效的列表来调用它，如下所示:

> pack [1; 2; 2; 3; 2; 2; 2; 4];;
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]

折叠

一旦你有了一个递归版本，你通常就会有一个使用折叠的版本的秘诀。在这种情况下，由于上述 pack函数最终必须反转累加器(使用 List.rev )，右折叠是最合适的。在 F# 中，这是通过内置的 List.foldBack 完成的。功能:

let pack' xs =
    let imp x = function
        | (i, count) :: ta when i = x -> (i, count + 1) :: ta
        | ta -> (x, 1) :: ta
    List.foldBack imp xs []

在这种情况下，传递给 List.foldBack 的函数作为匿名函数传递有点过于复杂，所以我选择将其定义为私有(private)内部函数。相当于递归 imp上面使用的函数 pack函数，但您会注意到它不必递归调用自身。相反，它只需要返回累加器的新值。

结果是一样的:

> pack' [1; 2; 2; 3; 2; 2; 2; 4];;
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]