CODEWITHSUNDEEP
f#
Khaine775
Khaine775

Reputation: 2765

F# List.exists on two lists

I have two lists listA and listB where I want to return true if listB contains any element also in listA.

let listA = ["A";"B";"C"]
let listB = ["D";"E";"A"]

Should return true in this case. I feel like this should be easy to solve and I'm missing something fundamental somewhere.

For example, why can't I do like this?

let testIntersect = for elem in listA do List.exists (fun x -> x = elem) listB

Upvotes: 1

Views: 1694

Answers (3)

rmunn
rmunn

Reputation: 36688

One function that you could use is List.except, which is not yet documented (!) but can be seen in this pull request that was merged a couple of years ago. You'd probably use it like this:

let testIntersect a b =
    let b' = b |> List.except a
    // If b' is shorter than b, then b contained at least one element of a
    List.length b' < List.length b

However, this runs through list B about three times, once to do the except algorithm and once each to do both the length calls. So another approach might be to do what you did, but turn list A into a set so that the exists call won't be O(N):

let testIntersect a b =
    let setA = a |> Set.ofList
    match b |> List.tryFind (fun x -> setA |> Set.contains x) with
    | Some _ -> true
    | None   -> false

The reason I used tryFind is because List.find would throw an exception if the predicate didn't match any items of the list.

Edit: An even better approach is to use List.exists, which I temporarily forgot about (thanks to Honza Brestan for reminding me about it):

let testIntersect a b =
    let setA = a |> Set.ofList
    b |> List.exists (fun x -> setA |> Set.contains x)

Which, of course, is pretty much what you were originally wanting to do in your testIntersect code sample. The only difference is that you were using the for ... in syntax in your code sample, which wouldn't work. In F#, the for loop is exclusively for expressions that return unit (and thus, probably have side effects). If you want to return a value, the for loop won't do that. So using the functions that do return value, like List.exists, is the approach you want to take.

Upvotes: 3

TheInnerLight
TheInnerLight

Reputation: 12184

You can't write something like your example code because a plain for doesn't return a result, it just evaluates an expression for its side-effects. You could write the code in a for comprehension:

let testIntersect listA listB = 
    [for elem in listA do yield List.exists (fun x -> x = elem) listB]

Of course, this then returns a bool list rather than a single bool.

val testIntersect :
  listA:seq<'a> -> listB:'a list -> bool list when 'a : equality

let listA = ["A";"B";"C"]
let listB = ["D";"E";"A"]

testIntersect listA listB
val it : bool list = [true; false; false]

So, we can use the List.exists function to ensure that a true occurs at least once:

let testIntersect listA listB = 
    [for elem in listA do yield List.exists (fun x -> x = elem) listB]
    |> List.exists id

val testIntersect :
  listA:seq<'a> -> listB:'a list -> bool list when 'a : equality

val listA : string list = ["A"; "B"; "C"]
val listB : string list = ["D"; "E"; "A"]
val it : bool = false

It's pretty inefficient to solve this problem using List though, it's better to use Set. With Set, you can calculate intersection in O(log N * log M) time rather than O(N*M).

let testSetIntersect listA listB =
    Set.intersect (Set.ofList listA) (Set.ofList listB)
    |> Set.isEmpty
    |> not

Upvotes: 4

Petr
Petr

Reputation: 4280

let testIntersect listA listB = 
    (Set.ofList listA) - (Set.ofList listB) |> Set.isEmpty |> not

Upvotes: 2

Related Questions