コンスセルのリストで再帰版直積

再帰にはコンスセルが便利。

Program.cs

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

class Program
{
    static void Main(string[] args)
    {
        var upperOrLower = "ABCD"
            .Select(x => new[] { char.ToUpper(x), char.ToLower(x) }.AsEnumerable())
            .DirectProduct(x => new string(x.ToArray()));

        foreach (var s in upperOrLower)
        {
            Console.WriteLine(s);
        }
    }
}

public static class EnumerableEx
{
    public static IEnumerable<TResult> DirectProduct<T, TResult>(
        this IEnumerable<IEnumerable<T>> source,
        Func<IEnumerable<T>, TResult> selector)
    {
        return DirectProductRec(new ConsCell<IEnumerable<T>>(source), new ConsCell<T>(), selector);
    }

    static IEnumerable<TResult> DirectProductRec<T, TResult>(
        ConsCell<IEnumerable<T>> src, ConsCell<T> list,
        Func<IEnumerable<T>, TResult> selector)
    {
        if (src.IsEmpty)
        {
            return Enumerable.Empty<TResult>();
        }

        if (src.Tail.IsEmpty)
        {
            return src.Head.Select(x => selector(list.Push(x).Reverse()));
        }

        return src.Head.SelectMany<T, TResult>(x => DirectProductRec(src.Tail, list.Push(x), selector));
    }
}

public class ConsCell<T> : ICollection<T>
{
    private readonly T head;
    private readonly ConsCell<T> tail;
    private readonly bool isTerminal;

    public ConsCell()
    {
        this.isTerminal = true;
    }

    public ConsCell(T value, ConsCell<T> tail)
    {
        this.head = value;
        this.tail = tail;
    }

    public ConsCell(IEnumerable<T> source)
        : this(EnsureNotNull(source).GetEnumerator())
    {
    }

    private static IEnumerable<T> EnsureNotNull(IEnumerable<T> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");
        return source;
    }

    private ConsCell(IEnumerator<T> itor)
    {
        if (itor.MoveNext())
        {
            this.head = itor.Current;
            this.tail = new ConsCell<T>(itor);
        }
        else
        {
            this.isTerminal = true;
        }
    }


    public bool IsEmpty
    {
        get { return this.isTerminal; }
    }

    public T Head
    {
        get
        {
            this.ErrorIfEmpty();
            return this.head;
        }
    }

    public ConsCell<T> Tail
    {
        get
        {
            this.ErrorIfEmpty();
            return this.tail;
        }
    }

    private void ErrorIfEmpty()
    {
        if (this.isTerminal)
            throw new InvalidOperationException("this is empty.");
    }

    public ConsCell<T> Push(T head)
    {
        return new ConsCell<T>(head, this);
    }

    public ConsCell<T> Concat(ConsCell<T> second)
    {
        if (this.isTerminal)
            return second;
        return this.tail.Concat(second).Push(this.head);
    }

    public bool Contains(T item)
    {
        for (ConsCell<T> p = this; !p.isTerminal; p = p.tail)
        {
            T v = p.head;
            if (v == null && item == null)
            {
                return true;
            }
            else if (v.Equals(item))
            {
                return true;
            }
        }

        return false;
    }

    public int Count
    {
        get
        {
            int c = 0;
            for (ConsCell<T> p = this; !p.isTerminal; p = p.tail)
            {
                c++;
            }

            return c;
        }
    }

    public ConsCell<T> Reverse()
    {
        ConsCell<T> rev = new ConsCell<T>();
        for (ConsCell<T> p = this; !p.isTerminal; p = p.tail)
        {
            rev = rev.Push(p.head);
        }

        return rev;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (ConsCell<T> p = this; !p.isTerminal; p = p.tail)
            yield return p.head;
    }

    #region IEnumerator

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    #endregion

    #region ICollection<T>

    bool ICollection<T>.IsReadOnly
    {
        get { return true; }
    }

    void ICollection<T>.CopyTo(T[] array, int arrayIndex)
    {
        for (ConsCell<T> p = this; !p.isTerminal; p = p.tail)
        {
            if (array.Length <= arrayIndex)
                throw new ArgumentOutOfRangeException("arrayIndex");
            array[arrayIndex++] = p.head;
        }
    }

    void ICollection<T>.Add(T item)
    {
        throw new NotSupportedException();
    }

    void ICollection<T>.Clear()
    {
        throw new NotSupportedException();
    }

    bool ICollection<T>.Remove(T item)
    {
        throw new NotSupportedException();
    }

    #endregion
}