### Contents

A purely functional definition of Sets
...without any data structures

What would a defintion of classic sets in F# look like. These would just be composed of functions, without any underlying data types.

The simplesy defintion of a `Set` is a boundary - everything inside it belongs to the set, everything outside it does not. We can define that membership using a simple function type.

``````type 'a Set = 'a -> bool
``````

`true` for a value that belongs to the set and `false` otherwise.

For example. the set of natural numbers is:

``````let nat x = x > 0
``````

## contains

Contains just calls our function, but constrains its value to `bool`- which will help out type inference down the line.

``````let contains value set : bool = set value
``````

## empty

A set that contains nothing could never return `true`.

``````let empty = fun _ -> false
``````

## universal

A universal set is a set which contains all objects, including itself. For now, our definition does not care about Russel's paradox.

``````let universal = fun _ -> true
``````

## zip

A zip combines two sets with a combinator function.

``````let zip set1 set2 fn = fun v -> fn (set1 |> contains v) (set2 |> contains v)
``````

## union

A set union combines the elements of both sets. We can express this with `zip`:

``````let union set1 set2 = zip set1 set2 (||)
``````

## intersect

An intersection of two sets only has members which belong in both the sets, or, ANDing.

``````let intersect set1 set2 = zip set1 set2 (&&)
``````

## filter

``````let filter fn set1 = zip set1 fn (&&)
``````

and moving on to constructing sets.

## singleton

A singleton set has only one element.

``````let singleton value = fun v -> value = v
``````

## ofList

``````let ofList list = fun v -> list |> List.contains v
``````

# Tests

``````assert (1 |> FSet.singleton |> FSet.contains 1)
assert (1 |> FSet.singleton |> FSet.contains 0 |> not)
assert ([1; 2; 3] |> FSet.ofList |> FSet.contains 1)
assert ([1; 2; 3] |> FSet.ofList |> FSet.union (FSet.singleton 4) |> FSet.contains 4)
assert ([1; 2; 3] |> FSet.ofList |> FSet.intersect (FSet.singleton 1) |> FSet.contains 1)
assert ([1; 2; 3] |> FSet.ofList |> FSet.intersect (FSet.singleton 4) |> FSet.contains 4 |> not)
``````