Haskell でリストの要素を swap する 9 つの方法

0. Python でリストの要素を swap する方法

Python で「リストの特定のインデックス i, j の要素を swap したい」場合、以下のように書ける。

def swap(i, j, ary):
    tmp    = ary[i]
    ary[i] = ary[j]
    ary[j] = tmp

要素を交換するために、一時的に値を退避させておく変数 tmp を利用し、要素を上書き。

多重代入を使うなら、一時変数を省略できる。

ary[i], ary[j] = ary[j], ary[i]

こういった操作ができるのは、Python ではリストが「変更可能なシーケンス型」として定義されているため。

では、同様のことを変数の更新ができない Haskell ではどのように書けばよいのか？

 

1. データコンストラクタによる分解と take, drop 関数を使う

例えば、具体的に 0 ～ 7 を要素に持つリストの 2 番目と 5 番目の要素を交換したい場合で考える。

典型的なリスト処理は、リストをデータコンストラクタで分解し、要素を先頭から末尾へと辿る。

先頭の要素 0 から見て、交換したい要素の位置は 2 番目と 5 番目。これを一つ後ろに進め、要素 1 から見た場合、交換したい要素の位置は 1 番目と 4 番目になる。同じように要素 2 から見たら、0 番目と 3 番目。

つまり、先頭から末尾へと視点を移していくと、交換したい要素の位置が相対的に変化する。これを利用して swap 関数を考えればよい。

交換したい要素の小さい方のインデックスが 0 より大きい場合は、元の要素をそのまま返す。データコンストラクタで (x:xs) のように分解したとき、リスト xs に対しては swap する位置を 1 ずつ変化させて再帰的に定義。

swap i j (x:xs)     = x : swap (i-1) (j-1) xs

次に、交換したい要素の小さい方のインデックスが 0 となった場合。以下のように区分けすれば take, drop 関数を組み合わせればよいことがわかる。

swap 0 j xs'@(x:xs) = xs' !! j : take (j-1) xs
                      ++ x : drop j xs

全体は gist: 940061 — Gist

 

2. スライスしてから結合

別の方法としては、予め特定のインデックス間の要素をスライスする関数をしておき、下図の黄色の部分を取得した後、 swap する要素を結合して、最後に全体を合わせる。

slice 関数は、ライブラリに定義されている splitAt 関数を利用して定義。

slice i j = snd . splitAt i . fst . splitAt (j+1)

これを使い、

swap i j xs = let a = slice' 0     (i-1)
                  b = slice' (i+1) (j-1)
                  c = slice' (j+1) (length xs - 1) 
              in a ++ (xs!!j):b ++ (xs!!i):c
    where
      slice' i j = slice i j xs

全体は gist: 940063 — Gist

 

3. 累積変数でインデックスを付ける

Python のリストはインデックスが付いている。しかし、Haskell のリストは付いていない。インデックスが利用できれば swap 関数を考えやすいのではないかな？

累積変数でインデックスを代替する方法を考える。

swap i j xs0 = swap' 0 xs0
    where
      swap' idx [] = []
      swap' idx (x1:xs1) | idx == i  = xs0 !! j : swap''
                         | idx == j  = xs0 !! i : swap''
                         | otherwise = x1       : swap''
          where
            swap'' = swap' (idx+1) xs1

gist: 940091 — Gist

 

4. zip 関数でインデックスを付け、累積変数を使い末尾再帰

インデックスを付けるなら、累積変数を使うよりも zip 関数を使う方が楽。予めインデックス付けしてから関数を適用する方法に変更してみる。

ついでなので、累積変数 acc を利用し、末尾再帰で定義。

swap i j xs0 = swap' [] withIdx
    where
      withIdx = zip [0..] xs0

      swap' acc []                         = reverse acc
      swap' acc ((idx,x1):xs1) | idx == i  = swap' ((xs0!!j):acc) xs1
                               | idx == j  = swap' ((xs0!!i):acc) xs1
                               | otherwise = swap' (x1:acc)       xs1

