Haskell における文字列の連結

{-

ひとつ関数型言語らしい書き方を見つけたので試してみた。Squeak では、文
字列を連結させるには二つのやり方がある。ひとつは、単に文字列をくっつけ
る。もうひとつは、ストリームを作って流し込む。違いは効率にある。文字列
をくっつけるためには、くっつけた結果のための新しいメモリが必要だが、沢
山の文字列をくっつける状況だと、くっつける度にメモリを作るのは大変だ。
文字列が長くなればなるほど時間がかかる。ストリームはその辺を上手いこと
やる。これは大体どの言語でも同じ。Haskell では、ストリームではなくリン
クリストを使うが、考え方は似ている。しかし、「関数合成」を使うところが
違う。

まず遅いバージョン。1 から好きな数までの数字を、改行と共にくっつけて返
す関数を考える。この関数では、再帰的に数字を小さいものからくっつけてい
る。-}

 -- putStr (concatNumbers 10) のように使います。
countNumbers x | x < 1     = ""
               | otherwise = countNumbers (x - 1) ++ show x ++ "\n"

{- 表記は違うが、Squeak でも同じように書ける。

countNumbers: x 
    "self countNumbers: 10"
    ^ x < 1
        ifTrue: ['']
        ifFalse: [(self countNumbers: x - 1), x asString , String cr]

関数型ではどうするのか、オブジェクトではなく、関数をくっつける。-}

 -- putStr (countNumbers2 10 "")
countNumbers2 :: Integer -> ShowS
countNumbers2 x | x < 1 = \s -> s
                | otherwise = countNumbers2 (x - 1) . shows x . ('\n' :)

{- このプログラム読むためには前提となる知識が幾つか必要だ。まず型定義。:: 
の後ろに関数が期待する型を書く。無くても動くがエラーチェックになるので
あった方が良い。次に Prelude に定義される ShowS 型。これは String ->
String の別名で、文字列を受け取り文字列を返す関数をあらわす。と言うと
難しいが、要するに unix の「パイプ」だと思えばよい。パイプはまさに関数
合成のメタファとして最適だ。入り口から材料が入って、出口に結果が出てく
る。パイプの繋ぎ方を変えると別の物体が現れる。パイプを連結するための演
算子が . (ドット)だ。ShowS は文字列を受け取り文字列を返すので、連結し
ても全体は ShowS のままだ。unix の | と反対に、データは右から左に流れ
る。直感に反するが、数学の f(g(x)) を f.g x と書く書き方から来ているの
で文句は言えない。

このプログラムのコンセプトは次のとおり、工場に文字列の流れるコンベヤが
ある。配置された工員は文字列の先頭に文字をひとつだけ付加する事が出来る
(実装の話をすると、この先頭に文字をひとつだけ付加する操作は文字列の長
さに関わらず同じ速度だ)。工員を適当に並べて好きな文字列を出力する事が
出来る。

これを再帰的に考える。出力したい数字は 1 以上なので、数字が 1 以下の時
は何も出力しない。という事は流れてきた文字列をそのまま流す x < 1 = \s
-> s 。\ はラムダ演算子だが、字面で何をやってるか分かると思う。

それ以外 (otherwise)は、まず流れてきた文字列の先頭に改行をくっつける。
('\n' : ) 本来は : LISP で言う CONS の意味で、リストをくっつける時に使
う演算子なのだが (例 1 : 2 : 3 : [] => [1:2:3]) このように引数を書かな
いと、引数が欲しくて仕方が無い状態になる(カリー化)。この場合はひとつの
文字列を欲しい状態になるので、文字列を引数にとって文字列を返す関数だと
考える事が出来る。

この調子で、さらにその先頭に表示した数字をくっつければよいのだが、桁数
の事も考えて自分で作るのは面倒くさいので、出来合いの shows 関数を使う。
shows 関数はオブジェクトをひとつ受け取り、そのオブジェクトを表示するた
めの工員 (ShowS) を返す。

さらにこれを繰り返せばよい。関数合成を直接サポートする言語は珍しいが、
関数合成自体の考え方は画像処理なんかでよく出るので、もしかしてこういう
のがスマートにかける言語は便利なのかなと思う。オブジェクト指向に無理や
り当てはめると、コマンドパターン(実行のカプセル化)とコンポジットパター
ン(部分と全体の同一視)という事になるが haskell だと 3 行だ。-}