Porting functional programming code to Linq

Question

I am very new to C# programming, so for practice I thought I would try to port a simple haskell function over to Linq. From learn you a haskell, there is the following implementation of powerset:

powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs

Where filterM is defined like so

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     = return []
filterM p (x:xs) = do
  flg <- p x
  ys  <- filterM p xs
  return (if flg then x:ys else ys)

De-sugaring the do notation and specializing to m = list, this is

filterM :: (a -> [Bool]) -> [a] -> [[a]]
filterM _ []     = [[]]
filterM p (x:xs) = 
  p x >>= (\flg ->
    filterM p xs >>= (\ys ->
      if flg then [x:ys] else [ys]))

So, porting the above code to Linq, this is what I have:

//prepend taken from a stackexchange post
static class IEnumerableExtensions
{
    static IEnumerable<T> Prepend<T>(this IEnumerable<T> seq, T val)
    {
        yield return val;
        foreach (T t in seq)
        {
            yield return t;
        }
    }
}

class Program
{
    static List<List<T>> FilterND<T>(Func<T, List<bool>> preds, List<T> xs)
    {
        if (xs.Any())
        {
            //unrolling haskell do notation.
            //>>= becomes SelectMany
            return
            preds(xs.First()).SelectMany(b =>
            FilterND(preds, xs.Skip(1).ToList()).SelectMany(ys =>
                b ?
                new List<List<T>> { ys.Prepend(xs.First()).ToList() } :
                new List<List<T>> { ys }
            ))
            .ToList();
        }
        else
        {
            return new List<List<T>> { new List<T> { } }; //[[]]
        }
    }

    static List<List<T>> Powerset<T>(List<T> xs)
    {
        Func<T, List<bool>> preds = (x => new List<bool> { true, false });
        return FilterND<T>(preds, xs);
    }

    static void Main(string[] args)
    {
        var test = new List<int>() {1, 2, 3, 4, 5};
        var pow = Powerset(test);
        foreach (var xs in pow)
        {
            Console.Write("[");
            foreach (var x in xs)
            {
                Console.Write(x);
            }
            Console.Write("]\n");
        }
    }
}

My main questions are:

1. How do I go about making things lazy in the correct places?
2. In what ways should I be qualifying my input (ref, out, etc)?
3. Is it even possible to make this sort of code run fast?

Answer 1

I've hardly written a line of Haskell in my life... but hopefully that isn't too important since you're happy with plain old concrete types here.

---

As Adriano Repetti said in his comment, working with IEnumerable<T> rather than List<T> - or pretty much anything else - allows for lazy evaluation: your Prepend extension method is a beautiful example of this already. Most implementations of IEnumerable are nice enough to not break when you try to use them in funky ways through LINQ, so don't worry about that. If you are worried about that, then just .ToArray() the input (or use an IReadOnlyList<T>) so that you know you can trust the input.

Doing a quick job of replacing all those lists with IEnumerable<T>s and removing the calls to .ToList() gives this:

private static IEnumerable<IEnumerable<T>> FilterND<T>(Func<T, IEnumerable<bool>> preds, IEnumerable<T> xs)
{
    if (xs.Any())
    {
        return
            preds(xs.First()).SelectMany(b =>
                FilterND(preds, xs.Skip(1)).SelectMany(ys =>
                    b
                        ? new [] { ys.Prepend(head) }
                        : new [] { ys }
                    )
                );
    }
    else
    {
        return new [] { Enumerable.Empty<T>() };
    }
}

Note that I use arrays for 'throw away' fixed-length enumerables: they will be (marginally) faster, and provide a much tidier syntax. Enumerable.Empty<T>() is used rather than new T[0] or new T[] { } just because it is absolutely clear that I just want something empty.

Prepend is lazy, so is SelectMany: this whole package is now lazy. You can kind-of ratify this by putting a print line in Prepend, and writing the following code:

var ps = PowersetNess.PowerSet(new[] { 1, 2, 3 });

int si = 0;
foreach (var s in ps)
{
    Console.WriteLine(si++ + "\t" + string.Join(", ", s));
}

Without the print in Prepend the output will look like this:

0       1, 2, 3
1       1, 2
2       1, 3
3       1
4       2, 3
5       2
6       3
7

With the prepend, we can see that the calls are interspersed everywhere, which implies that something is being lazy.

Prepend!
Prepend!
Prepend!
0       1, 2, 3
Prepend!
Prepend!
1       1, 2
Prepend!
Prepend!
2       1, 3
Prepend!
3       1
Prepend!
Prepend!
4       2, 3
Prepend!
5       2
Prepend!
6       3
7

