Во время выполнения одного из упражнений учебника по языку Haskell Р. Душкина, меня посетила мысль, что упражнение можно выполнить и на языке C# в духе Haskell.
Упражнение заключалось в реализации функции для получения бесконечного списка простых чисел с помощью алгоритма ”решето Эратосфена”. Надеюсь на то, что автор учебника не обидится на меня за то, что я привел тут решение задачи. Оно же почти в том же виде описано на wikipedia (ссылка выше на решето). Мое же решение отличается от опубликованного лишь тем, что четные числа я вычернкул загодя:
primes :: [Integer] primes = 2 : sieve [3, 5..] where sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]Нет, я не подглядывал и решение на Haskell в википедии обнаружил уже после того, как решил поделиться мыслями на эту тему. Мысли были примерно следующего характера:
Круто, ведь несколько раз мне приходилось реализовывать решето Эратосфена, и ни разу не пришло в голову реализовать его для бесконечного списка! Всегда требовалось задавать порог-размер решета. Беда даже не в том, что нужен порог, а в том, что нужно его тщательно подбирать для каждой задачи. Слишком малый порог грозит тем, что размера решета не хватит, а слишком большой опасен тем, что приложение будет слишком много времени тратить на ненужный счет.
Впрочем, в C# есть механизмы для работы с бесконечными последовательностями. Ну или почти бесконечными.
Подумал я так, и решил повторить решение на C#:
public static IEnumerable<int> GetPrimes() { yield return 2; var sieve = Generate(3, 2); while(true) { var p = sieve.First(); yield return p; sieve = sieve.Where(x => x % p > 0); } } static IEnumerable<int> Generate(int start, int step) { for (int i = start; ; i += step) yield return i; }По ходу написания ощутил, что в C# таки нет некоторых инструментов, но в остальном реализация на C# почти полностью соответсвует представленному выше решению на Haskell, потому я решение на Haskell не буду комментировать.
Код на C# вполне рабочий. Первым делом он возвращает 2, затем берет последовательность нечетных чисел больше 2 и на каждой итерации делает следующее: берет первое число p из последовательности и навешивает на последовательность фильтр, выкидывающий все что делится нацело на p.
Итак, отличия этого кода от решения на Haskell.- В C# нет типа BigInt (неограниченного целого). Потому решение на C# ограничено типом Int32.
- В C# нет встроенного генератора бесконечного списка. Enumerable.Range требует ограничителя диапазона и не воспринимает шаг. Впрочем, легко написать свой генератор, что я и сделал.
- В C# недоступен механизм рекурсии для работы с бесконечными списками. Ну т.е. рекурсия сама по себе есть, но воспользовавшись ей мы получим переполнение стека не дойдя до второго члена последовательности. Потому рекурсивное определение списка пришлось заменить на цикл с изменяемым состоянием. Да, решение на C# императивно. Ну да ладно, хоть состояние изменяемое, но оно невидимое клиенту изменяемое состояние.
Вот, пожалуй, и все отличия, подмеченные мной с первого раза. Все да не все. Что-то заставляет скомпилированный код на C# доставать 1000-е простое число в 5 раз дольше, чем выполняется код на интерпретаторе Haskell!!! Нет, это не шутка. А если попросить Haskell обойтись ограниченным целым (Int32), то он работает в 20 раз быстрее C#-а!!!
Все дело в том, что Haskell на каждой итерации выполняет фильтрацию над хвостом бесконечного списка, а C# выполняет фильтрацию над всей бесконечной последовательностью. Т.е. при поручении очередного элемента каждый раз требуется пройти часть бесконечной последовательности с самого начала, но уже с новыми условиями для фильтрации, которые добавляются на каждой итерации. Далее представлен слегка оптимизированный вариант на C#:public static IEnumerable<int> GetPrimes1() { yield return 2; var sieve = Generate(3, 2); Func<int, bool> predicate = x => true; while (true) { var p = sieve.First(); yield return p; predicate = predicate.And(x => x % p > 0); sieve = Generate(p, 2) .Where(predicate); } } static Func<T, bool> And<T>(this Func<T, bool> p1, Func<T, bool> p2) { return t => p1(t) && p2(t); }Теперь последовательности не просматриваются каждый раз сначала, вместо этого на каждой итерации генерируется новая последовательность нечетных чисел и на нее накладываются фильтры, которые пришлось накопить в локальной переменной. Здесь можно заметить что накапливать можно не условия фильтрации, а сами простые числа, которые можно подставить в неизменное условие фильтрации.
public static IEnumerable<int> GetPrimes2() { yield return 2; var primes = new List<int> {2}; var sieve = Generate(3, 2); Func<int, bool> predicate = x => primes.All(p => x % p > 0); while (true) { var p = sieve.First(); yield return p; primes.Add(p); sieve = Generate(p, 2) .Where(predicate); } }Впрочем, последние две версии решета на C# уже уверенно обгоняют интерпретатор Haskell-а. Вот только оригинальное решето Эратосфена они напоминают лишь отдаленно. И сильно смахивают на проверку делением на предварительно найденные простые числа. Следующее решение на языке F#:
let primes = let gen n = seq { n..2..System.Int32.MaxValue } let f (sieve, filter) = let p = sieve |> Seq.filter filter |> Seq.hd Some(p, (gen p, (fun x -> filter x && x % p > 0))) Seq.unfold f (gen 3, (fun _ -> true)) |> Seq.append [2]Оно больше всего соответствует варианту GetPrimes1() на C#, хотя написано без явно изменяемого состояния. В библиотеке F# имеется тип для представления больших целых, но я им здесь не воспользовался.