Haskell で変数の更新を伴うインデックス付きループを再帰で置き換えるには

1. ループ内における変数の更新はややこしい

Programming in Scala (p354) に次のような関数の例が書かれている。

• 「
  Programming
  in Scala
  

  Scalaスケーラブル
  プログラミング
  
  文字列の配列の中から最長の文字列と、そのインデックスを返す」

これを Python で書くなら、

def longestWord(words):
    word = words[0]
    idx = 0
    for i in range(1, len(words)):
        if len(word) < len(words[i]): 
            word = words[i]
            idx = i
    return (word, idx)

print longestWord("The quick brown fox".split())

やってることは単純。しかし、昔からこういうコードを読むのは苦手だった。

最初にローカル変数を複数用意して、ループ内でごちゃごちゃと更新。この程度ならまだしも、ループが二重以上になると頭が沸騰してくる。 (+_+)

曲者はループ内での変数の更新。

更新されている変数は、

• 最長の文字列を保持する word 
• 最長の文字列のインデックスを保持する idx
• 文字列の配列要素を走査するための i

配列を走査するイメージを頭に描きつつ、状況に応じて変数を更新。

誰かに計算を任せ、その結果を受け取るという楽な方法ではない。

 

2. 「再帰」と更新用の引数を用いて、変数の更新を模倣する

では、これを変数の更新が許されず、for ループも用意されていない Haskell でどう書くのか？

次の 2 点を覚えておく。

1. ループを「再帰」で置き換える。
2. 変数の更新は、再帰で与える引数において、更新後と想定する値を渡すことで代替。

加えて、Haskell では配列ではなくリストがよく用いられ、配列的な発想とは異なることに注意。

構造的な違いとして、配列は要素が格納されている場所にインデックス情報が存在するのに対して、リストはそれがない。リストが再帰的な構造を基盤として要素を走査するが、配列はインデックスによりそれを行うこと。

よって、完全に対応したものを考えているのではなく、結果として同等な方法の比較をする。

 

更新される値を考えない場合

まずは、インデックスは無視して、最長の文字列を返すだけの関数を考える。

longestWord [x]    = x
longestWord (x:xs) = let word = longestWord xs
                     in if length x < length word 
                        then word 
                        else x

リストに対する関数を考えるときは、オブジェクト指向のアナロジーで考えているので、上記二行目のコード、

longestWord xs

を以下のように頭の中で置き換えている。

xs.longestWord()

全体としては下図のようなイメージ。

 

更新される値に相当する引数を使う

次に、インデックスも返すために、更新用の変数と同じ役割をする引数 idx を関数に追加する。 idx 変数に配列のインデックスに相当する値を累積させる。(これを累積と言うのか微妙だけれど。。)

longestWord' idx [x]      = (x, idx)
longestWord' idx (x1:xs1) = let (x2, idx2) = longestWord' (idx+1) xs1
                            in if length x1 < length x2
                               then (x2, idx2)
                               else (x1, idx)

longestWord xs = longestWord' 0 xs

先ほどと同じく上記二行目のコード、

longestWord’ (idx+1) xs1

を以下のように頭の中で置き換えている。

xs1.longestWord’(idx+1)

これより、インデックスを累積 (更新) するための変数は、リストのある要素が次の要素に対して、特定の計算の結果を渡す先だと見ることができる。

リスト処理における再帰的な関数は、オブジェクト指向の考え方と親和性が高い。

 

3. 予めインデックスを用意しておく方法

別の方法としては、対象のリストとは別にインデックスのリストを用意し、それと組み合わせた結果に対して関数を定義する。

longestWord' :: [(String, Int)] -> (String, Int)
longestWord' [x]             = x
longestWord' (x1@(x,idx):xs) = let x2@(x', idx') = longestWord' xs
                               in if length x < length x' 
                                  then x2 else x1
                                  

longestWord xs = longestWord' $ zip xs [0..]

この方法は、インデックス情報を持った配列に構造を予め似させてから計算を行なっていると言える。ただし、ループはリストの再帰的な構造を利用することにより代替していることは先ほどと変わりはない。

また、遅延評価の Haskell では、予めどのくらいインデックスが必要か考えておく必要はない。

 

4. State モナドで試したら

ところで、状態の「更新」と聞いて連想するのは State モナド。「longestWord’ 関数を再帰的に適用するごとにインデックスの状態を更新する」と見なして考えたら、どのように書けるのだろう？

 

s –> (a, s) 型の関数

最初は、ライブラリに用意されている State モナドを利用するのではなく、関数をつなげる関数も自分で定義して考える。

