Filtering lists in F# without throwing data away
Tags: fsharp, showdev
Published: 2022-01-21 16:46:43

A while back I got a new assignment that was a bit different from what we usually see.  We wanted to send letters to a select group of clients but we were not able to say who should get the letter.  We were only able to specify who should *not* get the letter.

So we started with a list of all clients and then we would remove people from that list in steps following a number of filter criteria.

Usually for these kind of assignments you would just apply a number of suiting [`List.filter`](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#filter) and that's it.  But not this time.

What made this task a little quirky was that we were required to log for each step who we removed from the list. So we needed something different from `List.filter`.  Instead we needed a way to filter the list while for each step logging the persons we filtered away.  It is like [`List.partition`](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections-listmodule.html#partition) on steroids.

In pseudo-code the process looked like so:
```fsharp
readListOfPersons()
|> filterOnCriterion1()
|> writeExludedPersonsToFile()
|> filterOnCriterion2()
|> writeExludedPersonsToFile()
|> filterOnCriterion3()
|> writeExludedPersonsToFile()
|> writeIncludedPersonsToFile()
```
I wrote a small module `Split` that does exactly that.  I recently cleaned it up and made it public on Github 
{% github t4rzsan/fsharp-split %}
It is based on a simple type that holds a list for included items and a list of excluded items.
```fsharp
type Split<'a> =
    { Included: 'a list
      Excluded: 'a list }
```
You use the `Split.create` function for splitting a list into included and excluded using a predicate function.
```fsharp
[ 1; 2; 3; 10; 354; 234; 23; 45 ]
|> Split.create (fun x -> x >= 10)

// The result is:
// { Included = [10; 354; 234; 23; 45]
//   Excluded = [1; 2; 3] }
```
We can now rewrite the pseudo-code example above with real code from the `Split` module:
```fsharp
let finalListOfPersons =
    readListOfPersons()
    |> Split.create filterCriterion1
    |> Split.outputExcluded printer
    |> Split.recreate filterCriterion2
    |> Split.outputExcluded printer
    |> Split.recreate filterCriterion3
    |> Split.outputExcluded printer
    |> Split.outputIncluded printer
```
The function `Split.recreate` does a new split on the `Included` list.

The module also has a number of other functions for manipulating both the `Included` and the `Excluded` lists, like `Split.sort`, `Split.map` and `Split.filter`.  You can also do things like appending `Excluded` to `Included` with `Split.merge` and swap the two with `Split.swap`.

Finally can get retrieve `Included` with `Split.decompose`.

Here is an example with numbers:
```fsharp
let printer title l =
    printfn "%s: %A" title l

let finalList =
    [ 1; 2; 3; 10; 354; 234; 23; 45 ]
    |> Split.create (fun x -> x >= 10)
    |> Split.outputExcluded (printer "Less than 10")
    |> Split.recreate (fun x -> (x % 2) = 0)
    |> Split.outputExcluded (printer "Odd")
    |> Split.swap
    |> Split.outputExcluded (printer "Even")
    |> Split.decompose
```
Output is:
```
Less than 10: [1; 2; 3]
Odd: [23; 45]
Even: [10; 354; 234]
```
And `finalList` ends up being `[23; 45]`.