Comments 20
Увы, о композиции в С-подобном синтаксисе говорить очень неудобно. А рассуждать о её изяществе даже опасно, засмеют и композицию заругают. Недаром у Lisp, Haskell, F# и J такой "странный" синтакис :)
Толкового ответа не нашел, только кучу пространных рассуждений и понимание, что я не одинок в своих заморочках. Наиболее ценное что нашел, это что если добавить рекурсию, то похоже что да.
Но наличие рекурсии это очень сильное требование. По сути, (и частично-, и без этого расширения) рекурсивные функции можно выполнять на машине тьюринга. Вопрос у меня скорее теперь такой — можно ли сделать и filter, и map, и reduce рекурсиями?
Навскидку, на пальцах, и не претендуя на 100%-ую точность.
// псевдоязык, "+" это сложение массивов
map = function(array, method, index = 0) => array.length == 0 ? [] : map(array[0, index - 1], method, 0) + [method(array[index])] + map(array[index + 1, array.length], method, 0);
filter = function(array, predicate, index = 0) => array.length == 0 ? [] : filter(array[0, index - 1], predicate, 0) + predicate(array[index]) ? array[index] : [] + filter(array[index + 1, array.length, predicate, 0);
reduce = function(array, method, initial, index = array.length) => array.length == 0 ? initial : method(reduce(array[0, index - 1], method, initial, index + 1), array[index]);
Это для иллюстрации хода мыслей, не более. Я не скажу, что очень глубоко в вопросе. Буду рад, если кто просветлит конкретно. Смущает наличие сравнения, так как возможности программировать условные переходы на основе сравнения — это всё, уже и есть машина Тьюринга. То есть добавление рекурсии по сути — это и есть создание машины Тюринга, а не map-filter-reduce.
Еще раз, буду очень рад если кто разъяснит вопрос, потому что иногда как-будто ежа под череп загнали с этим вопросом: по идее map — это биективное отображение, filter — отображение с потерей (проекция), reduce — взятие координаты. В таком ключе может показаться что есть всё, что нужно. Беда похоже только в том, что это нельзя это повторять, не имея операции ветвления/прерывания. И это похоже то что отличает машину Тьюринга (и класс реализуемых на ней алгоритмов) от класса map-filter-reduce.
while (true) { console.log("Hello!"); }
Уже не укладывается в filter-map-reduce, исходя из моих рассуждений.
Это конечно не есть пример полезной программы, но как идея.
В рамках чистого ФП функции map и filter реализуются через reduce, так что ваш вопрос сводится к такому: какой класс задач можно решить с помощью свёртки (катаморфизма)? Не претендуя на исчерпывающий и математически точный ответ можно сказать, что одна только свёртка позволяет обрабатывать конечные индуктивные данные. С её помощью можно построить конечный автомат, или автомат с магазинной памятью. Они не эквивалентны машине Тьюринга, но способны вычислять примитивно рекурсивные функции. На вскидку, с помощью reduce и без изменяемых состояний можно построить программу, эквивалентную программе, использующей только цикл for (точнее, foreach, C-шный for это переодетый while). Это хороший и полезный класс программ, гарантирующий тотальность. Для реализации цикла while потребуется ленивый генератор данных для свёртки: анаморфизм. Их композиция — хиломорфизм, уже Тьюринг полна. Повторюсь, все эти рассуждения имеют смысл при отсутствии изменяемого состояния, так как если сворачивающая функция может получить доступ к ссылке на сворачиваемые данные и изменять их на ходу, то это уже не катаморфизм, а бардак. В таком случае ответ на ваш вопрос будет таким: да, свёртка тьюринг-полна, но она тут ни при чём, это просто цикл. Кстати, в С# изменять итератор цикла foreach запрещено на уровне языка.
Насчет foreach в C# я в курсе, но while(true); там сделать можно, и в этом выражении нет изменяемых данных. Насчет «просто цикл» — просто или не просто, но уже тьюринговая полнота.
Используя свёртку можно построить детерминированный автомат с магазинной памятью, а значит, с его помощью можно распознать и транслировать любую контекстно-свободную грамматику. Вот, например, анализатор языка Дика (правильных скобочных выражений) с использованием левой свёртки:
brackets :: String -> Bool
brackets expr = foldl pda [0] expr == [0]
where
pda [] _ = []
pda (x:xs) c = delta c x ++ xs
delta '(' 0 = [1,0]
delta '(' 1 = [1,1]
delta ')' _ = []Это Haskell, на JS можно написать как-то так:
function brackets(s) {
return s.reduce(f,[0])
function f(stack,x) {
return stack == [] ? [] : stack.concat(delta(stack.pop(),x))
}
function delta(s,x) {
if (x == ')') return []
if (s == 0) return [0,1]
if (s == 1) return [1, 1]
}
}Уже другим голову грею — проблемой остановки, точнее её альтернативной формулировкой.
Ушел в прострацию :)
Например, если представить МТ вот как-то так
data = initial;
while (predicate(data)) data = method(data);
Если взять за A всю область определения method, то множество (method(A), predicate(method(A))) похоже не должно содержать замкнутых путей. Вряд ли я тут что-то решил (или даже переформулировал), но в качестве прокрастинации, сидя на работе, сгодится :)
Свёртка не тьюринг-полна, она как раз и гарантирует тотальность при обработке конечных данных тотальной функцией. В этом её преимущество и ограничение: за пределы КС-языков со свёрткой уже не выйти, нужна машина Тьюринга, цикл while или генерация данных для свёртки.
А вот что вы понимаете под множеством
(method(A), predicate(method(A))) и замкнутыми путями я не очень понял.
Если рассматриваемый язык строго типизирован и все функции чистые, то
data : A
method : A -> A
predicate : A -> Boolа значит, область значения функции method и область определения предиката совпадают.
Описанный вами паттерн это полноценный вычислитель, в котором анаморфизмом является итератор, а катаморфизмом — функция dropWhile, определяемая через свёртку:
head . dropWhile predicate . iterate method $ initialТотальность тут, увы, ничем не гарантирована, зато есть тьюринг-полнота. Если в качестве типа A взять некоторое окружение, то получим модель императивной программы в чистом функциональном исполнении.
Ну, и для полноты картины, стоит сказать, что эту модель можно свести к поиску наименьшей неподвижной точки слегка модифицированной функции method. А именно оператор фиксированной точки (Y-комбинатор) делает нетипизированное лямбда-исчисление тьюринг-полным. С этих рассуждений, когда-то и начали Алонзо Чёрч и его ученик Алан Тьюринг.
Собственно моя идея заключалась не в неподвижной точке как раз (и не в функторах), а в том, X = множество пар для всех a из A (a, predicate(method(a))) — согласен, с учетом области определения можно «сократить», но не теряя одного шага вычисления, — не должно иметь замкнутых путей, то есть, определяя путь как подмножество X, такое что для всех x из пути верно method(x.a) всегда имеет второй координатой true. Возможно, это может означать, что множество не компактно, не знаю, как гипотеза.
Это всё что я имел в виду.
Вот про функторы автор зря начал говорить. В контексте статьи речь идёт о контейнерах. Слово функтор, конечно, красивое, но оно накладывает бОльшие ограничения, чем указано в статье и даёт больше преимуществ, чем в ней указано. Понятно, что это перевод и что из песни слов не выкинешь, но для понимания того как использовать map в JS этот термин и его общность ни к чему. Вот если объяснить как построить reduce а вместе с ним и map для дерева, очереди, объектов (не всяких), или каких-либо других самописных стуктур, тогда становится понятнее зачем может понадобиться этот термин. Впрочем, хорошо что говоря о reduce автор не упоминает катаморфизмы.
Современные браузеры эффективнее выполняют более громоздкие традиционные конструкции, например, циклы.
По ссылке очень плохой пример, если циклы просто молотят массив, то map единственный, кто создает новый массив — логично, что map будет сильно медленнее.
И совершенно бесполезное создание бесполезной функции:
// Бесполезная анонимная функция создается на каждой итерации бенчмарка, отбирая баллы
arr.map(function (item) {
someFn(item);
});Можно упростить, до
arr.map(someFn);К тому же агрегатные функции не равнозначны простому циклу без проверок из-за того, что они пропускают дырки.
Довольно широко известен такой пример:
['10','10','10','10','10'].map(parseInt)
// [10, NaN, 2, 3, 4]
Верный вариант:
arr.map(function (item) {
return someFn(item);
});
Вариант для ES6:
arr.map(item => someFn(item));
Использование map и reduce в функциональном JavaScript