OCaml关于list的简单练习

Simple exercise of OCaml about list

大家早上好,

我必须做一个编程练习,但我卡住了!

好吧,练习需要一个函数,给定一个不为空的整数列表,return第一个出现次数最多的数字。

例如:

重要:练习必须是函数式编程

我的想法是:

let rec occurences_counter xs i =  match xs with
                                |[] -> failwith "Error"
                                |x :: xs when x = i -> 1 + occurences_counter xs i
                                |x :: xs -> occurences_counter xs i;;

在这个函数中我卡住了:

let rec mode (l : int list) : int = match l with
                                 |[] -> failwith "Error"
                                 |[x] -> x
                                 |x::y::l when occurences_counter l x >=  occurences_counter l y -> x :: mode l
                                 |x::y::l when occurences_counter l y > occurences_counter l x -> y :: mode l;;

提前致谢,我是编程和 Whosebug 方面的新手 对不起我的英语

一个解决方案:首先计算一对夫妇的列表(数量,出现次数)。 提示:使用 List.assoc.

然后,遍历该对列表以找到最大出现次数,然后 return 找到数字。

您需要在处理输入列表的同时维护一个状态,该状态存储每个数字的出现次数。基本上,状态可以是 map,其中键在列表元素的域中,值在自然数域中。如果您将使用 Map,算法将具有 O(NlogN) 的复杂性。您还可以使用关联列表(即 ('key,'value) list 类型的列表)来实现映射。这将导致二次复杂性。另一种方法是使用散列 table 或长度等于输入域大小的数组。两者都会给您带来线性复杂性。

收集统计数据后,(即从元素到其出现次数的映射)您需要遍历一组获胜者,然后选择列表中第一个。

在 OCaml 中,解决方案如下所示:

open Core_kernel.Std

let mode xs : int =
  List.fold xs ~init:Int.Map.empty ~f:(fun stat x ->
      Map.change stat x (function
          | None -> Some 1
          | Some n -> Some (n+1))) |>
  Map.fold ~init:Int.Map.empty ~f:(fun ~key:x ~data:n modes ->
      Map.add_multi modes ~key:n ~data:x) |>
  Map.max_elt |> function
  | None  -> invalid_arg "mode: empty list"
  | Some (_,ms) -> List.find_exn xs ~f:(List.mem ms)

算法如下:

  1. 运行 通过输入并计算每个元素的频率
  2. 运行通过统计和计算频谱(即从频率到元素的映射)。
  3. 获取频率最高的元素集合,并在输入列表中找到一个元素,即在这个集合中。

例如,如果我们取样本 [1;2;5;1;2;3;4;5;5;4;5;5]

  1. stats = {1 => 2; 2 => 2; 3 => 1; 4 => 2; 5 => 5}
  2. mods = {1 => [3]; 2 => [1;2]; 5 => [5]}

您需要安装 core 库才能使用它。使用 coretop 在顶层玩这个功能。或者 corebuild 编译它,像这样:

corebuild test.byte --

如果源代码存放在test.ml

一条建议:

如果您之前对列表进行排序,则可以简化您的算法。这具有 O(N log(N)) 复杂性。然后测量最长的相同数字序列。

这是一个很好的策略,因为您将工作的困难部分委托给了众所周知的算法。

它可能不是最漂亮的代码,但这是我想出的 (F#)。首先,我将每个元素转换为中间格式。此格式包含元素本身、出现的位置和出现的数量。

type T<'a> = {
    Element:  'a
    Position: int
    Occurred: int
}

想法是可以添加那些记录。所以你可以先变换每一个元素,然后把它们加在一起。所以像

这样的列表
[1;3]

将首先转换为

[{Element=1;Position=0;Occurred=1}; {Element=3;Position=1;Occurred=1}]

通过将两个相加,您只能将具有相同 "Element" 的相加。取两者中编号较小的位置,并将发生的位置加在一起。例如,如果您有

{Element=3;Position=1;Occurred=2} {Element=3;Position=3;Occurred=2}

结果会是

{Element=3;Position=1;Occurred=4}

我想到的想法是 Monoid。但是在真正的 Monoid 中,你必须想出你也可以将不同的元素加在一起。通过尝试一些东西,我觉得在更容易的地方添加相同元素的限制。我用这种类型创建了一个小模块。包括一些用于创建、添加和比较的辅助函数。

module Occurred =
    type T<'a> = {
        Element:  'a
        Position: int
        Occurred:  int
    }

    let create x pos occ = {Element=x; Position=pos; Occurred=occ}
    let sameElements x y = x.Element = y.Element
    let add x y =
        if not <| sameElements x y then failwith "Cannot add two different Occurred"
        create x.Element (min x.Position y.Position) (x.Occurred + y.Occurred)
    let compareOccurredPosition x y =
        let occ = compare x.Occurred y.Occurred
        let pos = compare x.Position y.Position
        match occ,pos with
        | 0,x -> x * -1
        | x,_ -> x

有了这个设置,我现在写了两个附加函数。一个 aggregate 函数首先将每个元素转换为 Occurred.T,然后按 x.Element 对它们进行分组(结果是列表的列表)。然后它使用内部列表上的 List.reduce 将具有相同元素的 Occurred 添加到一起。结果是一个列表,它只包含一个 Occurred.T 每个元素的第一个位置和出现的项目数量。

let aggregate =
    List.mapi (fun i x -> Occurred.create x i 1)
    >> List.groupBy (fun occ -> occ.Element)
    >> List.map (fun (x,occ) -> List.reduce Occurred.add occ)

您现在可以使用该聚合函数来实现不同的聚合逻辑。在您的情况下,您只想要出现次数最多和位置最低的那个。我写了另一个函数来做到这一点。

let firstMostOccurred =
    List.sortWith (fun x y -> (Occurred.compareOccurredPosition x y) * -1) >> List.head >> (fun x -> x.Element)

一张纸条。 Occurred.compareOccurredPosition 写道它按升序对所有内容进行排序。我认为人们希望默认情况下按此顺序从最小到最大的元素。所以默认情况下,第一个元素是出现次数最少且位置最大的元素。通过将它的结果与 -1 相乘,您将该函数转换为降序排序函数。我这样做的原因是我可以使用 List.head。我也可以使用 List.last 来获取最后一个元素,但我觉得最好不要为了获取最后一个元素而再次遍历整个列表。最重要的是,你不想要 Occurred.T 你想要元素本身,所以我打开 Element 以获得数字。

一切都在进行中

let ll = [
    [1;2;5;1;2;3;4;5;5;4;5;5]
    [2;1;2;1;1;2]
    [-1;2;1;2;5;-1;5;5;2]
    [7]
]

ll
|> List.map aggregate
|> List.map firstMostOccurred
|> List.iter (printfn "%d")

现在将打印此代码

5
2
2
7

它还有一些粗糙的边缘,比如

  1. Occurred.add 如果您尝试添加 Occurred with different Elements
  2. 会抛出异常
  3. List.head 为空列表抛出异常

并且在这两种情况下都没有编写代码来处理这些情况或确保不会引发异常。