F# Compare two lists, take different actions

Question

How to idiomatically do this: given a list of stuff, find if an item in it meets a criteria in another list, if it does do one action, if it doesn't do another action. I saw code doing this in C# and I wondered how I would do it in F#.

Here is the code as it would be implemented imperatively in F#:

let find list1 list2 =
    for i in list1 do
        let mutable found = false
        for k in list2 do
            if i=k then    //if the criteria is equals
                found <- true
                //do task using k & i
        if found =false then   
            //do other task using i
            ()

How can this be done more functionally?

Answer 1

Same idea as yours, only slightly clearer. I distilled your "criteria" into an argument function f : 'a -> 'b -> bool.

let find f xs ys = 
    xs |> List.map (fun x -> (x, List.tryFind (f x) ys))
       |> List.iter (function (x, None) -> printfn "%A" x
                            | (x, Some y) -> printfn "%A,%A" x y)

You'd use it like this:

find (=) [1;2;3;4] [1;3] (* Prints 1,1 -- 2 -- 3,3 -- 4. *)

Answer 2

Short answer

let crossJoin xs ys =
    xs
    |> Seq.map (fun x -> ys |> Seq.map (fun y -> (x, y)))
    |> Seq.concat
let group f xs ys = ys |> crossJoin xs |> Seq.groupBy f

Longer answer

In general, when you need to compare every element in one list with every element in another list, you'll need a Cartesian product, which you can define like this:

let crossJoin xs ys =
    xs
    |> Seq.map (fun x -> ys |> Seq.map (fun y -> (x, y)))
    |> Seq.concat

If, for example, you have:

let integers = [0 .. 10] |> List.toSeq
let strings = [0 .. 5] |> Seq.map string

the Cartesian product would be:

> crossJoin integers strings |> Seq.toList;;
val it : (int * string) list =
  [(0, "0"); (0, "1"); (0, "2"); (0, "3"); (0, "4"); (0, "5"); (1, "0");
   (1, "1"); (1, "2"); (1, "3"); (1, "4"); (1, "5"); (2, "0"); (2, "1");
   (2, "2"); (2, "3"); (2, "4"); (2, "5"); (3, "0"); (3, "1"); (3, "2");
   (3, "3"); (3, "4"); (3, "5"); (4, "0"); (4, "1"); (4, "2"); (4, "3");
   (4, "4"); (4, "5"); (5, "0"); (5, "1"); (5, "2"); (5, "3"); (5, "4");
   (5, "5"); (6, "0"); (6, "1"); (6, "2"); (6, "3"); (6, "4"); (6, "5");
   (7, "0"); (7, "1"); (7, "2"); (7, "3"); (7, "4"); (7, "5"); (8, "0");
   (8, "1"); (8, "2"); (8, "3"); (8, "4"); (8, "5"); (9, "0"); (9, "1");
   (9, "2"); (9, "3"); (9, "4"); (9, "5"); (10, "0"); (10, "1"); (10, "2");
   (10, "3"); (10, "4"); (10, "5")]

Given the crossJoin function, you can easily group these tuples according to a comparison function:

let group f xs ys = ys |> crossJoin xs |> Seq.groupBy f

Example:

> group (fun (x, y) -> x.ToString() = y) integers strings |> Seq.toList;;
val it : (bool * seq<int * string>) list =
  [(true, seq [(0, "0"); (1, "1"); (2, "2"); (3, "3"); ...]);
   (false, seq [(0, "1"); (0, "2"); (0, "3"); (0, "4"); ...])]

Now you have a sequence of tuples, where the first value in the tuple is either true or false.

If, for example, you want to perform a particular action for all matches, you can unpack the groups:

> group (fun (x, y) -> x.ToString() = y) integers strings |> Seq.filter fst |> Seq.head |> snd |> Seq.toList;;
val it : (int * string) list =
  [(0, "0"); (1, "1"); (2, "2"); (3, "3"); (4, "4"); (5, "5")]

Then you can simply use Seq.iter or Seq.map to perform the action.

Notice that this uses lazy evaluation all the way through.

Unless your actual actions involve manipulating shared state, you have an embarrassingly parallel solution at hand, so you could easily spread the work over multiple processors.