Может ли весь код быть представлен в виде последовательности операций Map / Filter / Reduce?

16

Недавно я проводил рефакторинг больших кусков кода и заменял их запросами Linq.

Удаление языкового смещения. Linq - это набор операций Map / Filter и Reduce, которые работают с последовательностью данных.

Это заставило меня задуматься, насколько теоретически я смогу это сделать. Смогу ли я переписать всю кодовую базу в серию (или даже одну) операций Map / Filter и Reduce.

К сожалению, мне платят за то, что я делаю полезные вещи, поэтому я не смог больше экспериментировать, но я не могу представить себе какую-либо структуру кода, которая не может быть реструктурирована как таковая. Побочный код может быть обработан через монады. Даже вывод по существу отображает адреса памяти на экранные адреса.

Есть что-нибудь, что нельзя (теоретически) переписать как запрос Linq?

computer-science Mongus Pong
источник
Для деревьев смотрите здесь: stackoverflow.com/questions/250377/…
blueberryfields
Я всегда думал, что «Reduce» достаточно, чтобы гарантировать завершение Тьюринга (карта и фильтр могут быть реализованы как операции Reduce, не так ли?) - по крайней мере, функциональный язык, эквивалентный Reduce. Я не знаю достаточно о Linq, чтобы быть уверенным, насколько близко реализация следует за функциональной.
черничные
1
Я не знаю, но грубое практическое правило заключается в том, что все, о чем кто-либо даже подумает написать весь свой код, окажется завершенным по Тьюрингу. Но следствием этого является то, что завершенность по Тьюрингу не очень захватывающая.
PSR
1
Я согласен с PSR; Я думаю, что правильный ответ на этот вопрос должен касаться полноты по Тьюрингу. В качестве доказательства можно попытаться реализовать машину Тьюринга, используя только эти операции.
Роб
Бесполезная мысль: даже если мы допустим бессмысленные подобные действия my_list.map(_ignored => a copy of my_list), кажется, что использование такой программы в пространстве ограничено каким-то полиномом (в зависимости от длины программы). Тогда такой язык, конечно, не может вычислить проблемы, которых нет в PSPACE. Тем не менее, поскольку многие проблемы в PSPACE считаются внутренними, не говоря уже о больших классах, это не может быть очень серьезным ограничением.

Ответы:

1

Это называется функциональным программированием, и многие считают его основополагающим понятием. Вот хорошее введение в Joel On Software . Более технический ответ - нет, в настоящее время не существует известного способа задать вопросы на вашем компьютере (четко определенным образом), на которые невозможно ответить с помощью исчисления SKI.

JP Mcgrady
источник
1
В функциональном программировании есть гораздо больше, чем в функциях map, filterи reduce(это происходит трижды, если мы игнорируем полноту тьюринга и используем практические языки FP). Фактически, они просто бывают довольно общими и, следовательно, в целом полезными, но на самом деле являются очень простыми приложениями функционального программирования. Голое минимальное лямбда-исчисление может определять эти функции среди многих других, а не наоборот.
«Вот хорошее введение в Joel On Software», которое позволяет спутать Fortran с Basic, поэтому я бы не стал сильно доверять другим фактам.
Quant_Dev