gist: 940084 — Gist

 

5. 畳み込み関数

データコンストラクタでリストを分解し、順に要素を辿っていくのなら、畳み込み関数を使った方がスッキリと書ける。

累積変数 acc を用意し、そこへ要素を追加すると伴に、インデックスを更新していく。

swap i j xs = reverse $ fst $ foldl f ([],0) xs
    where
      f (acc, idx) x | idx == i  = (xs!!j:acc, idx+1)
                     | idx == j  = (xs!!i:acc, idx+1)
                     | otherwise = (x:acc, idx+1)

gist: 940099 — Gist

 

6. map 関数でシンプルに

考えてみたら、データコンストラクタによる分解、累積変数、畳み込み関数とか面倒なことを考えなくても、map 関数で個々の要素を変換する方法が一番考えやすくないかな？

swap i j xs = swap' withIdx
    where
      withIdx = zip [0..] xs
      
      swap' = map f
          where
            f (idx, x) | idx == i  = xs !! j
                       | idx == j  = xs !! i
                       | otherwise = x

gist: 940129 — Gist

 

7. オブジェクト指向的に考える

実は、一番最初に考えた方法は全然違う。オブジェクト指向で考える方が馴染みがあるので、個々の要素に自分で考えてもらう方が自然な感じがする。

頭に入れておくことは、個々の要素が把握できる情報を、

• 自分の持っている値
• 自分よりも後ろにあるリスト

の 2 つだけだと制約を付けて考えること。

イメージしやすいように、リストを一方向リストで描く。

リストをデータコンストラクタの分解により、先頭から末尾のリストへと次々に swap 関数を適用していくことをイメージする。

swap 0 3 xs となったとき、リスト xs は自分の持っている値 (先頭要素) が swap 対象であることを知る。ここから後ろのリストに対して、この要素が保持する値を swap する値を取得したい。この役割を担うのが関数 idxAt 。

idxAt を後方のリストに対して次々に適用していく。

目的の要素に辿り着いたら、その値を返す。

これで swap するための片方の値 5 を取得できた。

次に、先ほどの swap 0 3 xs のときに戻り、もう片方の値を swap するため、後方のリストへ自分が保持する値 2 を渡していく。この役割を担うのが関数 set 。

後ろのリストへ set 関数を適用していく。

目的の要素に辿り着いたら、要素を置き換える。

以下が上記を実現したコード。

swap 0 j (x:xs) = idxAt (j-1) xs : set x (j-1) xs
    where
      idxAt 0 (x:_) = x
      idxAt j (_:xs) = idxAt (j-1) xs

      set x 0 (_:ys) = x:ys
      set x j (y:ys) = y:set x (j-1) ys

swap i j (x:xs) = x : swap (i-1) (j-1) xs

gist: 940153 — Gist

 

8. State モナド (1)

全く別の方法として、効率も何もかも無視し、「状態の変更」という視点から State モナドを利用したらどう書けるか試す。

さて、何をどう考えればいいのか？

下図のように想定する。

• 内容が変更されると想定する「リスト」と「一時変数」を用意

これが時刻 t0 ～ t3 において、以下のように変化すると考える。

1. 時刻 t0 : リストを swap する前の状態。
2. 時刻 t1 : 一時変数にリストの 2 番目の要素を代入する。
3. 時刻 t2 : リストの 2 番目の要素を 5 番目の要素で上書き。
4. 時刻 t3 : リストの 5 番目の要素を一時変数の値で上書き。

時刻 t0 における「リスト」と「一時変数」の状態を、時刻 t1 の状態に変更する関数を f1 とする。( 以降それぞれ f2, f3 と仮定。 )

State モナドを利用する場合、型を合わせるために「状態を変更する関数」を

s –> (a, s)

という型であると想定する必要がある。

