関数型プログラミングでスタックとキューを使用する（JavaScript）

Question

関数型プログラミングに関する記事の一部を読んでいます。基準の1つは「同じ入力を与えられると、常に同じ出力を生成します」です。このルールに基づいて、どうすればプッシュ/プル/シフト/ unshiftをjavascriptの結果は常に変更する必要がありますか？また、配列にユーザー入力を格納する必要がある場合は、スタック/キューまたは回避策を適用する方法を提案できます。ありがとう。

stack: [] 

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

Answer 1

"同じ入力と同じ出力"

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

右。 Array.prototype.pushは破壊的な関数です。入力を変更します。我々が進む前に、の上で行きましょう

---

...基礎となるデータ構造を変化させません、明らかなものバインディング契約

を - あなたのスタック/キューは、純粋な関数を使用して実装される必要があるであろうStack契約

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

、これらの機能の任意の他の使用は

未定義の動作です

• あなたは、スタックを使用して、以下を参照実装はちょうど可能な実装であるstackPop
その上

を呼び出す前に空でないことを確認する必要がありemptyStack

に最初の値をstackPush必要があります。ポイントはStackの実装は、契約が満たされている限り重要ではありません。

---

"しかし、それはしかし不変です？"

はい、もちろんですが、それを信じるために見る必要がある場合は、自分自身を見てください。サンプルのスタックsを作成し、stackPopを2回呼び出します。 不変のデータ構造を実装したため、結果はの呼び出しごとに同じです。

// 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 {}

---

ので、これは本当に不自然な例で、スタック

[OK]を使用して文字列を逆に。読者を圧倒することなく、pushとpopを示したコードを思いついて少し問題が出ていました。

誰かが言う前に、これは文字列を逆にする本当にダムな方法ですが、その点以外にもあります。これは、文字列を逆にすることと、不変のデータ構造を持つ純粋な関数を使用することを実証することについては、あまりありません。

（ボーナス：ほとんどの人は、このようなとしてそれらについて考えていませんが、String sおよびNumber sがあまりにも不変です）

// 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'