Как реализовать этот алгоритм без мутации

Question

Я пытаюсь реализовать следующий алгоритм в функциональном языке, используя неизменяемость, функции более высокого порядка и/или рекурсию (без циклов или мутации).

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

Однако, если разница между двумя соседними элементами меньше некоторого числа (скажем 10), функция (notify) должна быть вызвана с этими аргументами

Любые советы о том, как я могу переписать его?

for (i = 1, i < queue.legth, i++) { 
    left = queue[i-1] 
    right = queue[i] 

    if (abs(left - right) < 10) { 
    notify(left, right) 
    } else if (left > right) { 
    queue[i-1] = right 
    queue[i] = left 
    } 
} 

UPDATE

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

Answer 1

JavaScript является ужасным языком для этого. Но вот идея.

Сначала реализуйте связанные списки. Ваш API может включать в себя следующие команды:

var empty_list = create_empty_list() 
var larger_list = list.prepend(thing) 
var is_empty = list.is_empty() 
var first_element = list.head() 
var tail = list.tail() 
var reversed_list = list.reversed() 

Внутренне связанный список только объект с головой, а другой объект, указывающий на хвост. Поэтому добавление к списку просто означает создание нового узла с новым значением, указывающим на старый. (т. е. не мутация!) Итак, у вас есть аксессоры. И тогда reversed - простая рекурсивная функция. (Вы должны вспомогательная функция list._reversed(tail), а затем list.reversed() просто list._reversed(create_empty_list()). Вспомогательная функция возвращает tail для пустого списка, а в противном случае возвращает this.tail._reversed(tail.prepend(this.head)).)

С связанным списком, вы можете перемещаться по очереди, строительство переставить список и звоните notify, где вы хотите. Когда вы закончите итерацию по очереди, у вас есть связанный список точно назад. Однако затем вы вызываете reversed, чтобы получить очередь в правильном порядке.