詳解・id:nobsunさん版 tr

ちょっと大げさか。

 cf. OSS WEB|ossz|oneline|2006-04-28

tr :: [Char] -> [Char] -> (String -> String)
tr set1 set2 = map trans
  where
    trans = foldl (flip $ uncurry add) id (zip set1 set2)
    add k v s q | k == q = v
                | otherwise = s q

これがちゃんと動くことは試してみればすぐにわかる。けど,どうやって動くのかがわかんないぞ。
というわけで,細かく見ていくことにしよう。想定する読者は1週間後の自分。

まずは tr の引数から。定義には書かれていないけど3つの引数をとる。= の右側の map がとるはずの2つの引数のうちひとつしか書いてないから,もうひとつの引数が隠れているのがわかる。これを str としよう。
それからもうひとつ,trans のなかで set1,set2 が使われてるから,この2つは trans の引数だと考えることもできる。さらに str のうちの1文字を引数に取るはずだから trans は3つの引数をとる関数ということになる。
これらを明示的に書いてやるとこうなる。

tr set1 set2 str = map (trans set1 set2) str
  where
    trans set1 set2 c = foldl (fllip $ uncurry add) id (zip set1 set2) c
    add k v s q | k == q = v
                | otherwise = s q

つぎは add。これが実際の文字の変換を行う関数だろう。引数を4つとって,うち3つめは何らかの関数。
で,問題は trans の中身。ここがわからない。foldl は引数を3つとる関数だけど,ここでは4つとっているように見える。なぜだ,おかしい。

わかんないから,それぞれの関数の型を順に追ってみることにしよう。ghci で関数の型を確認できるように wehre 節をなくして次のように書き換える。

tr set1 set2 = map (trans set1 set2)
trans set1 set c = foldl (flip $ uncurry add) id (zip set1 set2) c
add k v s q | k == q = v
            | otherwise = s q

それじゃいってみよう。まずは trans。

trans :: (Eq b) => [b] -> [b] -> b -> b

思った通り3引数。
つぎはその中身のほうを少しずつ確かめてみよう。foldl の第1引数と思われる filp $ uncurry add の中を少しずつ。
add

add :: (Eq a) => a -> t -> (a -> t) -> a -> t

uncurry add

uncurry add :: (Eq a) => (a, b) -> (a -> b) -> a -> b

add の第1,第2引数をひとつのタプルにまとめている。t が b に変わってるけどこれは型変数の名前が変わっただけだから気にしない。
つぎ,flip $ uncurry add

flip $ uncurry add :: (Eq a) => (a -> b) -> (a, b) -> a -> b

第1引数と第2引数を入れ替えてるだけだな。
つぎは foldl (flip $ uncurry add) ……のまえに foldl を確認。

foldl :: (a -> b -> a) -> a -> [b] -> a

ほーらおかしい。第1引数の関数は (a -> b -> a) じゃなきゃいけないのに (flip $ uncurry add) は(a -> b) -> (a, b) -> a -> b だ。なのに実際に確かめてみると

foldl (flip $ uncurry add) :: (Eq a) => (a -> b) -> [(a, b)] -> a -> b

なぜだ。(flip $ uncurry add) の型 (a -> b) -> (a, b) -> a -> b とfoldlの第1引数の型 (a -> b -> a) を眺めながら考える。

……考える。

……まだ眺める。

……一晩寝る。

あー!!そうか,カリー化だ。3引数の関数に引数を1つ与えると2引数の関数が得られる。もう1つ引数を与えれば1引数の関数を得る。
つまり flip $ uncurry add を3引数の関数じゃなく,2引数をとって1引数の関数を返す関数だと考えればいい。型式で書くとこう。

flip $ uncurry add :: (Eq a) => (a -> b) -> (a, b) -> (a -> b)

これなら foldl の第1引数の型と対応するじゃないか。

(a -> b) -> (a, b) -> (a -> b)
   |          |          |
   |          |          |  (a -> b) と a ,(a, b) と b が対応する
   |          |          |
   a     ->   b    ->    a

この対応にしたがって foldl の型を書き換えてみると

foldl :: ((a -> b) -> (a, b) -> (a -> b)) -> (a -> b) -> [(a, b)] -> (a -> b)

これに (a -> b) -> (a, b) -> (a -> b) である (flip $ uncurry add) を与えて得られる関数の型は

(a -> b) -> [(a, b)] -> (a -> b)

上で書いた foldl (flip $ uncurry add) の型と一致する(一番右の a -> b を括弧でくくってやればいい)。つまり,この関数は「 (a -> b) である関数と [(a,b)] --(a,b)であるタプルのリスト--を引数にとって (a -> b) である関数」を返すってことだ。

ここまでくればあとは簡単だ。
実際の引数を見てみると,第1引数には id,第2引数には zip で得られるタプルのリストとなっている。id の型は (a -> a) だけど,これは a と b がおなじ型だと考えればいい。set1 と set2 は両方とも文字列で,こっちも a と b がおなじになるから問題はない。でもってその結果は(bをaに置き換えて書けば) (a -> a) である関数,となる。
結局,foldl (flip $ uncurry add) id (zip set1 set2) は「文字を引数にとって,適切に変換した文字を返す関数」ってことになる。どう変換するかは関数自体が知っている--(zip set1 set2)がいわば変換テーブルになっている。これが trans の実体って訳だ。

tr 全体ではさらに簡単。trans を str の頭から順に適用しているだけだ。

ふー。やっと解読したって感じだな。なんか,関数は値を返すものだというのがしみこんでいて,「関数を返す関数」というのに頭が回らない。なんだか「関数を返す関数」を自在に使えるようになることが関数言語使いになるってことなのかと思った。

ところで,話は変わるけど。

あれっ.これだめだ.tr “aaa” “xyz” “abracadabra” は tr “a” “z” “abracadabra” と同じじゃなきゃいけないのに...

これはそういうものなんだろうか。俺のPCに入ってる tr コマンドでは ‘a’ は ‘x’ に変換される。

>echo abracadabra | tr aaa xyz
xbrxkxdxbrx

このコマンド,Windows には付いてないからどこからか手に入れたもののはず。よく覚えてないけど GNU だか Cygwin だったかじゃなかったかなぁ。

カテゴリー: Haskell パーマリンク

1 Response to 詳解・id:nobsunさん版 tr

  1. takatoh のコメント:

    一番肝心な部分で関数の型を書き間違えてたので修正。(flip $ uncurry add)の型:
    ○ (a -> b) -> (a, b) -> a -> b
    × (a, b) -> (a -> b) -> a -> b

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください