Applicative combinations of functions by Mark Seemann
Applicative lists and sequences enable you to create combinations of functions as well as values.
This article is an instalment in an article series about applicative functors. In the previous article, you saw how you can use applicative lists and sequences to generate combinations of values; specifically, the example demonstrated how to generate various password character combinations.
People often create passwords by using a common word as basis, and then turn characters into upper- or lower case. Someone feeling particularly tech-savvy may replace certain characters with digits, in an imitation of 1337. While this isn't secure, let's look at how to create various combinations of transformations using applicative lists and sequences.
List of functions #
In the previous article, I mentioned that there was a feature of applicative lists that I had, so far, deliberately ignored.
If you consider an example like this:
let passwordCombinations = [sprintf "%s%s%s%s%s%s"] <*> ["P"; "p"] <*> ["a"; "4"] <*> ["ssw"] <*> ["o"; "0"] <*> ["rd"] <*> [""; "!"]
you may have already noticed that while the left side of the <*> operator is a list of functions, it contains only a single function. What happens if you supply more than a single function?
You get a combination of each function and each list element.
Assume that you have three functions to convert characters:
module Char = // char -> char let toUpper c = System.Char.ToUpperInvariant c // char -> char let toLower c = System.Char.ToLowerInvariant c // Not even trying to be complete: // char -> char let to1337 = function | 'a' | 'A' -> '4' | 'b' -> '6' | 'E' -> '3' | 'H' -> '#' | 'i' -> '!' | 'l' -> '1' | 'o' | 'O' -> '0' | 't' -> '+' | c -> c
All three are functions that convert one char value to another, although many values could pass through without being modified. Since they all have the same type, you can create a list of them:
> List.map String.map [Char.toUpper; Char.toLower; Char.to1337] <*> ["Hello"; "World"];; val it : string list = ["HELLO"; "WORLD"; "hello"; "world"; "#e110"; "W0r1d"]
There's a bit to unpack there. Recall that all three functions in the Char module have the same type: char -> char. Making a list of them gives you a (char -> char) list, but you really need a (string -> string) list. Fortunately, the built-in String.map function takes a char -> char function and uses it to map each char values in a string. Thus, List.map String.map [Char.toUpper; Char.toLower; Char.to1337] gives you a (string -> string) list.
When you apply (<*>) that list of functions with a list of string values, you get all possible combinations of each function used with each string. Both "Hello" and "World" are converted to upper case, lower case, and 1337.
Combinations of functions #
Perhaps you're happy with the above combinations, but can we do better? As an example, you'll notice that to1337 only converts an upper-case 'E' to '3', but ignores a lower-case 'e'. What if you also want the combination where 'e' is first converted to upper case, and then to 1337? You'd like that, but you still want to retain the combinations where each of these transformations are applied without the other.
Fear not; functions are values, so you can combine them as well!
In the previous article, did you notice how you could model the presence or absence of a particular value? Specifically, the last character in the potential password could be '!', but '!' could also be omitted.
Consider, again, the expression for all password combinations:
let passwordCombinations = [sprintf "%s%s%s%s%s%s"] <*> ["P"; "p"] <*> ["a"; "4"] <*> ["ssw"] <*> ["o"; "0"] <*> ["rd"] <*> [""; "!"]
Notice that the last list contains two options: "!" and the empty string (""). You can read about this in another article series, but character strings are monoids, and one of the characteristics of monoids is that they have an identity element - a 'neutral' element, if you will. For strings, it's ""; you can append or prepend the empty string as much as you'd like, but it's not going to change the other string.
If you have a set of functions of the type 'a -> 'a, then the built-in function id is the identity element. You can compose any 'a -> 'a function with id, and it's not going to change the other function.
Since functions are values, then, you can create combinations of functions:
// (char -> char) list let maps = [fun f g h -> f >> g >> h] <*> [Char.toUpper; id] <*> [Char.toLower; id] <*> [Char.to1337; id]
Here, maps is a list of functions, but it's not only three functions as in the above example. It's eight functions:
> List.length maps;; val it : int = 8
The above applicative composition of maps combines three lists of functions. Each list presents two alternatives: a function (e.g. Char.toUpper), and id. In other words, a choice between doing something, and doing nothing. The lambda expression fun f g h -> f >> g >> h takes three (curried) arguments, and returns the composition of calling f, then passing the result of that to g, and again passing the result of that to h. f is either Char.toUpper or id, g is either Char.toLower or id, and h is either Char.to1337 or id. That's eight possible combinations.
Combine eight functions with two string values, and you get sixteen alternatives back:
> List.map String.map maps <*> ["Hello"; "World"];; val it : string list = ["he110"; "w0r1d"; "hello"; "world"; "#3LL0"; "W0RLD"; "HELLO"; "WORLD"; "he110"; "w0r1d"; "hello"; "world"; "#e110"; "W0r1d"; "Hello"; "World"]
Notice, for example, how one of the suggested alternatives is "#3LL0". Previously, there was no translation from 'e' to '3', but now there is, via Char.toUpper >> id >> Char.to1337.
Some of the combinations are redundant. For example, "hello" is generated twice, by Char.toUpper >> Char.toLower >> id and id >> Char.toLower >> id, respectively. You can reduce the output with List.distinct:
> List.map String.map maps <*> ["Hello"; "World"] |> List.distinct;; val it : string list = ["he110"; "w0r1d"; "hello"; "world"; "#3LL0"; "W0RLD"; "HELLO"; "WORLD"; "#e110"; "W0r1d"; "Hello"; "World"]
You can write equivalent code in Haskell, but it's so similar to the F# code that there's no reason to show it.
Translation to C# #
Using the Apply extension methods from the previous article, you can translate the above code to C#.
While you can use the .NET Base Class Library's Char.ToUpperInvariant and Char.ToLowerInvariant methods as is, you'll need to supply a to1337 function. You can write it as a named static method, but you can also write it as a delegate:
Func<char, char> to1337 = c => { switch (c) { case 'A': case 'a': return '4'; case 'b': return '6'; case 'E': return '3'; case 'H': return '#'; case 'i': return '!'; case 'l': return '1'; case 'o': case 'O': return '0'; case 't': return '+'; default: return c; } };
You're also going to need an id function:
Func<char, char> id = c => c;
In order to compose three functions to one, you can write something like this:
Func<Func<char, char>, Func<char, char>, Func<char, char>, Func<char, char>> compose3 = (f, g, h) => x => h(g(f(x)));
That's going to be a contender for some of the most obscure C# code I've written in a while. By the double use of =>, you can tell that it's a delegate that returns a delegate. That's not even the worst part: check out the type of the thing! In reality, nothing happens here that doesn't also happen in the above F# code, but it's an example of the superiority of Hindley–Milner type inference: in F#, you don't have to explicitly type out the type.
With a function to compose three other functions, you can now apply the three alternative functions:
IEnumerable<Func<char, char>> maps = new[] { compose3 } .Apply(new[] { Char.ToUpperInvariant, id }) .Apply(new[] { Char.ToLowerInvariant, id }) .Apply(new[] { to1337, id });
Now you have a sequence of functions that translate char values to char values. What you really need, though, is a sequence of functions that translate string values to string values.
The F# core library defines the built-in String.map function, but as far as I can tell, there's no equivalent method in the .NET Base Class Library. Therefore, you must implement it yourself:
Func<Func<char, char>, Func<string, string>> stringMap = f => (string s) => new string(s.Select(f).ToArray());
This is a function that takes a Func<char, char> as input and returns a Func<string, string>. Again, the type declaration isn't the prettiest.
You can now apply maps to some string values, using the Apply extension method:
IEnumerable<string> hellos = maps.Select(stringMap).Apply(new[] { "Hello", "World" });
This produces exactly the same output as the above F# example, even in the same order.
Applicative functors are elegant in F# and Haskell, but awkward in a language like C# - mostly because of its inferior type inference engine.
Summary #
Previous articles demonstrated how applicative lists can be used to compose several lists into a list that contains all possible combinations. In this article you saw how this also extends to combinations of functions.
The last three articles (including the present) focus on lists as applicative functors, but lists aren't the only type of applicative functor. In the next articles, you'll encounter some other applicative functors.
