# Functions as Data

Mark Galea Programming languages have evolved largely through a series of abstractions; these abstractions mostly deal with control (e.g. functions) or data. In the post, Houses, Arrays and Higher Order Functions, we have focused on the use of functions as control elements and have delved into the concept of higher order functions. Today we will revisit functions and focus on their use as data elements. Using functions to represent data might seem pretty counter intuitive at first but this blurred line between functions as control elements and functions as data elements is a powerful concept.

# Sets

In order to illustrate how functions can be used as data elements we will create a Set library with the following operations: `union`, `intersection` and `difference`. We will define a set using the characteristic function `T -> Boolean` i.e. a function which takes an element `T` as input and return a `true` or `false` depending on whether the element is contained within the set. Using classic OOP we can define a set as follows:

``````class Set<T>(vararg values: T) {
var elements: List<T> = values.toList()
fun contains(element:T): Boolean = this.elements.contains(element)
}
``````

In this case a set is defined as a class with a generic type `T`, we will use the underlying list data structure `elements` to implement the `contains` function. We can use the OOP representation as follows:

``````val s1 = Set(1)
val s2 = Set(2, 3, 4)
``````

Using functions as data elements we would implement a Set as follows:

``````fun <T>setOf(element: T): (T) -> Boolean  = { test -> element!!.equals(test) }
fun <T>contains(set: (T)->Boolean, element: T): Boolean  = set(element)
``````

The function `setOf` is a constructor function (as defined by SICP) which takes in an `element` and returns a higher order functions that implements the characteristic function `(T) -> Boolean`. `contains` just delegates the test to the `setOf` higher order function by calling `set(element)`. Some observant readers might have noticed that the class `Set` can ingest a number of values whilst the `setOf` function can only ingest one value. Using the `union` operator (defined further on) we can extends the `setOf` function to accept a variable number of elements `T`.

``````fun <T>setOf(vararg elements: T): (T) -> Boolean {
return elements.map { setOf(it) } .reduce { s, t -> union(s, t) }
}
``````

Using the `setOf` function we can define the set `s1` and `s2` as follows:

``````val s1 = setOf(1)
val s2 = setOf(2, 3, 4)
``````

Note that even though the representation is completely different the end user consuming either library will not be exposed to the underlying details of our implementations (OOP vs Functions). To an end user (except for minor syntactic differences) these two Sets are not different from each another.

# Union

Now that we have a means of representing a set, let us implement `union` in both representations. In the OOP approach we would implement union as follows:

``````class Set<T>(vararg values: T) {
fun union(other:Set<T>): Set<T> {
val unionSet = Set<T>()
val elements = ArrayList(this.elements)
elements.addAll(other.elements.filter { x -> !this.elements.contains(x) })
unionSet.elements = elements
return unionSet
}
...
}
``````

In this case we are using the backing data stucture `elements` to keep track of what is in the set. We can test this implementation as follows:

``````val s1 = Set(1)
val s2 = Set(2, 3, 4)
println(s1.union(s2).contains(1)) // -> true
println(s1.union(s2).contains(2)) // -> true
println(s1.union(s2).contains(3)) // -> true
println(s1.union(s2).contains(4)) // -> true
println(s1.union(s2).contains(5)) // -> false
println(s1.union(s2).contains(0)) // -> false
``````

Using functions we get a much more pure definition (mathematically speaking):

``````fun <T>union(s1: (T)->Boolean, s2: (T)->Boolean): (T)->Boolean =
{element -> s1(element) || s2(element) }
``````

An `element` is contained in the union of set `s1` and `s2` if the `element` is either in set `s1` or `s2`. This is clearly represented by the line `element -> s1(element) || s2(element)`. Don't be fooled by the fact that Kotlin does not support structural types, had the language supported structural types our definition would be a bit more concise:

``````fun <T>union(s1: Set<T>, s2: Set<T>):Set<T> =
{element -> s1(element) || s2(element) }
``````

Needless to say this is just semantic sugar; regular functions (with milk) will do just fine! One would use the union operator as follows:

``````val s1 = setOf(1)
val s2 = setOf(2, 3, 4)
println(contains(union(s1, s2), 1)) // -> true
println(contains(union(s1, s2), 2)) // -> true
println(contains(union(s1, s2), 3)) // -> true
println(contains(union(s1, s2), 4)) // -> true
println(contains(union(s1, s2), 5)) // -> false
println(contains(union(s1, s2), 0)) // -> false
``````

Note again that the usage is very similar and an end user would find it hard to believe that the Set is implemented using functions.

# Intersection

Having defined `union`, `intersection` will only be one synaptic leap away. Let's start off with the OOP version.

