Описание тега difference-lists

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

На практике это сводится к явному поддержанию конечного указателя по списку в дополнение к указателю заголовка списка, так что добавление в конец списка становится операцией O(1). Независимо от того, создан ли экземпляр или нет, часть списка "над" конечным указателем является "разницей". Эти списки также называются "бессрочными".

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

Это также тесно связано с коркурсией. В то время как рекурсивная процедура будет строить список, сначала рекурсивно вычисляя остальную часть списка, а затем добавляя к нему элемент заголовка, процедура corecursive выдает элемент заголовка, прежде чем приступить к определению еще не вычисленной остальной части списка. Это также суть tailrecursion-модуль минусы оптимизации. В Haskell это моделируется защищенной рекурсией.