いわゆる関数型言語が (扇情的に)バカのためのものと言われるのを実感したことについて
扇情的な宣伝文句として「バカ」のような言葉を使うのは個人的には好きではないのですが、まさにそういう体験をしてしまったので備忘録的に残しておこうと思いました。好きでないというのは、まあ普通に失礼じゃね？というだけのことなのですが。宣伝文句でなくても使わないようにしたいところです。
Elmという言語があります。いわゆるAltJSの一つで、文法などはHaskellとかに近いです。コンパイラもHaskellで書かれています。 Haskellがデフォルトで評価を遅延させるのに対し、Elmでは正格評価されます。そのため、再帰関数は末尾再帰にしてやることで最適化が効くようになります。確かバージョン0.16以降で有効だったはずです。他の言語でも、末尾再帰にすることで最適化が効くものがあるようです。例えばErlangでは、末尾再帰になっている関数はスタックフレームが除去されるとのことです。
さて、Elmで遊んでみたときに、以下のような関数を書きました。リストの値に関数を適用した結果でグループ分けするというものです。
groupBy : (a -> b) -> List a -> List (List a) groupBy f list = case list of [] -> [] x :: xs -> List.filter (\y -> f y == f x) (x :: xs) :: groupBy f (List.filter (\y -> f y /= f x) xs)
(シンタックスにElmが使えないっぽかったので、Haskellを指定してみました。微妙に文法が違うようですが、まあ大体一緒らしいのでいいでしょう。)
上のようにgroupByを定義すると、例えば
> groupBy String.length ["foo", "bar", "hello", "baz", "world"] [["foo","bar","baz"],["hello","world"]] : List (List String)
となります。ところがこの関数を末尾再帰にしようとしたとき、僕にはどういうふうにすればよいかすぐに分かりませんでした。バカなので……。
困った僕は簡単な問題の一般化を当て嵌めて考えてみることを思いつきました。階乗を再帰関数で書くのは有名なので、これを使って考えることにしました。末尾再帰でないバージョンはこうです。
factorial : Int -> Int factorial n = case n of 0 -> 1 _ -> n * factorial (n - 1)
負数に対応していませんが、今は一般化することが目的ですから細かいことは気にしません。2番目のアームを見ると、次のような形に一般化できそうです。
f x = g (f (h x))
上の場合では、g x y = x * y, h x = x - 1です。そして、階乗の末尾再帰であれば僕にでも書くことができます。
factorial_ n acc = case n of 0 -> acc _ -> factorial_ (n - 1) (n * acc) factorial n = factorial_ n 1
ここから末尾再帰の一般化を考えると、
関数f x = g x (f (h x))に対して、適切なyを選ぶことでf1 x y = f1 (h x) (g x y)の形に変形してもよい
といえそうです。これが一般に成り立つかどうか、僕には分かりません。バカなので……。
反例があったとしても、上のgroupByで成り立てばよいのです。
f1 = groupBy f h = List.filter (\y -> f x /= f y) g xs ys = List.filter (\y -> f x == f y) xs :: ys
を当てはめてみると、
groupBy_ f (x::xs) acc = groupBy_ f (List.filter (\y -> f x /= f y) xs) (List.filter (\y -> f x == f y ) (x :: xs) :: acc
のようにできそうです。replなどで確かめてみると、どうやら正しい結果が得られているようでした。なんだかこのままだと読みにくいですが、なんとなくやっていることは分かるんじゃないでしょうか。
賢い人であればすぐに末尾再帰にできたでしょうが、そうでなくても何とか力技で末尾再帰ができました。そもそも慣れの問題もあり、手続き型の言語であればもっと簡単に書けたのかも知れませんが、タイトルに書いたようなことを思ったので記事にした次第です。