State モナドで、状態の変更をシミュレートした関数として用いられるのは、

s –> (a, s)

という型を持つ。

先ほど定義した longestWord’ 関数の場合であれば、第1引数と第2引数を逆転させ、適当に配列を与えたときの型がこれに相当する。

*Main> :t (flip longestWord') ["The","quick","brown","fox"]
(flip longestWord') ["The","quick","brown","fox"]
  :: (Num a) => a -> ([Char], a)

この関数を再帰によりつなぎ、計算が進行するに連れ、インデックスを保持する変数が更新されていくと考えてみる。

 

計算をつなげる関数

最初に以下の型を持つ関数に対して、

s –> (a, s)

1. 何らかの状態を持つ型 s の値を引数に与えると、
2. その値が更新されたことに付随して、
3. 結果 a が生じる
4. … と解釈できる関数を「つなげる」関数

を考える。( 詳しくは「Haskell の State モナド (1) - 状態を模倣する」を参照 )

読みやすさを考慮して、上記関数の型に別名を付けておく。

type State s a = s -> (a, s)

この State s a 型をつなげる計算を comb とする。 (>>= に相当)

comb :: State s a -> (a -> State s b) -> State s b
comb m k = \s -> let (x1, s') = m s in k x1 s'

comb の第1引数の結果に対して、第2引数が関心を持たない関数を comb_ とする。 (>> に相当)

comb_ :: State s a -> State s b -> State s b
comb_ m n = m `comb` \_ -> n

状態の変更を行わず、与えた引数を結果とする関数を ret とする。 (return に相当)

ret :: a -> State s a
ret x = \s -> (x, s)

 

計算をつなげる関数を使って longestWord’ を定義

準備ができたので、longestWord’ 関数の定義をする。

ここでは「インデックスを保持する変数」が更新されることに付随して、「最長の文字列」という結果が生じると見なして考える。上記で定義した 3 つの関数を使うと、更新されるインデックスを隠蔽できる。

State s a の s に相当するのが「インデックス」を表わす Int 型。 a に相当するのが「最長の文字列」を保持する String 型。

longestWord' :: [String] -> State Int String
longestWord' [x]    = ret x
longestWord' (x:xs) = longestWord' xs `comb` \x' ->
                      if length x < length x'
                      then inc `comb_` ret x'
                      else ret x

inc = \idx -> ((),idx +1) 

longestWord xs = longestWord' xs 0

インデックスを更新する操作を inc 関数で定義している。

( コード全体は gist: 823793 - GitHub )

 

5. Control.Monad.State を利用する

今度はライブラリに用意されている関数に置き換える。

最初に State モナドを利用するためにモジュールをインポート。

import Control.Monad.State

これを利用して、

longestWord' :: [String] -> State Int String
longestWord' [x] = return x
longestWord' (x:xs) = longestWord' xs >>= \x' ->
                      if length x < length x'
                      then inc >> return x'
                      else return x

inc = modify (+1)

longestWord xs = runState (longestWord' xs) 0

inc 関数は、インデックスの状態に相当する変数を更新していた。このような状態を更新する関数もライブラリに用意されている。

Control.Monad.State.Class

modify :: MonadState s m => (s -> s) -> m

Maps an old state to a new state inside a state monad. The old state is thrown away.

( コード全体は gist: 823796 – GitHub )

 

do 式

モナドは do 式を利用できるので、longestWord’ 関数を以下のように書くことも可能。

longestWord' :: [String] -> State Int String
longestWord' [x]    = return x
longestWord' (x:xs) = do x' <- longestWord' xs
                         if length x < length x'
                            then do inc 
                                    return x'
                            else return x

( コード全体は gist: 823796 - GitHub )

 

6. 更新する変数を増やした場合

最初に定義した Python のコードでは、更新される変数は idx と word だった。上記 Haskell のコードでは、更新される値がインデックスに限定されている。

idx と word が更新されると想定し、より Python で書いたときのコードに似せるなら、

longestWord' word idx []     = (word, idx)
longestWord' word idx (x:xs) = let (x', idx') = longestWord' x (idx+1) xs
                               in if length word < length x'
                                  then (x', idx')
                                  else (word, idx)

longestWord (x:xs) = longestWord' x 0 xs

大雑把なイメージは下図。 longestWord 関数において、longestWord’ 関数の第1・第2引数を与えることが、Python における変数の初期化に相当する。

先ほどと同じようにオブジェクト指向的に見るなら、

longestWord' x (idx+1) xs

を以下のように頭の中で置き換える。

xs.longestWord’(x, idx+1)

 

State

word, idx を更新される変数と見なし、先ほどと同じく、ライブラリに用意されている State モナドを利用しないで書いてみる。

今回は、更新される変数として word, idx をタプルの要素とし、結果に相当するものは () とする。

関数の型は、

[String] –> State (String, Int) ()

更新される変数 word を計算のつながりの中で参照するためには、状態を結果として取り出す必要がある。そのための関数を get とすると、

get :: State s s
get = \s -> (s, s)

状態を変更するための関数 put も用意しておく。

put :: s -> State s ()
put x = \_ -> ((), x)

最終的に結果は必要なく、状態がわかれば良いので、そのための関数 execState を定義。

execState :: State s a -> s -> s
execState s s0 = snd $ s s0

これらを用いて、

longestWord' :: [String] -> State (String, Int) ()
longestWord' [] = ret ()
longestWord' (x:xs) = get             `comb` \x1@(word, idx) ->
                      put (x, idx+1)  `comb_` 
                      longestWord' xs `comb_` 
                      get             `comb` \x2@(word', idx') ->
                      if length word < length word' then put x2 else put x1
                   
longestWord (x:xs) = (execState $ longestWord' xs) (x, 0)

( コード全体は gist: 823947 – GitHub )

 

Control.Monad.State

Control.Monad.State を利用するなら、

longestWord' [] = return ()
longestWord' (x:xs) = get             >>= \x1@(word, idx) ->
                      put (x, idx+1)  >> 
                      longestWord' xs >> 
                      get             >>= \x2@(word', idx') ->
                      if length word < length word' then put x2 else put x1

longestWord (x:xs) = execState (longestWord' xs) (x, 0)

( コード全体は gist: 824329 - GitHub )

上記を do 式で書き直すと、

longestWord' [] = return ()
longestWord' (x:xs) = do x1@(word, idx) <- get
                         put (x, idx+1) 
                         longestWord' xs
                         x2@(word', idx') <- get
                         if length word < length word' then put x2 else put x1

( コード全体は gist: 824329 – GitHub )

 

7. foldl を使い、畳み込みながら更新

追記(2011.2.19) : 畳込み関数を使うなら、foldl の第2引数に更新する変数に相当する値を与える。

longestWord' (x:xs) = foldl f (x, 0, 0) xs
    where
      f (word, idx, i) w | length word < length w = (w, inc, inc)
                         | otherwise              = (word, idx, inc)
          where 
            inc = i + 1

longestWord xs = let (word, idx, _) = longestWord' xs in (word, idx)

 

State

Control.Monad.State を使うなら、どうなるのだろう？ (cf. Haskell の sequence 関数 - foldr をイメージして)

読みやすくするために予め別名を付ける。

type Word  = String  -- 最長の文字列
type Idx   = Int     -- 最長の文字列のインデックス
type Index = Int     -- ループで使うインデックス

これを用いて、畳み込むとき、ループで使うインデックス (Index) が更新されていくと同時に、 (最長の文字列、そのインデックス) という結果が生じると解釈する。

longestWord' :: [String] -> State Index (Word, Idx)
longestWord' (x:xs) = foldl f (return (x, 0)) xs
    where
      f :: State Index (Word, Idx) -> String -> State Index (Word, Idx)
      f s w = s >>= \(word, idx) ->
              (if length word < length w
              then return (w, idx+1)
              else return (word, idx)) >>= \wordIdx ->
              State $ \i -> (wordIdx, i+1)

longestWord xs = let (wordIdx, _) = runState (longestWord' xs) 0 in wordIdx

( コード全体は gist: 834817 - GitHub)

do 式で置き換えるなら、

longestWord' :: [String] -> State Index (Word, Idx)
longestWord' (x:xs) = foldl f (return (x, 0)) xs
    where
      f :: State Index (Word, Idx) -> String -> State Index (Word, Idx)
      f s w = do (word, idx) <- s
                 wordIdx <- if length word < length w
                            then return (w, idx+1)
                            else return (word, idx)
                 State $ \i -> (wordIdx, i+1)

longestWord xs = let (wordIdx, _) = runState (longestWord' xs) 0 in wordIdx

( コード全体は gist: 834817 - GitHub )

//TODO

「Haskell の Data.IORef を使い IO モナドの中で変数を更新」につづく

 

参考記事

• 第6回 局所的な「状態」を利用するためのStateモナド - 本物のプログラマはHaskellを使う：ITpro