Data.Sequence の両端における操作

Haskell の両端キュー

Haskell には Data.Sequence と呼ばれる両端キューライブラリが存在します。
ただのリストと比較すると

• 左端と右端どちらにも定数時間で要素を挿入できる¹
• Sequence 同士を対数時間で連結可能(>< とかいう可愛い演算子です)^{2 3}
• 対数時間で要素にアクセス可能。しかもMaybeモナドに包んで返す関数もある⁴
  などといった強みがあります。
  調べてみたところ両端への挿入や端の要素の削除が、個人的にクセ強でしたのでまとめました。

要素を挿入する

(<|) と (|>) 演算子を使います。定義は以下になります。
先頭への挿入 : (<|) :: a -> Seq a -> Seq a
末尾への挿入 : (|>) :: Seq a -> a -> Seq a
挿入の方向をイメージするとどうということはありませんが、よくある手続き型言語とは異なり引数に順序がありますので注意しましょう。

.hs

import qualified Data.Sequence as Seq

let que = Seq.fromList [1,2] :: Seq.Seq Int
    ex1 = que Seq.|> 5
    ex2 = 10 Seq.<| que 

main = do
  print ex1
  print ex2
-- fromList [1,2,5]
-- fromList [10,1,2]

端の要素を削除する

端の要素および端の要素を削除したキューを同時に取得する

削除操作について、一応 deleteAt関数があるのですが、先頭または末尾を削除したいだけなのにいちいちインデックスの指定が面倒かつ削除した端の要素も同時に欲しい、という状況が多いと思います(そういう設定にしておきました)。
しかし、その要望を叶える関数はライブラリには存在しません。なので実装してみました。コードは以下

.hs

popFrontWithValue :: Seq.Seq a -> Maybe(a, Seq.Seq a)
popFrontWithValue x = case(Seq.viewl x) of
-- ViweL型をパターンマッチ
-- 空なら Nothing
  Seq.EmptyL -> Nothing
-- (左端の要素、左端を削除した残り)を Just で包んで返却
  (frontValue Seq.:< rest) -> Just(frontValue, rest)

popBackWithValue :: Seq.Seq a -> Maybe(Seq.Seq a, a)
popBackWithValue x = case(Seq.viewr x) of
  Seq.EmptyR -> Nothing
  (rest Seq.:> backValue) -> Just(rest, backValue)

軽く解説します。
まず viewl、viewr という関数らについてですが、定義は以下のようになります。
viewl :: Seq a -> ViewL a
viewr :: Seq a -> ViewR a
Sequence を引数に ViewL または ViewR という型が返されています。おそらく ViewL、ViewR とはなんじゃい、となるのでこちらも確認してみましょう(deriving句は略)
data ViewL a = EmptyL | a :< Seq a
data ViewR a = EmptyR | Seq a :> a
つまり
ViewL は (空) | (先頭の要素) :< (残りのキュー)
ViewR は (空) | (残りのキュー) :< (末尾の要素)
という構造であると同時に、リストの構造に似通っていることが分かります

.hs

let a = Seq.fromList [1,2,3] 
    b = Seq.fromList[] :: Seq.Seq Int

--             先頭の要素 :< 残りのキュー
Seq.viewl a == 1 Seq.:< Seq.fromList[2,3]
--             空です
Seq.viewl b == Seq.EmptyL

--             残りのキュー :> 末尾の要素
Seq.viewr a == Seq.fromList[1,2] Seq.:> 3
--             空です
Seq.viewr b == Seq.EmptyR

つまり、popFrontWithValue と popBackWithValue は、ViewL 型および ViewR 型からパターンマッチを用いて、端から削除した要素および残りのキューをタプルで返したわけです(Maybeモナドのプレゼント付き！)

端の要素または端の要素を削除したキューのみを取得する

当然ながら、端の要素だけが欲しい！端の要素を削除した後のキューだけが欲しい！という方もいらっしゃると思いますので以下の関数を使うとよいでしょう(命名は適当です)。Maybe が必要なければ外してお使いください。

.hs

-- 左端の要素のみ取得
front :: Seq.Seq a -> Maybe a
front x = case(Seq.viewl x) of
  Seq.EmptyL -> Nothing
  (frontValue Seq.:< _) -> Just frontValue

-- 左端の要素を削除した残りのキューを取得
popFront :: Seq.Seq a -> Maybe(Seq.Seq a)
popFront x = case(Seq.viewl x) of
  Seq.EmptyL -> Nothing
  (frontValue Seq.:< rest) -> Just rest

-- 右端の要素のみ取得
back :: Seq.Seq a -> Maybe a
back x = case(Seq.viewr x) of
  Seq.EmptyR -> Nothing
  (_ Seq.:> backValue) -> Just backValue

-- 左端の要素を排除した残りのキューを取得
popBack :: Seq.Seq a -> Maybe(Seq.Seq a)
popBack x = case(Seq.viewr x) of
  Seq.EmptyR -> Nothing
  (rest Seq.:> _) -> Just rest

おまけ

ViewL 型と ViewR 型の演算子 :< と:> ですが、しばしばどっちか分からなくなったり>:だとか<:のような存在しない演算子を書き出してしまいます。そこで私は二度と忘れない覚え方を思いついたのです。
ViewL は悲しい顔で (:<) ViewR は笑顔(:>)です

1. リストだと左端(先頭)への挿入はO(1)ですがが右端(末尾)への挿入がO(n) ↩

2. リストだと左端(先頭)へのリスト結合はO(n)、末尾へのリスト結合はO(n^2) ↩

3. リスト結合のオーダーがちょっと自信ありませんので、間違っていればご指摘いただけるとありがたいです ↩

4. リストだと要素へのアクセスはO(n) ↩