Статьи

Тьюринг ‘Карта’, ‘Уменьшить’ и ‘Фильтр’ завершены?

Июнь 8, 2018

Да.

Вы можете реализовать любой алгоритм с картой, уменьшением и фильтрацией в контексте современных языков, которые реализуют эти конструкции. Предикатные функции, на которые они полагаются, являются полными по Тьюрингу, что делает их полными по Тьюрингу.

Но это умный ответ **, не так ли? Реализация всего вашего алгоритма в функции предиката и оборачивание его в вызов карты кажется обманом.

Можете ли вы реализовать алгоритм только с картой, уменьшить и отфильтровать?

Нет.

Эти три функции сами по себе не могут выполнять приседания. Написание чего-то подобного map(reduce(reduce(map(reduce(filter(4))))))ничего не сделает.

Сначала мы должны решить, что мы пытаемся спросить.

Я терял сон из-за всего этого с тех пор, как на прошлой неделе меня обстреливал технический редактор. «Умный человек однажды сказал мне, что вы можете написать любую программу в виде последовательности карт и уменьшить количество вызовов. Я хотел бы добавить фильтр для более полного набора инструментов,» написал я в визуализации данных с d3.js .

Единственный комментарий редактора был: «Это неправильно. Например, вы не можете реализовать такую ​​сортировку ».

И да, он прав. Но он также не. Что Smart Guy ™ пытался рассказать мне все те годы назад, когда он познакомил меня с функциональным программированием?

Вернуться к основам.

Чтобы иметь полный язык Тьюринга, вам нужно:

  1. Напишите ячейку
  2. Читать ячейку
  3. Двигай влево
  4. Переместить вправо
  5. Ветвление (основано на значении ячейки)

Мы предполагаем, что наша память практически бесконечна. Это означает, что это не бесконечно само по себе, но мы можем добавить больше, когда закончится.

В своей работе по созданию LISP Маккарти писал, что рекурсивной альтернативе итеративной машине Тьюринга нужны следующие конструкции:

  1. atom — является ли этот символ атомом (одним из основных символов)
  2. eq — оба эти символы атомы
  3. car — возвращает первую часть двухэлементного списка
  4. cdr — возвращает вторую часть двухэлементного списка
  5. cons — строит список из двух элементов
  6. рекурсивные определения с использованием этих пяти конструкций

Куда это приведет нас к нашему первоначальному вопросу? Можем ли мы построить что-нибудь из последовательности карт, уменьшить и отфильтровать?

Это зависит.

В контексте строгого функционального языка , с добавлением рекурсии, да, мы, вероятно, можем.

В конце концов, внедрение наивной быстрой сортировки в Haskell занимает не более , чем рекурсии, car, cdr, consи фильтр.

quicksort [] = []
quicksort (x:xs) =
          let smaller = quicksort (filter (<=x) xs)
              bigger = quicksort (filter (>x) xs)
          in smaller ++ [x] ++ bigger

В основном, если quicksortполучен пустой список, вернуть пустой список. В противном случае создайте новый список и поместите элементы меньше, чем xслева, больше справа. ++является по существу минусом, и этот (x:xs)бит разделяет список, поэтому первый элемент становится, xа остальные элементы становятся xs.

Это одна из самых кратких реализаций сортировки, которую я когда-либо видел. И мы не на самом деле выйти из нашей карты, уменьшить и рамку фильтра, сделали мы? Возможность добавления и разделения списков обычно предполагается.

Но можем ли мы пойти еще дальше? Можем ли мы реализовать filterс помощью карты и уменьшить? Давай попробуем.

function filter (predicate, list) {
    return list.map(function (a) {
        return predicate(a) ? [a] : null;
    }).reduce(function (prev, current) {
        return current ? prev.concat(current) : prev;
    }, []);
}

Да мы можем. Даже в Javascript, о котором был первоначальный вопрос. Это довольно просто: пометьте нежелательные записи с помощью map, а затем используйте reduceдля создания нового списка без нежелательных записей.

Мы могли бы пойти дальше и использовать только reduce?

function filter2 (predicate, list) {
    return list.reduce(function (prev, current) {
        return predicate(current) ? prev.concat(current) : prev;
    }, []);
}

Получается, что reduceи filterэто одна и та же функция, если предположить, что разветвление и сравнение являются заданными. .concatкстати, есть минусы Javascript.

Мы можем реализовать этот пример на Haskell в Javascript . Доказательство того, что даже с Javascript, рекурсии, сопоставления и сокращения достаточно, чтобы сделать что-нибудь.

function quicksort (list) {
    if (list.length == 0) {
        return [];
    }
 
    var x = list[0],
        xs = list.slice(1);
 
    return quicksort(filter2(function (a) { return a <= x; }, xs))
        .concat(x)
        .concat(
            quicksort(filter2(function (a) { return a > x; }, xs)));
}

Точно такой же код, как и раньше, просто более словарный, потому что Javascript более пушистый, чем Haskell.

Но ближе ли мы к открытию нашего вопроса?

Не на самом деле нет. Мы только что показали, что с учетом условий, способа нарезки и добавления списков, рекурсии, сопоставления и сокращения мы можем делать все что угодно. Даже в Javascript.

Вы должны прочитать мою книгу, почему программисты работают по ночам .

29
Share: