Как реализовать функцию OCaml типа (строка * int) list -> (строка * int list) список, где список вывода представляет собой список элементов во входных данных - PullRequest
Новая
       79

Как реализовать функцию OCaml типа (строка * int) list -> (строка * int list) список, где список вывода представляет собой список элементов во входных данных

0 голосов
/ 23 февраля 2019

У меня вопрос: как мне преобразовать список пары строк и целых в список пар строк и int.

Например, если у меня есть список [("hello",1) ; ("hi", 1) ; ("hello", 1) ; ("hi", 1) ; ("hey",1 )], я должен получить обратно [("hello",[1;1]) ; ("hi", [1;1]) ; ("hey",[1])], где в основном из предыдущей функции, которую я написал, которая создает пары string * int в списке, я хочу сгруппировать каждую строку,то же самое в пару, у которой есть список единиц длины = до того, сколько раз эта точная строка появилась в паре из списка ввода.Извините, если моя формулировка сбивает с толку, но я совершенно заблудился в этой функции.Ниже приведен код, который я написал до сих пор: 

let transform5 (lst: (string *int) list) : (string *int list) list = 
                match lst with
                   | (hd,n)::(tl,n) -> let x,[o] = List.fold_left (fun (x,[o]) y -> if y = x then x,[o]@[1] else 
(x,[o])::y,[o]) (hd,[o]) tl in (x,[1])::(tl,[1])

Любая помощь приветствуется!

1 Ответ

0 голосов
/ 24 февраля 2019

Общие советы о том, как улучшить понимание основных понятий:

Код предлагает вам больше практиковаться в деструктурировании и манипулировании списками.Я рекомендую прочитать главу о списках и шаблонах в Real World Ocaml и потратить некоторое время на изучение первых 20 или около того 99 проблем OCaml .

Некоторые указатели на код, который вы написали до сих пор:

Я реорганизовал ваш код в строго эквивалентную функцию с некоторыми аннотациями, указывающими на проблемные области: 

let transform5 : (string * int) list -> (string * int list) list =
  fun lst ->
  let f (x, [o]) y =
    if y = x then          (* The two branches of this conditional are values of different types *)
      (x, [o] @ [1])       (* : ('a * int list) *)
    else
      (x, [o]) :: (y, [o]) (* : ('a * int list) list *)
  in
  match lst with
  | (hd, n) :: (tl, n) ->                      (* This will only match a list with two tuples *)
    let x, [o] = List.fold_left f (hd, [o]) tl (* [o] can only match a singleton list *)
    in (x, [1]) :: (tl, [1])                   (* Doesn't use the value of o, so that info is lost*)
   (* case analysis in match expressions should be exhaustive, but this omits
      matches for, [], [_], and (_ :: _ :: _) *)

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

Рефакторинг проблемы

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

В общем, функция типа 'a -> 'b можетследует понимать как проблему:

Учитывая x : 'a, создайте y : 'b где ...

Наша функция имеет тип (string * int) list -> (string * int list) list, и вы указываетепроблема довольно ясная, но я немного отредактировал, чтобы соответствовать формату:

Учитывая xs : (string * int) list, создайте ys: (string * int list) list, где я хочу сгруппировать каждую строку из xs, которая одинакова впара (string * int list) в ys, которая имеет список из единиц длины = того, сколько раз эта точная строка появилась в паре из xs.

Мы можем разбить это на два подпункта-проблемы:

Учитывая xs : (string * int) list, построить ys : (string * int) list list, где каждый y : (string * int) list в ys - это группа элементов в xs с одинаковыми string. 


let rec group : (string * int) list -> (string * int) list list = function
  | [] -> []
  | x :: xs ->
    let (grouped, rest) = List.partition (fun y -> y = x) xs in
    (x :: grouped) :: group rest

Учитывая xs : (string * int) list list, построить ys : (string * int list) list, где для каждой группы (string, int) list in xs у нас есть один (s : string, n : int list) в ys, где s - строка, определяющая группу, а n - список, содержащий все 1 в группе. 

let rec tally : (string * int) list list -> (string * int list) list = function
  | [] -> []
  | group :: xs ->
    match group with
    | [] -> tally xs (* This case shouldn't arise, but we match it to be complete *)
    | (s, _) :: _ ->
      let ones = List.map (fun (_, one) -> one) group in
      (s, ones) :: tally xs

Решением вашей первоначальной проблемы будет просто составление этих двух подзадач: 

let transform5 : (string * int) list -> (string * int list) list =
  fun xs -> (tally (group xs))

Надеюсь, это полезная иллюстрация одного из способов разложить проблемы такого рода.Однако в написанном мною коде есть некоторые очевидные недостатки: он неэффективен в том смысле, что он создает промежуточную структуру данных и должен многократно повторять первый список, чтобы сформировать свои группы, прежде чем, наконец, подвести итоги.Он также прибегает к явной рекурсии, тогда как было бы предпочтительнее использовать функции более высокого порядка, чтобы позаботиться об итерациях по спискам для нас (как вы пытались в своем примере).Попытка исправить эти дефекты может быть поучительной.

Пересмотр нашего контекста

Является ли проблема, которую вы поставили в этом вопросе SO, лучшей подзадачей из общей задачи, которую вы решаете?Вот два вопроса, которые возникли у меня:

Почему у вас есть (string * int) list, где значение int всегда 1 на первом месте?Несет ли это на самом деле больше информации, чем string list?

В общем, мы можем представить любое n : int с помощью int list, которое содержит только 1 с и имеет length = n.Почему бы просто не использовать здесь?

...