同一画像検索(3): 再帰のKAIZEN

前回の記事で、同一キーのファイルを集める処理に再帰を使った関数tomapを示した。 やりたいのはListを与えて最終的にMap(連想配列)が欲しいだけなのだが、 引数にもMapが入っていて気持ち悪い感じだった。

そのあと、いろいろ記事を見たり本を読んだりして、やはりかっこ悪い書き方だったので KAIZENする。参考にしたのはこの本。プログラミングHaskell

再帰関数の基本形は次のような形らしい。

f [] = v
f (x:xs) = x (+) f xs

ここでvは基底、(+)はいわゆる算術加算ではなく、xとf xsを混ぜ合わせる(笑) 関数とする。この形で前回の処理を書き換えてみる。

(前回)
m = tomap dat Map.empty  -- 呼び出し元

tomap :: [(String, String)] -> Map String [String] -> Map String [String]
tomap  (x:xs) m = tomap xs (Map.insert k l m)
  where
    k = fst x
    l = tolist x (Map.lookup k m)
    
(KAIZEN)
m = tomap dat  -- 呼び出し元

tomap :: [(String, String)] -> Map String [String]
tomap [] = Map.empty
tomap (x:xs) = insertItem x (tomap xs)

insertItem :: Map String [String] -> (String, String) -> Map String [String]
insertItem m x = Map.insert k l m
  where
    k  = fst x
    l  = tolist x (Map.lookup k m)

前回は引数にMapが必要だったがそれがなくなっている。またMap.emptyが関数の中に 移ったことで、呼び出し元でいちいち書かなくて良くなった。とはいえ、あらたにinsertItemが必要になったので、トータルとしてどうなんだろう。

ということで次につながると。基本的な再帰の形になったら再帰ではなくfoldが使えるそうだ。 書き換えてみる。

m = Prelude.foldl insertItem Map.empty dat  -- 呼び出し元

insertItem :: Map String [String] -> (String, String) -> Map String [String]
insertItem m x = Map.insert k l m
  where
    k  = fst x
    l  = tolist x (Map.lookup k m)

呼び出し元にfoldlを使った。ただし、foldlはPreludeにもMapにも定義されているので、 Preludeを明示する必要がある。これで無駄な関数定義が不要になってすっきり。

次回はこれまで確認したところを組み合わせて、実際に動く同一画像検索プログラムを 作ることにしよう。