In F# when should I use List.choose and when to use List.filter

Question

I have just been doing a CodeWars exercise - "create a function that takes a list of non-negative integers and strings and returns a new list with the strings filtered out".

My solution used List.filter and it failed for one of the edge cases. So I looked at their solution and it used List.choose - which seemed to pretty much identical to my version except it converted the result to an option before deciding whether to include it in the new list.

I am confused - please can someone explain when it is best to use 'choose' and when it is best to use 'filter'?

Answer 1

I think you have already observed the essence of the answer: filter allows you to test for a condition, but with choose you can also project your value in the same expression, which would take a separate map if using filter.

Since the problem statement isn't clear (a list cannot contain integer and strings at the same time, except when they are boxed; i.e. the type of the list would be obj list), we can look at both scenarios. Note the additional map functions when using filter.

// List of strings that may contain integer representations
["1"; "abc"; "2"; "def"]
|> List.choose (System.Int32.TryParse >> function
| true, i -> Some i
| _ -> None )

["1"; "abc"; "2"; "def"]
|> List.map System.Int32.TryParse
|> List.filter fst
|> List.map snd

Both expressions return int list = [1; 2].

// List of object that are either of type int or of type string
[box 1; box "abc"; box 2; box "def"]
|> List.choose (function
| :? int as i -> Some i
| _ -> None )

[box 1; box "abc"; box 2; box "def"]
|> List.filter (fun i -> i :? int)
|> List.map unbox<int>

In the case of obj list as input the projection serves to provide the correct result type. That might be done in a different way, e.g. with an annotated let binding.

In the end, the decision between the two is down to your personal preferences.

Answer 2

List.choose is strictly more general than List.filter. You can implement List.filter using only List.choose, but not the other way around. You should use List.choose in place of List.filter only when you can't use the latter because it's simpler and describes your intention more accurately.

You can observe this difference pretty much from the type signatures alone.

List.choose : ('T -> 'U option) -> 'T list -> 'U list
List.filter : ('T -> bool) -> 'T list -> 'T list

List.filter can be implemented with List.choose like this:

let filter : ('T -> bool) -> 'T list -> 'T list =
  fun predicate ->
    List.choose (fun x -> if predicate x then Some x else None)

List.choose can however be implemented (inefficiently) using List.filter along with List.map and Option.get' (it is in fact calledfilterMap` in many languages and libraries):

let choose : ('T -> 'U option) -> 'T list -> 'U list =
  fun f list ->
    list
      |> List.map f
      |> List.filter (fun x -> x <> None)
      |> List.map Option.get

Note that Option.get can raise an exception, but won't here because we've filtered out the Nones that would cause that. But because it is unsafe, it's easy to make a mistake and because this implementation is not very efficient, it's nice to have List.choose come out-of-the-box.