CODEWITHSUNDEEP
f#
Razoll
Razoll

Reputation: 107

Compare values in a list

Trying to conceptualize how I would compare several values in a list to find the largest value, without using mutable variables.

For example in an imperative language I could simply store a max variable that gets updated every time the iteration finds a larger value in the list. Like such:

max = 0;
for i in list
  if i > max
    max = i

Now, in functional programming if i had a list, for example [1; 2; 3] How would I get around the issue of using a max variable?

Upvotes: 0

Views: 118

Answers (1)

Jarak
Jarak

Reputation: 982

The easy answer would be to use let maxValue = List.max theList.

If you were wanting to 'roll your own' without using an explicitly mutable variable, the obvious way is to use a recursive function. Personally, I would define it like so:

let listMax theList = 
    let rec maxHelper remainingList maxSoFar = 
        match remainingList with
        | [] -> maxSoFar
        | h :: t -> 
                      if h > maxSoFar then
                          maxHelper t h
                      else
                          maxHelper t maxSoFar

    maxHelper theList (List.head theList)

Note that this implementation as presented would throw an exception with an empty input list (also, I haven't actually tested this, so there might be a slight error in there). The reason I have done it this way is that it uses tail recursion, which should mean it's roughly as efficient as a mutable solution, but keeps the complexity of the exposed function signature to the bare minimum.

Alternatively, this could also be done fairly easily with a List.fold call. E.g. 

List.fold (fun (nextElem, maxSoFar) -> 
    if nextElem > maxSoFar then nextElem else maxSoFar) (List.head theList) theList

Same proviso about not having tested it applies to this too.

In both of the presented cases, this could be made more generic to apply to any binary operation that returns a boolean, by using another parameter that is a function which carries out said operation. E.g.

List.fold (fun (nextElem, maxSoFar) -> 
        if comparatorFunction nextElem maxSoFar then nextElem else maxSoFar)
        (List.head theList) theList

Upvotes: 2

Related Questions