Data.Sequenceメモ

高速なキューData.Sequence.

空のキュー

Prelude Data.Sequence> empty
fromList []

キューの先頭に要素を追加

Prelude Data.Sequence> 1 <| 2 <| 3 <| empty
fromList [1,2,3]

キューの末尾に要素を追加

Prelude Data.Sequence> empty |> 1 |> 2 |> 3
fromList [1,2,3]

先頭から要素を一つ取り出す

Prelude Data.Sequence> viewl $ 1 <| 2 <| 3 <| empty
1 :< fromList [2,3]

viewl は Seq a の a を返すのではなく, ViewL a を返す。

Prelude Data.Sequence> :t viewl
viewl :: Seq a -> ViewL a

ViewL のパターンマッチ

foo :: ViewL Int -> Int
foo EmptyL    = -1
foo (x :< xs) = x

末尾から要素を一つ取り出す

Prelude Data.Sequence> viewr $ 1 <| 2 <| 3 <| empty
fromList [1,2] :> 3

viewr の場合は ViewR a が返る。

bar :: ViewR Int -> Int
bar EmptyR = -1
bar (xs :> x) = x

畳み込み

Seq a は Foldable クラスのインスタンス。

import Data.Sequence
import qualified Data.Foldable as F

foo :: Seq Int -> [String]
foo = F.foldr bar []
  where
    bar :: Int -> [String] -> [String]
    bar x ys = show x : ys

*Main> foo $ 1 <| 2 <| 3 <| empty
["1","2","3"]

今のところ、これらだけでなんとかなっている。