関数 f1 ～ f3 の関数を上記の型に合うように考えるなら、

f1 :: ([a], a) –> ((), ([a], a))

しかし、これだとごちゃごちゃして見にくいので、予め以下のように別名を付けておく。

リストは、

type Ary a = [a]

一時変数は、

type Temp a = a

上記 2 つを合わせたものを、

type Vars a = (Ary a, Temp a)

これにより、先ほどの f1 を以下のように書ける。

f1 :: Vars a –> ((), Vars a)

更に、ライブラリに定義されている State モナドを利用するために、

f1 :: State (Vars a) ()

という型に合わせる。

 

予め State モナドを利用するために、

import Control.Monad.State

関数 f1 は「一時変数にリストの i 番目の要素を代入する」。名前を toTemp とするなら、

toTemp :: Int -> State (Vars a) ()
toTemp i = State $ \(xs, tmp) -> ((), (xs, xs !! i))

get, put 関数を使って定義すると、

toTemp i = get >>= \(xs, tmp) ->
           put (xs, xs!!i)

modify 関数で置き換えるなら、

toTemp i = modify $ \(xs, tmp) -> (xs, xs!!i)

 

リストの i 番目の要素を j 番目の要素で上書きする関数を copyElem とすると、

copyElem :: Int -> Int -> State (Vars a) ()
copyElem i j = modify $ \(xs, tmp) ->
               (take i xs ++ xs!!j : drop (i+1) xs, tmp)

 

リストの j 番目の要素を一時変数の値で上書きする関数を formTemp とすると、

fromTemp :: Int -> State (Vars a) ()
fromTemp j = modify $ \(xs, tmp) ->
             (take j xs ++ tmp : drop (j+1) xs, tmp)

上記 3 つの関数を使い swap を定義する。

swapS :: Int -> Int -> State (Vars a) ()
swapS i j = toTemp i >> copyElem i j >> fromTemp j

swap i j xs = fst $ execState (swapS i j) (xs, 0)

全体は gist: 940268 — Gist

 

9. State モナド (2)

上記の State モナドでは「一時変数」に相当するものを想定した。しかし、これがなくても問題ない。

別名を付けるのも面倒なので、リストの特定のインデックスを更新する関数 update を

update :: Int –> a –> [a] -> ((), [a])

とする。 これを元に State モナドに合わせるために以下のように型を定める。

update :: Int -> a -> State [a] ()

この update 関数の定義は、

update i x = State $ \xs -> ((), take i xs ++ x : drop (i+1) xs)

先ほどと同じように get, put 関数を使うなら、

update i x = get >>= \xs ->
             put $ take i xs ++ x : drop (i+1) xs

modify 関数で置き換えるなら、

update i x = modify $ \xs -> take i xs ++ x : drop (i+1) xs

次に、リストの特定のインデックスの値を取得する関数を getIdxAt とすると、その型は、

getIdxAt :: Int -> State [a] a

この定義は、

getIdxAt i = State $ \xs -> (xs !! i, xs)

get 関数を使うと、

getIdxAt i = get >>= \ xs ->
             return $ xs !! i

関数合成を利用すると、

getIdxAt i = get >>= return . (!! i)

この二つの関数を使い swap を定義する。

swapS i j = getIdxAt i >>= \a ->
            getIdxAt j >>= \b ->
            update i b >>
            update j a

swap i j xs = (execState $ swapS i j) xs

上記 swapS 関数では変数 a, b の二つを利用しているが、一つだけでも十分。

swapS i j = getIdxAt i >>= \tmp ->
            getIdxAt j >>= update i >>
            update j tmp

do 式を使うなら、

swapS i j = do tmp <- getIdxAt i
               update i =<< getIdxAt j
               update j tmp

そういえば、get 関数を使うなら、getIdxAt 関数も必要もないか。

swapS i j = do xs <- get
               update i (xs!!j)
               update j (xs!!i)

全体は gist: 940572 — Gist