「filterM で powerset」をC#らしく

(2025/6)
さすがにコード例が古いので、コレクション式を使って書き換え。

filterM は.NETにはないので、無理に実装を合わせる必要はない。
特に、Func<int, IEnumerable<bool>> pred = x => new[] { true, false }; の部分をラムダ式にする意味はない。
やってることは直積なんだから、[true, false] でいい。

List<int> xs = [1, 2, 3, 4];
List<List<int>> ys = PowerSet(xs);

foreach (var l in ys)
{
    Console.WriteLine($"[{string.Join(", ", l)}]");
}

List<List<T>> PowerSet<T>(List<T> xs)
{
    List<T> newAdd(List<T> l, T x) => [.. l, x];
    List<bool> flags = [true, false];
    List<List<T>> folder(List<List<T>> acc, T x)
    {
        var col =
            from f in flags
            from l in acc
            select f ? newAdd(l, x) : l;
        return [.. col];
    }
    List<List<T>> state = [[]];
    return xs.Aggregate(state, folder);
}

---

前回の 『「filterM で powerset」をC#に翻訳』はHaskellからの翻訳なのでC#的にいろいろ無理があった。特に再帰のところ。
熟練した C# 使いは再帰を書かない？ その通り。ではどうするか。Aggregateを使う。

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.Aggregate(
            Enumerable.Repeat(new LinkedList<T>(), 1),
            (acc, x) => acc.SelectMany(q => Accumulate(q, x, predicates))
        );
    }

    private static IEnumerable<LinkedList<T>> Accumulate<T>(
        LinkedList<T> q,
        T x,
        Func<T, IEnumerable<bool>> predicates)
    {
        foreach(var b in predicates(x))
        {
            if (b)
            {
                q.AddLast(x);
                yield return q;
                q.RemoveLast();
            }
            else
            {
                yield return q;
            }
        }
    }

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