Naturally, if you insert those .ToList() calls back in, then you will find all the Prepend!s at the top, because you are forcing evaluation and caching.

Now indulge me while I pull out a couple of variables and rename b to includeHead...

private static IEnumerable<IEnumerable<T>> FilterND<T>(Func<T, IEnumerable<bool>> preds, IEnumerable<T> xs)
{
    if (xs.Any())
    {
        T head = xs.First();
        IEnumerable<T> tail = xs.Skip(1);

        return
            preds(head).SelectMany(includeHead =>
                FilterND(preds, tail).SelectMany(ys =>
                    includeHead
                        ? new [] { ys.Prepend(head) }
                        : new [] { ys }
                    )
                );
    }
    else
    {
        // just the empty set
        return new [] { Enumerable.Empty<T>() };
    }
}

Perhaps it is somehow clearer in Haskell to use >>= rather than a classic map, but the inner SelectMany can just be a Select, which will improve performance and reduce clutter rather.

private static IEnumerable<IEnumerable<T>> FilterND<T>(Func<T, IEnumerable<bool>> preds, IEnumerable<T> xs)
{
    if (xs.Any())
    {
        T head = xs.First();
        IEnumerable<T> tail = xs.Skip(1);

        return
            preds(head).SelectMany(includeHead =>
                FilterND(preds, tail).Select(ys =>
                    includeHead
                        ? Cons(head, ys)
                        : ys
                    )
                );
    }
    else
    {
        // just the empty set
        return new [] { Enumerable.Empty<T>() };
    }
}

You can also externalise the includeHead check, which will of course reduce overhead, and (I think) makes the whole method much more understandable.

private static IEnumerable<IEnumerable<T>> FilterND<T>(Func<T, IEnumerable<bool>> preds, IEnumerable<T> xs)
{
    if (xs.Any())
    {
        T head = xs.First();
        IEnumerable<T> tail = xs.Skip(1);

        return
            preds(head).SelectMany(includeHead =>
                includeHead
                    ? FilterND(preds, tail).Select(ys => Cons(head, ys))
                    : FilterND(preds, tail)
                );
    }
    else
    {
        // just the empty set
        return new [] { Enumerable.Empty<T>() };
    }
}

---

To answer your question 2: you don't need or want any out, ref, or in here. You could write a Decons method with out params to cleanly extract the head and tail of a list (shown below for fun), but it's probably not worth it, and doesn't have the same typing gaurentees as proper pattern matching.

public static bool Decons<T>(this IEnumerable<T> list, out T head, out IEnumerable<T> tail)
{
    if (list.Any())
    {
        head = list.First();
        tail = list.Skip(1);
        return true;
    }
    else
    {
        head = default(T);
        tail = null;
        return false;
    }
}

If I was using such a method in 'real' code it would be called TryDeconstruct or something. The pattern matching feature that are slowly being fed into C# may one day allow code looks like if (vs is (head, tail)), but I don't keep on top of that stuff.

Here is a (in my opinion very readable) version which uses a pair of nested foreach loops, and the Decons method.

private static IEnumerable<IEnumerable<T>> FilterND<T>(Func<T, IEnumerable<bool>> preds, IEnumerable<T> xs)
{
    if (xs.Decons(out var head, out var tail))
    {
        foreach (var includeHead in preds(head))
        {
            foreach (var partialSubSet in FilterND(preds, tail))
            {
                if (includeHead)
                    yield return partialSubSet.Prepend(head);
                else
                    yield return partialSubSet;
            }
        }
    }
    else
    {
        // just the empty set
        yield return Enumerable.Empty<T>();
    }
}

I hope that flood of C# was of some interest!

---

One final thing: you can tidy the definition of preds a bit (should it be predicates?) by using a local function.

Func<T, List<bool>> preds = (x => new List<bool> { true, false });
bool[] predicates(T x) => new bool[] { true, false };

This is just a matter of taste really (slightly surprised you didn't go with return FilterND<T>(x => new bool[] { true, false }, xs);). You could reduce the number of allocations by creating a single bool[] and always returning it, if performance is a serious concern, but this is the wrong place to be looking for a performance advantage.

P.S.: thanks for posting this, I had a lot of fun with it

Answer 2

Just a minor note to add to the existing answer: Prepend can be constructed quite cleanly from standard Linq methods as

static IEnumerable<T> Prepend<T>(this IEnumerable<T> seq, T val) =>
    Enumerable.Repeat(val, 1).Concat(seq);

or (arguably less readable here, but more consistent with the style in the other answer)

static IEnumerable<T> Prepend<T>(this IEnumerable<T> seq, T val) =>
    new [] { val }.Concat(seq);