詳解・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 が使われてるから，この２つは trans の引数だと考えることもできる。さらに str のうちの１文字を引数に取るはずだから trans は３つの引数をとる関数ということになる。
これらを明示的に書いてやるとこうなる。

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。これが実際の文字の変換を行う関数だろう。引数を４つとって，うち３つめは何らかの関数。
で，問題は trans の中身。ここがわからない。foldl は引数を３つとる関数だけど，ここでは４つとっているように見える。なぜだ，おかしい。

わかんないから，それぞれの関数の型を順に追ってみることにしよう。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

思った通り３引数。
つぎはその中身のほうを少しずつ確かめてみよう。foldl の第１引数と思われる 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 の第１，第２引数をひとつのタプルにまとめている。t が b に変わってるけどこれは型変数の名前が変わっただけだから気にしない。
つぎ，flip $ uncurry add

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

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

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

ほーらおかしい。第１引数の関数は (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の第１引数の型 (a -> b -> a) を眺めながら考える。

……考える。

……まだ眺める。

……一晩寝る。

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

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

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

(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) である関数」を返すってことだ。

ここまでくればあとは簡単だ。
実際の引数を見てみると，第１引数には id，第２引数には 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 だったかじゃなかったかなぁ。