Объединить списки с одинаковыми головами в двухмерном списке

Question

Я работаю со списком списков в OCaml и пытаюсь написать функцию, которая объединяет все списки, которые имеют одну и ту же головку.Это то, что у меня есть, и я использую встроенную функцию List.hd, но неудивительно, что я получаю ошибку «hd» сбоя:

let rec combineSameHead list nlist = match list with
 | [] -> []@nlist
 | h::t -> if List.hd h = List.hd (List.hd t)
    then combineSameHead t nlist@uniq(h@(List.hd t))
    else combineSameHead t nlist@h;;

Так, например,если у меня есть этот список:

[[Sentence; Quiet]; [Sentence; Grunt]; [Sentence; Shout]]

Я хочу объединить его в:

[[Sentence; Quiet; Grunt; Shout]]

Функция uniq, которую я написал, просто удаляет все дубликаты в списке.Пожалуйста, дайте мне знать, как бы я закончил это.Заранее спасибо!

Answer 1

Во-первых, я обычно избегаю таких функций, как List.hd, так как обработка шаблонов обычно более понятна и менее подвержена ошибкам. В этом случае ваш if может быть заменен защищенными шаблонами (предложение when после шаблона). Я думаю, что причиной вашей ошибки является то, что ваш код завершается ошибкой, когда t равно []; Защищенные шаблоны помогают избежать этого, делая случаи более явными. Таким образом, вы можете сделать (x::xs)::(y::ys)::t when x = y как выражение в вашем выражении match, чтобы проверить, совпадают ли заголовки первых двух элементов списка. В OCaml не редкость иметь несколько последовательных шаблонов, которые идентичны, за исключением охранников.

Далее: вам не нужно []@nlist - это все равно, что просто написать nlist.

Кроме того, похоже, что nlist@h и подобные выражения пытаются объединить списки перед передачей их рекурсивному вызову; однако в OCaml приложение функции связывается более тесно, чем любой оператор, поэтому фактически добавляет результат рекурсивного вызова к h.

У меня нет правильной версии функции. Но я хотел бы начать с написания защищенных шаблонов, а затем посмотреть, как далеко вы продвигаетесь в этом.

Answer 2

Ваша предполагаемая операция имеет простое рекурсивное описание: рекурсивно обрабатывает хвост вашего списка, затем выполняет операцию вставки с заголовком, который ищет список, начинающийся с той же заголовка, и, если он найден, вставляет все элементы, кроме голова, а в противном случае добавляет его в конце. Затем вы можете отменить результат, чтобы получить нужный список.

В OCaml этот алгоритм будет выглядеть так:

let process list = 
  let rec insert (head,tail) = function
    | [] -> head :: tail 
    | h :: t -> 
      match h with 
      | hh :: tt when hh = head -> (hh :: (tail @ t)) :: t 
      | _ -> h :: insert (head,tail) t
  in
  let rec aux = function 
    | [] -> []
    | [] :: t -> aux t
    | (head :: tail) :: t -> insert (head,tail) (aux t) 
  in
  List.rev (aux list)

Answer 3

Вы можете многое сделать, просто используя стандартную библиотеку:

(* compares the head of a list to a supplied value.  Used to partition a lists of lists *)
let partPred x = function h::_ -> h = x
  | _ -> false

let rec combineHeads = function [] -> []
  | []::t -> combineHeads t (* skip empty lists *)
  | (hh::_ as h)::t -> let r, l = List.partition (partPred hh) t in (* split into lists with the same head as the first, and lists with different heads *)
  (List.fold_left (fun x y -> x @ (List.tl y)) h r)::(combineHeads l) (* combine all the lists with the same head, then recurse on the remaining lists *)

combineHeads [[1;2;3];[1;4;5;];[2;3;4];[1];[1;5;7];[2;5];[3;4;6]];;
- : int list list = [[1; 2; 3; 4; 5; 5; 7]; [2; 3; 4; 5]; [3; 4; 6]]

Это не будет быстрым (однако, partition, fold_left и concat - все O (n)).

Answer 4

Я, вероятно, сделал бы что-то в соответствии с тем, что предложил Антонакос. Это полностью исключило бы стоимость поиска в списке. Вы также можете обнаружить, что использование StringSet.t StringMap.t будет проще при дальнейшей обработке. Конечно, удобочитаемость имеет первостепенное значение, и я все еще нахожу это в соответствии с этими критериями.

module OrderedString =
    struct
        type t = string
        let compare = Pervasives.compare
    end

module StringMap = Map.Make (OrderedString)
module StringSet = Set.Make (OrderedString)

let merge_same_heads lsts =
    let add_single map = function
        | hd::tl when StringMap.mem hd map ->
            let set = StringMap.find hd map in
            let set = List.fold_right StringSet.add tl set in
            StringMap.add hd set map
        | hd::tl ->
            let set = List.fold_right StringSet.add tl StringSet.empty in
            StringMap.add hd set map
        | []     ->
            map
    in
    let map = List.fold_left add_single StringMap.empty lsts in
    StringMap.fold (fun k v acc-> (k::(StringSet.elements v))::acc) map []

Answer 5

Рассмотрите возможность использования Map или хеш-таблицы для отслеживания головок и элементов, найденных для каждой головы.Вспомогательный список nlist не очень полезен, если списки с одинаковыми заголовками не соседствуют, как в этом примере:

# combineSameHead [["A"; "a0"; "a1"]; ["B"; "b0"]; ["A"; "a2"]]
- : list (list string) = [["A"; "a0"; "a1"; "a2"]; ["B"; "b0"]]