f# - 在 F# 中对一系列相等的字符进行切片/分组

Question

我需要提取文本中相等字符的序列。

例如:字符串 "aaaBbbccccccccDaBBBzcc11211" 应该被转换成一个字符串列表，比如["aaa";"B";"bb";"ccccccc";"D";"a";"BBB";"z";"cc";"11";"2";"11 "].

到目前为止，这是我的解决方案:

let groupSequences (text:string) = 

    let toString chars =
        System.String(chars |> Array.ofList)

    let rec groupSequencesRecursive acc chars = seq {
        match (acc, chars) with
        | [], c :: rest -> 
            yield! groupSequencesRecursive [c] rest
        | _, c :: rest when acc.[0] <> c -> 
            yield (toString acc)
            yield! groupSequencesRecursive [c] rest
        | _, c :: rest when acc.[0] = c -> 
            yield! groupSequencesRecursive (c :: acc) rest
        | _, [] -> 
            yield (toString acc)
        | _ -> 
            yield ""
    }

    text
    |> List.ofSeq
    |> groupSequencesRecursive []

groupSequences "aaaBbbcccccccDaBBBzcc11211"
|> Seq.iter (fun x -> printfn "%s" x)
|> ignore

我是 F# 新手。

这个解决方案可以更好吗？

Answer 1

这里是一个完全通用的实现:

let group xs =
    let folder x = function
        | [] -> [[x]]
        | (h::t)::ta when h = x -> (x::h::t)::ta
        | acc -> [x]::acc
    Seq.foldBack folder xs []

这个函数的类型是seq<'a> -> 'a list list when 'a : equality , 所以不仅适用于字符串，而且适用于任何(有限)元素序列，只要元素类型支持相等比较。

与 OP 中的输入字符串一起使用，返回值不是完全预期的形状:

> group "aaaBbbcccccccDaBBBzcc11211";;
val it : char list list =
  [['a'; 'a'; 'a']; ['B']; ['b'; 'b']; ['c'; 'c'; 'c'; 'c'; 'c'; 'c'; 'c'];
   ['D']; ['a']; ['B'; 'B'; 'B']; ['z']; ['c'; 'c']; ['1'; '1']; ['2'];
   ['1'; '1']]

而不是 string list , 返回值为 char list list .您可以使用 map 轻松地将其转换为字符串列表。 :

> group "aaaBbbcccccccDaBBBzcc11211" |> List.map (List.toArray >> System.String);;
val it : System.String list =
  ["aaa"; "B"; "bb"; "ccccccc"; "D"; "a"; "BBB"; "z"; "cc"; "11"; "2"; "11"]

这利用了 String采用 char[] 的构造函数重载作为输入。

如最初所述，此实现是通用的，因此也可以与其他类型的列表一起使用；例如整数:

> group [1;1;2;2;2;3;4;4;3;3;3;0];;
val it : int list list = [[1; 1]; [2; 2; 2]; [3]; [4; 4]; [3; 3; 3]; [0]]