「filterM で powerset」をC#に翻訳

powerset（べき集合）というのは、すべての部分集合を集めた集合。

元ネタだったqiitaの記事「filterM で powerset」が消えてるから、記憶から再構成。

powerset :: [a] -> [[a]]
powerset =  filterM (const [True, False])

（ちなみに、Haskellには subsequences という関数があって、上記powersetと等価である。）

C#にはモナドクラスなんてないからfilterMもないわけで、リスト（IEnumetrable）に特化した形で書くしかないからおいしくはない。

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var array = new[] { 1, 2, 3, 4, 5 };
        Func<int, IEnumerable<bool>> pred = x => new[] { true, false };

        foreach (var l in array.WhereMany(pred))
        {
            Console.WriteLine(l.ToStringEx());
        }
    }
}

public static class EnumerableEx
{
    public static IEnumerable<IEnumerable<T>> WhereMany<T>(
        this IEnumerable<T> source,
        Func<T, IEnumerable<bool>> predicates)
    {
        return source.GetEnumerator().WhereMany(predicates);
    }

    public static IEnumerable<IEnumerable<T>> WhereMany<T>(
        this IEnumerator<T> source,
        Func<T, IEnumerable<bool>> predicates)
    {
        if (!source.MoveNext())
            return Enumerable.Repeat(Enumerable.Empty<T>(), 1);

        var x = source.Current;
        var yss = source.WhereMany(predicates);
        return from b in predicates(x)
               from ys in yss
               select (b ? Enumerable.Repeat(x, 1).Concat(ys) : ys);
    }

    public static string ToStringEx<T>(this IEnumerable<T> source)
    {
        var strings = source.Select(x => x.ToString());
        return "[" + string.Join(", ", strings) + "]";
    }
}