An applicative password list by Mark Seemann

How to use the applicative functor capabilities of lists to create a password list, with examples that object-oriented programmers can understand.

This article is an instalment in an article series about applicative functors. In the previous article, you saw how to use Haskell and F# lists as applicative functors to generate combinations of values. In this article, you'll see a similar example, but this time, there will also be a C# example.

Guess the password variation #

Years ago, I worked in an organisation that (among other things) produced much demo software. Often, the demo software would include a demonstration of the security features of a product, which meant that, as a user evaluating the software, you had to log in with a user name and password. In order to keep things simple, the password was usually Passw0rd!, or some variation thereof.

(Keep in mind that this was demoware. Password strength wasn't a concern. We explicitly wanted the password to be easy to guess, so that users evaluating the software had a chance to test how log in worked. This was long before social login and the like.)

We had more than one package of demoware, and over the years, variations of the standard password had snuck in. Sometimes it'd be all lower-case; sometimes it'd use 4 instead of a, and so on. As the years went on, the number of possible permutations grew.

Recently, I had a similar problem, but for security reasons, I don't want to divulge what it was. Let's just pretend that I had to guess one of those old demo passwords.

There weren't that many possible variations, but just enough that I couldn't keep them systematically in my head.

• The first letter could be upper or lower case.
• The second letter could be a or 4.
• The o could be replaced with a zero (0).
• The password could end with an exclamation mark (!), but it might also be omitted.

> let (<*>) fs l = fs |> List.collect (fun f -> l |> List.map f);;

val ( <*> ) : fs:('a -> 'b) list -> l:'a list -> 'b list

> [sprintf "%s%s%s%s%s%s"]
    <*> ["P"; "p"] <*> ["a"; "4"] <*> ["ssw"] <*> ["o"; "0"] <*> ["rd"] <*> [""; "!"];;
val it : string list =
  ["Password"; "Password!"; "Passw0rd"; "Passw0rd!"; "P4ssword"; "P4ssword!";
   "P4ssw0rd"; "P4ssw0rd!"; "password"; "password!"; "passw0rd"; "passw0rd!";
   "p4ssword"; "p4ssword!"; "p4ssw0rd"; "p4ssw0rd!"]

This produces a list of all the possible password combinations according to the above rules. Since there weren't that many, I could start trying each from the start, until I found the correct variation.

The first list contains a single function. Due to the way sprintf works, sprintf "%s%s%s%s%s%s" is a function that takes six (curried) string arguments, and returns a string. The number 6 is no coincidence, because you'll notice that the <*> operator is used six times.

There's no reason to repeat the exegesis from the previous article, but briefly:

1. sprintf "%s%s%s%s%s%s" has the type string -> string -> string -> string -> string -> string -> string.
2. [sprintf "%s%s%s%s%s%s"] has the type (string -> string -> string -> string -> string -> string -> string) list.
3. [sprintf "%s%s%s%s%s%s"] <*> ["P"; "p"] has the type (string -> string -> string -> string -> string -> string) list.
4. [sprintf "%s%s%s%s%s%s"] <*> ["P"; "p"] <*> ["a"; "4"] has the type (string -> string -> string -> string -> string) list.
5. ...and so on.

Clearly, then, that's no coincidence. I deliberately shaped the initial function to take six arguments, so that it would match the six segments I wanted to model.

Perhaps the most interesting quality of applicative functors is that you can compose an arbitrary number of objects, as long as you have a function to match the number of arguments.

Haskell #

This time I started with F#, but in Haskell, <*> is a built-in operator, so obviously this also works there:

passwordCombinations :: [String]
passwordCombinations =
  [printf "%s%s%s%s%s%s"]
  <*> ["P", "p"] <*> ["a", "4"] <*> ["ssw"] <*> ["o", "0"] <*> ["rd"] <*> ["", "!"]

The output is the same as the above F# code.

C# #

While you can translate the concept of lists as an applicative functor to C#, this is where you start testing the limits of the language; or perhaps I've simply forgotten too much C# to do it full justice.

Instead of making linked lists an applicative functor, let's consider a type closer to the spirit of the C# language: IEnumerable<T>. The following code attempts to turn IEnumerable<T> into an applicative functor.

Consider the above F# implementation of <*> (explained in the previous article). It uses List.collect to flatten what would otherwise had been a list of lists. List.collect has the type ('a -> 'b list) -> 'a list -> 'b list. The corresponding method for IEnumerable<T> already exists in the .NET Base Class Library; it's called SelectMany. (Incidentally, this is also the monadic bind function, but this is still not a monad tutorial.)

For an applicative functor, we need a method that takes a sequence of functions, and a sequence of values, and produces a sequence of return values. You can translate the above F# function to this C# extension method:

public static IEnumerable<TResult> Apply<T, TResult>(
    this IEnumerable<Func<T, TResult>> selectors,
    IEnumerable<T> source)
{
    return selectors.SelectMany(source.Select);
}

That's a single line of code! That's not so bad. What's the problem?

So far there's no problem. You can, for example, write code like this:

Func<string, int> sl = s => s.Length;
var lengths = new[] { sl }.Apply(new[] { "foo", "bar", "baz" });

This will return a sequence of the numbers 3, 3, 3. That seems, however, like quite a convoluted way of getting the lengths of some strings. A normal Select method would have sufficed.

Is it possible to repeat the above password enumeration in C#? In order to do that, you need a function that takes six string arguments and returns a string:

Func<string, string, string, string, string, string, string> concat =
    (x, y, z, æ, ø, å) => x + y + z + æ + ø + å;

With programmers' penchant to start with the variable name x, and continue with y and z, most people will have a problem with six variables - but not us Danes! Fortunately, we've officially added three extra letters to our alphabet for this very purpose! So with that small problem out of the way, you can now attempt to reproduce the above F# code:

var combinations = new[] { concat }
    .Apply(new[] { "P", "p" })
    .Apply(new[] { "a", "4" })
    .Apply(new[] { "ssw" })
    .Apply(new[] { "o", "0" })
    .Apply(new[] { "rd" })
    .Apply(new[] { "", "!" });

That looks promising, but there's one problem: it doesn't compile.

The problem is that concat is a function that takes six arguments, and the above Apply method expects selectors to be functions that take exactly one argument.

Alas, while it's not pretty, you can attempt to address the problem with an overload:

public static IEnumerable<Func<T2, T3, T4, T5, T6, TResult>> Apply<T1, T2, T3, T4, T5, T6, TResult>(
    this IEnumerable<Func<T1, T2, T3, T4, T5, T6, TResult>> selectors,
    IEnumerable<T1> source)
{
    return selectors.SelectMany(f =>
        source.Select(x =>
        {
            Func<T2, T3, T4, T5, T6, TResult> g = (y, z, æ, ø, å) => f(x, y, z, æ, ø, å);
            return g;
        }));
}

This overload of Apply takes selectors of arity six, and return a sequence of functions with arity five.

Does it work now, then?

Unfortunately, it still doesn't compile, because new[] { concat }.Apply(new[] { "P", "p" }) has the type IEnumerable<Func<string, string, string, string, string, string>>, and no overload of Apply exists that supports selectors with arity five.

You'll have to add such an overload as well:

public static IEnumerable<Func<T2, T3, T4, T5, TResult>> Apply<T1, T2, T3, T4, T5, TResult>(
    this IEnumerable<Func<T1, T2, T3, T4, T5, TResult>> selectors,
    IEnumerable<T1> source)
{
    return selectors.SelectMany(f =>
        source.Select(x =>
        {
            Func<T2, T3, T4, T5, TResult> g = (y, z, æ, ø) => f(x, y, z, æ, ø);
            return g;
        }));
}

You can probably see where this is going. This overload returns a sequence of functions with arity four, so you'll have to add an Apply overload for such functions as well, plus for functions with arity three and two. Once you've done that, the above fluent chain of Apply method calls work, and you get a sequence containing all the password variations.

> new[] { concat }
.     .Apply(new[] { "P", "p" })
.     .Apply(new[] { "a", "4" })
.     .Apply(new[] { "ssw" })
.     .Apply(new[] { "o", "0" })
.     .Apply(new[] { "rd" })
.     .Apply(new[] { "", "!" })
string[16] { "Password", "Password!", "Passw0rd", "Passw0rd!", "P4ssword", "P4ssword!",
             "P4ssw0rd", "P4ssw0rd!", "password", "password!", "passw0rd", "passw0rd!",
             "p4ssword", "p4ssword!", "p4ssw0rd", "p4ssw0rd!" }

In F# and Haskell, the compiler automatically figures out the return type of each application, due to a combination of currying and Hindley–Milner type inference. Perhaps I've allowed my C# skills to atrophy, but I don't think there's an easy resolution to this problem in C#.

Obviously, you can always write a reusable library with Apply overloads that support up to some absurd arity. Once those methods are written, they're unlikely to change. Still, it seems to me that we're pushing the envelope.

Summary #

In this article, you saw how to turn C# sequences into an applicative functor. While possible, there are some bumps in the road.

There's still an aspect of using lists and sequences as applicative functors that I've been deliberately ignoring so far. The next article covers that. After that, we'll take a break from lists and look at some other applicative functors.

Next: Applicative combinations of functions.

Comments

var combinations = new[] { LanguageExt.Prelude.curry(concat) }
    .Apply(new[] { "P", "p" })
    .Apply(new[] { "a", "4" })
    .Apply(new[] { "ssw" })
    .Apply(new[] { "o", "0" })
    .Apply(new[] { "rd" })
    .Apply(new[] { "", "!" });

• ← Previous
• Archive
• Next →