Список различий

В информатике термин «список различий» относится к структуре данных, представляющей список с эффективной O (1) операцией конкатенации и преобразованием в связанный список за время, пропорциональное его длине. Списки различий можно реализовать с помощью первоклассных функций или с помощью унификации. Является ли список различий более эффективным, чем другие представления списка, зависит от шаблонов использования. Если алгоритм создает список путем объединения меньших списков, которые сами создаются путем объединения еще меньших списков, то использование списков различий может повысить производительность за счет эффективного «сглаживания» вычислений при построении списка.

Реализация с использованием функций

Список различий f с одним аргументом, — это функция добавление L если задан связанный список X в качестве аргумента , возвращает связанный список, содержащий L, добавленный к X. , которая , Объединение списков различий реализовано в виде композиции функций . Содержимое можно получить с помощью f [] .

Эта реализация обычно используется в функциональных языках программирования, таких как Haskell , хотя ее можно использовать и в императивных языках.

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

Примеры использования приведены в типе ShowS в Prelude Haskell и в библиотеке списков различий Дональда Брюса Стюарта для Haskell .

Реализация с использованием унификации

Другая реализация логического программирования языка Пролог использует переменные объединения. Список различий — это пара OpenList-Hole , где первый элемент OpenList — это список, содержащий несвязанную переменную объединения (дыру), а второй элемент Hole — ссылку на дыру.