Использование Stack & Queue в функциональном программировании (javascript)

Question

Я прочитал несколько статей о функциональном программировании, один из критериев: «Учитывая тот же ввод, они всегда производят один и тот же вывод». Основываясь на этом правиле, как я могу вызвать push/pull/shift/unshift в javascript, так как результат всегда должен меняться? Кроме того, вы можете предложить, как применять стек/очередь или обходной путь, если мне нужно сохранить вход пользователя в массив. Благодарю.

stack: [] 

recordData(value) { 
    stack.push(value) 
    ...... 
} 

Answer 1

"тот же вход же выход"

let stack = [] 
stack.push(1) // [1] 
stack.push(1) // [1,1] 

справа. Array.prototype.push - это деструктивная функция - она ​​мутирует ее вход. Ваша стек/очередь должна быть реализована с использованием чистых функций - явно те, которые не мутируют основную структуру данных ...

---

Binding соглашение

Прежде чем мы продолжим, давайте над Stack контракт

// stack contract 
stackIsEmpty(emptyStack)    => true 
stackIsEmpty(stackPush(x, emptyStack)) => false 
stackPop(stackPush(x, emptyStack))  => [x, emptyStack] 

Любое другое использование этих функций неопределенными поведение

• Вы должны stackPush первое значение на emptyStack
• Вы должны убедиться, что стек не пуст перед вызовом stackPop на нем

Реализация вы видите ниже только возможной реализации. Дело в том, что реализация Stack не имеет значения до тех пор, пока контракт будет выполнен.

---

"Но это неизменное, хотя?"

Да, конечно, но если вы должны убедиться, что это в это поверить, посмотрите сами. Мы создаем стек образца, s, а затем мы вызываем его stackPop. Результат одинаковый для каждого вызова, потому что мы внедрили неизменную структуру данных.

// stack data abstraction 
 
const emptyStack = {} 
 
const stackPush = (x, xs) => f => f(x,xs) 
 
const stackPop = s => s((x,xs) => [x,xs]) 
 
const stackIsEmpty = s => s === emptyStack 
 

 
// stackPush does not mutate emptyStack 
 
let s = stackPush(1, emptyStack) 
 
console.log(stackIsEmpty(emptyStack)) // true 
 

 
// stackPop does not mutate s 
 
let [test1, stack1] = stackPop(s) 
 
console.log(test1, stack1) // 1 {} 
 

 
// stackPop returning the same value for the same input, s 
 
let [test2, stack2] = stackPop(s) 
 
console.log(test2, stack2) // 1 {}

---

Reverse строку с использованием стека

Ok, так что это действительно надуманный пример. У меня возникли небольшие проблемы с куском кода, который продемонстрировал push и pop, не подавляя читателя.

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

(бонус: большинство людей не думают о них как таковой, но String s и s Number неизменны тоже)

// stack data abstraction 
 
const emptyStack = {} 
 
const stackPush = (x, xs) => f => f(x,xs) 
 
const stackPop = s => s((x,xs) => [x,xs]) 
 
const stackIsEmpty = s => s === emptyStack 
 

 
// some function using stack 
 
const strReverse = str => { 
 
    let load = (stack, str) => { 
 
    if (str.length === 0) 
 
     return stack 
 
    else 
 
     return load(stackPush(str[0], stack), str.substr(1)) 
 
    } 
 
    let unload = (str, stack) => { 
 
    if (stackIsEmpty(stack)) 
 
     return str 
 
    else { 
 
     let [char, nextStack] = stackPop(stack) 
 
     return unload(str + char, nextStack) 
 
    } 
 
    } 
 
    return unload('', load(emptyStack, str)); 
 
} 
 

 
console.log(strReverse('foobar')) // 'raboof'