``````class Set<T>(vararg values: T) {
fun intersection(other:Set<T>): Set<T> {
val intersectionSet= Set<T>()
val elements = ArrayList<T>()
elements.addAll(this.elements.filter { x -> other.contains(x) })
intersectionSet.elements = elements
return intersectionSet
}
...
}
``````

One would use the definition above as follows:

``````val s3 = Set(1, 2)
val s4 = Set(2, 3, 4)
println(s3.intersection(s4).contains(1)) // -> false
println(s3.intersection(s4).contains(2)) // -> true
println(s3.intersection(s4).contains(3)) // -> false
println(s3.intersection(s4).contains(4)) // -> false
println(s3.intersection(s4).contains(5)) // -> false
println(s3.intersection(s4).contains(0)) // -> false
``````

Using functions, we would represent the intersection function as:

``````fun <T>intersection(s1: (T)->Boolean, s2: (T)->Boolean): (T)->Boolean =
{ element-> s1(element) && s2(element) }
``````

Note how close this function is to the original mathematical definition; an `element` is contained in the intersection of Set `s1` and `s2` if the `element` is contained in set `s1` and set `s2`, hence:

``````element -> s1(element) && s2(element)
``````

One would use the above definition as follows:

``````val s3 = setOf(1, 2)
val s4 = setOf(2, 3, 4)
println(contains(intersection(s3, s4), 1)) // -> false
println(contains(intersection(s3, s4), 2)) // -> true
println(contains(intersection(s3, s4), 3)) // -> false
println(contains(intersection(s3, s4), 4)) // -> false
println(contains(intersection(s3, s4), 5)) // -> false
println(contains(intersection(s3, s4), 0)) // -> false
``````

# Difference

For completeness let us now implement `difference` in both representations. In the OOP approach we would implement difference as follows:

``````class Set<T>(vararg values: T) {
fun difference(other:Set<T>): Set<T> {
val differenceSet= Set<T>()
val elements = ArrayList<T>()
elements.addAll(this.elements.filter { x -> !other.contains(x) })
differenceSet.elements = elements
return differenceSet
}
...
}
``````

Using functions we can implement this using:

``````fun <T>difference(s1: (T)->Boolean, s2: (T)->Boolean): (T)->Boolean =
{element-> s1(element) && !s2(element) }
``````

# Set of multiple elements

Before we conclude I would like to give an intuition for the function

``````fun <T>setOf(vararg elements: T): (T) -> Boolean {
return elements.map { setOf(it) } .reduce { s, t -> union(s, t) }
}
``````

Specifically how we used `map` and `reduce` to create a characteristic function which accepts multiple elements as follows:

``````val s3 = setOf(2, 3, 4, 7)
``````

What `elements.map { setOf(it) }` does is map all `elements` to a characteristic function, hence 2 becomes:

``````test -> 2.equals(test)
``````

3 becomes:

``````test -> 3.equals(test)
``````

and so on.

The `reduce` function will combine the characteristic functions as follows:

``````union (
union(
union(
{test -> 2.equals(test)},
{test -> 3.equals(test)}
),
{test -> 4.equals(test)}
),
{test -> 7.equals(test)}
)
``````

Each `union` function creates a new characteristic function combining the underlying two characteristic functions. For e.g.

``````union(
{test -> 2.equals(test)},
{test -> 3.equals(test)}
)
``````

would create the following characteristic function:

``````{test ->
{test1 -> 2.equals(test1)}(test) ||
{test2 -> 3.equals(test2)}(test)
}
``````

If we want to test whether 2 is in the set union, we would reduce the characteristic function as follows:

``````union({test -> 2.equals(test)}, {test -> 3.equals(test)})(2)
{test ->
{test1 -> 2.equals(test1)}(test) || // 2 here is the element in the set s1
{test2 -> 3.equals(test2)}(test)    // 3 here is the element in the set s2
}(2) // 2 is the value to test.
``````

Replace all occurrences of `test` with the value 2, we obtain:

``````{test1 -> 2.equals(test1)}(2) || {test2 -> 3.equals(test2)}(2)
``````

Replace all occurrences of `test1` and `test2` with the value 2, we obtain:

``````2.equals(2) || 3.equals(2)
true
``````

Hence the characteristic function for the set union between `s1` and `s2` when applied to 2 has reduced to true, which is correct.

# Conclusion

In this post we have looked at how we can use functions as data elements. Using functions as a data representation might feel unnatural at first but this blurred boundary between functions as elements of control and functions as elements of data is quite powerful. I really hope that you find this technique useful. Stay safe and keep hacking!