キューの効率的な実装 または私は如何にしてHaskellを止めてF#を愛するようになったか - Qiita

この記事は F# Advent Calendar 2017 と Haskell (その2) Advent Calendar 2017 のために書かれています。 はじめに 最近『純粋関数型データ構造』の勉強会に参加していて、いろいろと学ぶことが多かったので、その一端でも残しておこうと思いました。 一言で言うと、『純粋関数型データ構造で効率を追求するなら遅延評価と正格評価の両方が必要』だという話です。 あらためて kinabaさんの有名なスライド を読んだら、ぜんぶ書いてあったので、そちらを理解している方は読む必要ありません。 私はネタとしては知っていましたが、今回本を読んで初めて内容を理解しました。 キューと償却計算量 キューってありますよね。 末尾に要素を追加したり（snoc）、先頭の要素を取り出したり（head、tail）できるデータ構造です。 純粋関数型で（破壊的更新なく）実装する場合