Clever Geek Handbook

Why doesn't max (Operator) return the longest list?

I want to find the longest of the two lists. Consider the following code example:

let xs = ['B']
let ys = ['A'; 'B']
let longest = max xs ys
printfn "%A" longest

Contrary to my expectation, the output of this program ['B']

is not ['A'; 'B']

.

Why List<'T>

implement max

here? How / where exactly is this implementation defined?

I see what max

requires comparison

, what I believe the implementation implies IComparable

. List<'T>

does this automatically using the attribute StructuralComparison

. But what does this automatic implementation look like?

What is the shortest alternative I can use to get the longest of the two lists?

+3


source to share


5 answers


F # compares lists item by item. As 'B' > 'A'

therefore, he considers the first list> the second (lexicographic order) and breaks further comparison. You can use a property .Length

on a list to compare lengths. For example, for example:

let longest = if xs.Length > ys.Length then xs else ys


Result:

val longest : char list = ['A'; 'B']
+6


source


Here is a reusable function for checking the greater length of any two sequences:



let longest x y = match (Seq.length x > Seq.length y) with
                  |true -> x
                  |false -> y
+1


source


If you want a general way to compare two objects by some property, you can create a function maxBy

:

let maxBy f x y = Array.maxBy f [|x; y|]

then you can do:

let longest = maxBy List.length xs ys

or directly:

let longest = Array.maxBy List.length [|xs; ys|]
+1


source


You can write a function maxBy

:

let maxBy f a b = if f b > f a then b else a

Then call it like this:

let longestList = maxBy List.length xs ys

Since List.length is O (N), performance will suffer if the lists are very long. The operation will be O (N1 + N2), where N1 and N2 are the lengths of the lists.

The performance will be useless if it is long and the other is short. To avoid this, you can write a more specific function. This function is O (min (N1, N2)):

let getLongest list1 list2 =
    let rec helper = function
    | [], _ -> list2
    | _, [] -> list1
    | _ :: t1, _ :: t2 -> helper (t1, t2)
    helper (list1, list2)

let longestList = getLongest xs ys
+1


source


Here's a reusable function that will return the longest list from a list of lists :

let longest ll = ll |> List.sortBy List.length |> List.rev |> List.head

Examples:

> longest [xs; ys];;
val it : char list = ['A'; 'B']
> let zs = ['A' .. 'D'];;
val zs : char list = ['A'; 'B'; 'C'; 'D']
> longest [xs; zs; ys];;
val it : char list = ['A'; 'B'; 'C'; 'D']

However, this won't work if you enter an empty list, as you need to define exactly what you need for the behavior to be in this case.

0


source






More articles:


All Articles