CODEWITHSUNDEEP
listmaxocaml
ohcamel
ohcamel

Reputation: 19

Find max value in list of `(string * int) list`

I have a list of (string * int) list elements and I need to find the biggest int element and return the corresponding(string * int) element.

I have something like this atm, but problem is, I think my approach is more of "typical programming"

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]

What I tried to do is to loop through the list and add the string and int value in another list, then sort them, reverse it and then take the head, which should be the max int, then I need to return the pair in (string * int)

Upvotes: 0

Views: 628

Answers (3)

Mulan
Mulan

Reputation: 135397

You could write a generic maxBy function. This allows you to get the max of any list -

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 *)

It can be fun to rewrite the same function in various ways. Here's another encoding -

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> *)

Upvotes: 1

ivg
ivg

Reputation: 35280

Your code is not a well-formed OCaml code. It highlights, however, some number of issues with your understanding of OCaml.

First of all, by default, values in OCaml are immutable. For example,

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

You will get 11111111111 as the output. This is because, during the loop, you are just computing every time the x+1 expression, where x is always 0 and you will always get 1 as the result. This is because, let x = <expr> in <body> is not changing the existing variable x but is creating a new variable x (shadowing any previous definitions) and make it available in the scope of the <body> expression.

Concerning your problem in general, it should be solved as a recursive function greatest_element, which has the following definition,

  1. for an empty list [] it is undefined;
  2. for a list of one element [x] is it is x;
  3. otherwise, for a list of x::xs it is max x (greatest_element xs),

where max x y is x if it is greater or equal to y.

Finally, it looks like you have missed the first steps in OCaml and before solving this task you have to move back and to learn the basics. In particular, you have to learn how to call functions, bind variables, and in general what are the lexical conventions and syntax of the language. If you need pointers, feel free to ask.

Upvotes: 5

Horia Pantelimon
Horia Pantelimon

Reputation: 43

  1. First of all, it doesn't seem that you did any kind of sorting in the code that you provided.
  2. Assuming that your list is of type (string * int) list then a possible to find the element with the maximum integer using recursion:
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)]

Upvotes: 2

Related Questions