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

如果您已经拥有命令式版本,则可以按照一组小步骤来转换为递归实现.

递归

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

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来完成工作.这个函数是递归的,并且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它的函数有点过于复杂而无法作为匿名函数传递,因此我选择将其定义为私有内部函数.它等同于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)]