Filtering lists in F# without throwing data away

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 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 on steroids.

In pseudo-code the process looked like so:

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

t4rzsan / fsharp-split

F# Split

Name: Filtering lists in F# without throwing data away
Rating: 1.3 (3065 reviews)
Author: t4rzsan

Split is an F# module for filtering lists but without losing the data that you filter away. If you use F#'s built in List.filter function, you have no way of keeping track of the items in the list that you filter away. With Split you can keep track of both the items that are included in the filter and the items that are excluded.

Take a look at Demo.fsx for an example on how to use Split. Also, check out this write-up on dev.to: https://dev.to/t4rzsan/filtering-lists-in-f-without-throwing-data-away-a7o.

View on GitHub

It is based on a simple type that holds a list for included items and a list of excluded items.

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.

[ 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:

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:

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].