CODEWITHSUNDEEP
ocaml
JJY
JJY

Reputation: 11

Finding two max in list

How do I find two max value in a list and sum up, not using rec, only can use List.fold_left or right and List.map? I used filter, but it's not allowed, anyways I can replace the filter?

let max a b =
  if b = 0 then a 
  else if a > b then a
  else b;;
                  
let maxl2 lst = 
  match lst with 
  | [] -> 0
  | h::t -> 
    let acc = h in 
    List.fold_left max acc lst + 
    List.fold_left 
      max acc 
      (List.filter (fun x -> (x mod List.fold_left max acc lst) != 0) lst);;

Upvotes: 0

Views: 230

Answers (3)

coredump
coredump

Reputation: 38924

Often, functions called by fold use an accumulator that is simple enough to be stored as an anonymous tuple. But this can become hard to understand when you are dealing with complex behaviors: you have to consider different corner cases, like what is the initial accumulator value? what is the regular behavior of the function, ie. when the accumulator has encountered enough values? what happens before that?

For example here you have to keep track of two maximal values (the general case), but your code has a build-up phase where there is only one element being visited in the list, and starts with initially no known max value. This kind of intermediate states is IMO the hardest part of using fold (the more pleasant cases are when the accumulator and list elements are of the same type).

I'd recommend making it very clear what type the accumulator is, and write as many helper functions as possible to clear things up. To that effect, let's define the accumulator type as follows, with all different cases treated explicitly:

type max_of_acc = 
  | SortedPair of int * int (* invariant: fst <= snd *)
  | Single of int
  | Empty

Note that this isn't the only way to do it, you could keep a list of maximum values, initially empty, always sorted, and of size at most N, for some N (and then you would solve a more general case, ie. a list of N highest values). But as an exercise, it helps to cover the different cases as above.

For example, at some point you will need to compute the sum of the max values.

let sum_max_of m = match m with
    | Empty -> 0
    | Single v -> v
    | SortedPair (u,v) -> u+v;;

I would also define the following helper function:

let sorted_pair u v = if u <= v then SortedPair (u,v) else SortedPair (v, u)

Finally, your function would look like this:

let fold_max_of acc w = match acc with
    | Empty -> ...
    | Single v -> ...
    | SortedPair (u, v) -> ...

And could be used in the following way:

# List.fold_left fold_max_of Empty [1;2;3;5;4];;
- : max_of = SortedPair (4, 5)

Upvotes: 1

Chris
Chris

Reputation: 36621

To build on what Jeffrey has said, List.fold_left looks at one element in a list at a time and an accumulator. Let's consider a list [1; 3; 7; 0; 6; 2]. An accumulator that makes sense is a tuple with the first element being the largest and the second element representing the second largest. We can initially populate these with the first two elements.

The first two elements of this list are [1; 3]. Finding the max of that we can turn this into the tuple (3, 1). The remainder of the list is [7; 0; 6; 2].

First we consider 7. It's bigger than 3, so we change the accumulator to (7, 3). Next we consider 0. This is smaller than both elements of the accumulator, so we make no changes. Next: 6. This is bigger than 3 but smaller than 7, so we updated the accumulator to (7, 6). Next: 2 which is smaller than both, so no change. The resulting accumulator is (7, 6).

Actually writing the code for this is your job.

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

List.fold_left is very powerful and can be used to implement List.filter, List.map, List.rev and so on. So it's not much of a restriction. I would assume the purpose of the exercise is for you to learn about the folds and what they can do.

If your solution with List.filter actually works, you should be able to replace List.filter by one you wrote yourself using List.fold_left. The basic idea of a fold is that it builds up a result (of any type you choose) by looking at one element of the list at a time. For filter, you would add the current element to the result if it passes the test.

However I have to wonder whether your solution will work even with List.filter. I don't see why you're using mod. It doesn't make a lot of sense. You seem to need an equality test (= in OCaml). You can't use mod as an equality test. For example 28 mod 7 = 0 but 28 <> 7.

Also your idea of filtering out the largest value doesn't seem like it would work if the two largest values were equal.

My advice is to use List.fold_left to maintain the two largest values you've seen so far. Then add them up at the end.

Upvotes: 2

Related Questions