Найти максимальное значение в списке из `(string * int) list` - PullRequest
0 голосов
/ 10 июня 2019

У меня есть список (string * int) list элементов, и мне нужно найти самый большой элемент int и вернуть соответствующий элемент (string * int).

У меня есть что-то вроде этого банкомата, но проблема в том, что яя думаю, что мой подход больше к "типичному программированию"

let it = [] in
for x = 0 to length LIST - 1 do
let str = ((List.nth LIST x).string) in
let num = ((List.nth LIST x).int) in
let it = it @ [num, str] in 
let (str, num) = List.hd(List.rev it) in
[str, num]

Я пытался сделать цикл по списку и добавить строку и значение int в другой список, затем отсортировать их, повернуть вспять и затем взятьголова, которая должна быть max int, тогда мне нужно вернуть пару в (string * int)

Ответы [ 3 ]

5 голосов
/ 10 июня 2019

Ваш код не является правильно сформированным кодом OCaml. Тем не менее, он освещает ряд проблем, связанных с вашим пониманием OCaml.

Прежде всего, по умолчанию значения в OCaml являются неизменными . Например,

  let x = 0 in
  for i = 0 to 10 do
    let x = x + 1 in
    print_int x;
  done

Вы получите 11111111111 в качестве вывода. Это потому, что во время цикла вы просто каждый раз вычисляете выражение x+1, где x всегда равно 0, и в результате вы всегда получите 1. Это связано с тем, что let x = <expr> in <body> не изменяет существующую переменную x, но создает новую переменную x (скрывает все предыдущие определения) и делает ее доступной в области действия выражения <body>.

Что касается вашей проблемы в целом, она должна быть решена как рекурсивная функция greatest_element, которая имеет следующее определение

  1. для пустого списка [] не определено;
  2. для списка из одного элемента [x] это x;
  3. в противном случае для списка x::xs это max x (greatest_element xs),

где max x y равно x, если оно больше или равно y.

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

2 голосов
/ 10 июня 2019
  1. Прежде всего, не похоже, что вы делали какую-либо сортировку в код, который вы предоставили.
  2. Предполагая, что ваш список имеет тип (string * int) list тогда можно найти элемент с максимальное целое число с использованием рекурсии:
let max_in_list list =
    let rec auxiliary max_str max_int = function
    | [] 
        -> (max_str, max_int)
    | (crt_str, crt_int)::tail when crt_int > max_int 
        -> auxiliary crt_str crt_int tail
    | _::tail 
        -> auxiliary max_str max_int tail
    in
    match list with
    | [] 
        -> None
    | (fst_str, fst_int)::tail 
        -> Some (auxiliary fst_str fst_int tail)

let check = max_in_list [("some", 1); ("string", 3); ("values", 2)]
1 голос
/ 12 июня 2019

Вы можете написать общую функцию maxBy. Это позволяет получить максимум из любого списка -

let rec maxBy f = function
  | [] -> None
  | [ x ] -> Some x
  | x :: xs ->
      match (maxBy f xs) with
        | Some y when (f y) > (f x) -> Some y
        | _ -> Some x
(* val maxBy : ('a -> 'b) -> 'a list -> 'a option = <fun> *)

let data = [("a", 3); ("b", 2); ("c", 6); ("d", 1)]
(* val data : (string * int) list = [("a", 3); ("b", 2); ("c", 6); ("d", 1)]*)

maxBy (fun (_, num) -> num) data
(* - : (string * int) option = Some ("c", 6) *)

maxBy (fun (str, _) -> str) data
(* - : (string * int) option = Some ("d", 1) *)

maxBy (fun x -> x) [3; 2; 6; 1]
(* - : int option = Some 6 *)

maxBy (fun x -> x) ["c"; "d"; "b"; "a"]
(* - : string option = Some "d" *)

maxBy (fun x -> x) []
(* - : 'a option = None *)

Может быть интересно переписать одну и ту же функцию различными способами. Вот еще одна кодировка -

let maxBy f list =
  let rec loop r = function
    | [] -> r
    | x::xs when (f x) > (f r) -> loop x xs
    | _::xs -> loop r xs
  in
  match list with
    | [] -> None
    | x::xs -> Some (loop x xs)
(* val maxBy : ('a -> 'b) -> 'a list -> 'a option = <fun> *)
...