[(key, [..]) 形式的列表存在问题； ...]

Question

我正在尝试学习 OCaml，因为我是这门语言的新手，我偶然发现了这个问题，我似乎找不到一种方法来查看，在一个函数中，我需要合并这些列表中的两种，如果已经有一个带有键的元素，如果是的话如何连接后面的元素。将不胜感激任何指导。

例如，如果我有：

l1: [(k, [e]); (ka, [])]
l2: [(k, [f; g])]

我最终会怎样：

fl: [(k, [e; f; g]); (ka, [])]

基本上，如何从两个列表中过滤键

k

，同时使它们的元素组合起来。

Answer 1

标准 OCaml 库中有一些函数用于处理对列表，其中每对的第一个元素是键。您将在这里找到它们的描述：https://ocaml.org/releases/4.12/api/List.html在关联列表下。

我会重复@ivg 所说的话。如果您要处理的不仅仅是几对，这不是您想要解决问题的方式。

Answer 2

首先，使用列表作为映射是一个坏主意。最好使用专用数据结构，例如映射和哈希表。

直接回答您的问题，您可以使用

(@)

运算符连接两个列表，例如，

# [1;2;3] @ [4;5;6];;
              
- : int list = [1; 2; 3; 4; 5; 6]

如果你合并的时候不想有重复的元素，而且我感觉我在重复自己的话，那么集合用列表是不好的，最好使用集合、哈希集合等专用数据结构。但如果您想继续，则可以通过在添加元素之前检查某个元素是否已在列表中来合并两个列表而不重复。易于实现但难以运行，从某种意义上说，以这种方式合并两个列表需要二次时间。

如果您仍然想坚持使用对列表，那么您会发现 List.assoc 函数很有用，因为它通过键查找值。总体算法是，给定两个列表，

xs

和

ys

，使用

ys

作为初始值

xs

折叠

acc

的元素，并且对于

(ky,y)

中的每个

ys

如果

 ky

已经在

acc

中，找到与

ky

值

x

关联的值并删除 (

List.remove_assoc

) 它，然后合并

x

和

y

并将合并后的值添加到

acc

列表中，否则（如果不在 acc 中）只需在前面加上

(ky,y) to 

acc`。请注意，该算法不保留顺序，因此如果它很重要，您需要更复杂的东西。此外，如果您的键已排序，您可以使其更高效且更容易实现。

Answer 3

绝对有更有效的方法来实现这一点，但让我们将其分解为处理关联列表的不同步骤。

第 1 步： 将两个列表合并为一个列表。简单的。我们只使用

@

运算符。

# let merge lst1 lst2 =
    let combined = lst1 @ lst2 in
    combined;;
val merge : 'a list -> 'a list -> 'a list = <fun>
# merge [(1, [0]); (3, [6; 7])] [(1, [2])];;
- : (int * int list) list = [(1, [0]); (3, [6; 7]); (1, [2])]

第2步：根据第一个元素对该列表进行排序。让我们定义一个

sort_by

函数来简化此操作。

# let merge lst1 lst2 =
    let combined = lst1 @ lst2 in
    let sort_by f lst = List.sort (fun a b -> compare (f a) (f b)) lst in
    combined 
    |> sort_by fst;;
val merge : ('a * 'b) list -> ('a * 'b) list -> ('a * 'b) list =
  <fun>
# merge [(1, [0]); (3, [6; 7])] [(1, [2])];;
- : (int * int list) list = [(1, [0]); (1, [2]); (3, [6; 7])]

第3步：根据key进行分组，这很容易，因为它们都是列表中连续的元素。

# let merge lst1 lst2 =
    let combined = lst1 @ lst2 in
    let sort_by f lst = List.sort (fun a b -> compare (f a) (f b)) lst in
    let group_by f lst =
      let rec aux f lst acc =
        match lst, acc with
        | [], _ -> List.rev acc
        | hd::rest, [] -> aux f rest @@ hd::acc
        | (k, v)::rest, (k', v')::rest' when k = k' -> 
            aux f rest @@ (k, v@v')::rest'
        | (k, v)::rest, _ -> aux f rest @@ (k, v)::acc
      in
      aux f lst []
    in
    combined
    |> sort_by fst
    |> group_by fst;;
val merge : ('a * 'b list) list -> ('a * 'b list) list -> ('a * 'b list) list =
  <fun>
# merge [(1, [0]); (3, [6; 7])] [(1, [2])];;
- : (int * int list) list = [(1, [2; 0]); (3, [6; 7])]

Answer 4

我猜你这样做是为了练习列表。 我要做的是将已经找到的密钥存储在累加器中

let mergePairs yourList = 
  let rec aux accKeys = function
    | [] -> []
    | x :: xs -> 
        let k,v = x in 
        if (* k in accKeys *) then aux accKeys xs (*we suppress already existing keys*)
        else (k, v @ (* get all the list of the other pairs with key = k in xs*)) :: aux (k::accKeys) xs 
  in 
  aux [] yourList;;