Перенос функциональных программный код в LINQ


Я очень новой для программирования в C#, поэтому для практики я решил попробовать портировать простую функцию Хаскелл сравнению с LINQ. Из узнаете вы на Haskell, есть следующие реализации множество:

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

Где filterM определяется как так

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)

Де-шугаринг делать нотации и специализируется на m = listэто

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

Так, перенос приведенный выше код с LINQ, это то, что у меня есть:

//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");
        }
    }
}

Мои основные вопросы:

  1. Как я могу идти о делать вещи ленивых в правильных местах?
  2. Каким образом я должен быть квалификационными мой вклад (реф, и т. д.)?
  3. Можно ли сделать такой код быстро бегать?


Комментарии
2 ответа

Я не написал ни строчки, Haskell в моей жизни... но надеюсь, что не слишком важно, так как вы счастливы с простой старый конкретных типов.


Как Адриано Репетти сказал в своем комментарии, работа с IEnumerable<T> а не List<T> - или почти ничего - позволяет для ленивых оценка: ваш Prepend метод расширения-это прекрасный пример этому уже есть. Большинство реализаций IEnumerable хороший достаточно, чтобы не сломать, когда вы пытаетесь использовать их в фанки пути с помощью LINQ, так что не беспокойся об этом. Если вы беспокоитесь об этом, то просто .ToArray() входной (или используйте IReadOnlyList<T>), так что вы знаете, вы можете доверять входным данным.

Делая быструю работу по замене всех этих списков с IEnumerable<T>S и удаление звонков .ToList() дает это:

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>() };
}
}

Обратите внимание, что я использую массивы для 'выкинуть' фиксированной длины enumerables: они будут (незначительно) быстрее, и обеспечивают гораздо опрятнее синтаксис. Enumerable.Empty<T>() используется вместо new T[0] или new T[] { } просто потому что совершенно очевидно, что я просто хочу что-то пустое.

Prepend ленивый, так это SelectMany: весь этот пакет сейчас лень. Вы можете какие-то ратифицировать это, поставив печати в Prependи пишем следующий код:

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

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

Без печати в Prepend выходные данные будут выглядеть так:

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

С начало, мы видим, что призывы перемежаются повсюду, что подразумевает, что что-то лениться.

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

Естественно, если вы вставить эти .ToList() зовет обратно, то вы найдете все Prepend!в верхней, потому что вы заставляете оценки и кэширования.

Теперь балуют меня, пока я достаю пару переменных и переименовать b для 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>() };
}
}

Возможно, это как-то яснее в Haskell использовать >>= а не классическая карта, а внутренняя SelectMany может просто быть Select, что позволяет повысить производительность и уменьшить беспорядок, скорее.

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>() };
}
}

Вы также можете экстернализировать 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 =>
includeHead
? FilterND(preds, tail).Select(ys => Cons(head, ys))
: FilterND(preds, tail)
);
}
else
{
// just the empty set
return new [] { Enumerable.Empty<T>() };
}
}


Чтобы ответить на ваш вопрос 2: вам не нужно или вы хотите out, refили in здесь. Вы могли бы написать Decons метод с out params, чтобы аккуратно извлечь голову и хвост списка (как показано ниже Для начала), но это, наверное, не стоит, и не набрав как gaurentees правильному шаблону.

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;
}
}

Если я использую такой метод в "реальный" код, оно будет называться TryDeconstruct или что-то. Соответствующий шаблон функции, которые медленно подается в C# может за один день разрешить код выглядит как if (vs is (head, tail))но я не держу на вершине этой вещи.

Вот это (на мой взгляд очень четкий) версия, которая использует пары вложенных foreach петли, и Decons метод.

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>();
}
}

Я надеюсь, что поток в C# был какой-то интерес!


Одна последняя вещь: вы можете привести в порядок определение preds немного (она должна быть predicates?) с помощью локальной функции.

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

Это просто дело вкуса на самом деле (немного удивлена, что ты не пошел с return FilterND<T>(x => new bool[] { true, false }, xs);). Можно уменьшить количество выделений за счет создания единой bool[] и они всегда возвращаются, если производительность является серьезной проблемой, но это неправильное место, чтобы искать преимущество в производительности.

С. П.: Спасибо за размещение этого, я имел большое удовольствие с ним

8
ответ дан 4 февраля 2018 в 06:02 Источник Поделиться

Просто небольшое примечание, чтобы добавить к существующему ответ: Prepend могут быть построены довольно чисто от стандартной технологии LINQ методы, как

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

или (возможно, менее четкий, но более соответствует стилю в другой ответ)

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

4
ответ дан 9 февраля 2018 в 10:02 Источник Поделиться