関数型プログラミング言語で文字列を再帰的に生成するときの高速化

# 何をしようとしているか

関数型プログラミング言語にて、データ列を持つモジュールを作り、そこに`toString`関数を作ろうとしています。
例えば、以下のようなシグネチャーを持つモジュールになります。

```sml:自作モジュールの例
signature MY_MODULE =
sig
  type t (* ただし、tはリストやツリーのような複数データを持つ *)
  val toString : t -> string
end
```

# よくやる畳み込みを使った解法とその問題点

このとき、自作モジュールのデータ列は、リストを使って実装するとします。
すると、以下のようにリストの畳み込み関数`foldr`と、文字列結合関数`^`を使って、`toString`書くと見通しが良さそうです。
リストの他にも、`array`や`vector`などでも同様です。

```sml:toString関数
type elem = ... (* 何らかの要素 *)
type t = elem list
fun toString datas =
    foldr (fn (e, acc) => (elemToString e) ^ acc) "" datas
```

例えば、`[A, B, C, D]`のようなデータがあれば、ざっくり言うと、以下のように展開されながら動きます。
`foldr`を使って実装したので、右から処理されていきます。

```:toString関数の展開例
   toString [A, B, C, D]
=> "A" ^ ("B" ^ ("C" ^ ("D" ^ "")))
=> "ABCD"
```

しかし、このコードはとても遅いです。
具体的には、入力のデータの長さnに対してO(n^2)時間かかります。

# なぜ畳み込みと文字列結合を組み合わせると遅いのか

SMLの文字列はイミュータブルであり、文字列の実体は`char vector`です。
そのため、文字列結合関数`^`は、新たな文字列を生成して返します。

このような前提の上で、`"X" ^ "Y"`のアルゴリズムは、例えば以下のようになります。[^1]

[^1]: [SML#コンパイラでの実装方法](https://github.com/smlsharp/smlsharp/blob/112eb8c41ba914cbd9d258a6bfd43bab9063015b/src/basis/main/String.sml#L72)

1. "X"の長さと"Y"の長さの合計の幅のバッファを確保する
2. バッファの前半に"X"をコピーする
3. バッファの後半に"Y"をコピーする
4. バッファを結合された文字列として返す

よって、`toString`関数の実行中に、途中生成される文字列は以下になります。

```:toString[A,B,C,D]が生成する文字列
""
"D"
"D"
"C"
"CD"
"B"
"BCD"
"A"
"ABCD"
```

はい。
明らかに無駄な文字列が大量に生成されています。
この関数は、入力のデータの長さnに対して、文字のコピー回数がO(n^2)起こるため、遅いです。

# 解法

`string`の実体は`char vector`のため、
徐々にデータが大きくなるようなループに使うと、
一時変数を作るコストがとても高いです。
よって、同じような場合でも、一時変数を作るコストが低いデータ構造を考えます。
これには、例えばリストがあげられます。

ここではリストを一時変数に使うことのコストの低さの説明のために、
`1 :: [2, 3]`のアルゴリズムを考えてみましょう。
ここで、`[2, 3]`はSMLでのリストを表します。

1. `1`を値に持つコンスセルを作る
2. `1`のコンスセルのポインタを、リスト`[2, 3]`の参照にする
3. `1`のコンスセルの参照を、新たなリストとして返す

このように、リストのcons（`::`）は、
新たなリストの生成時に元のリストを使いまわします。

それでは、一時変数にリストを使って先の`toString`関数を書き直してみます。
幸いにも、Standard ML Basis Libraryには、
`CharVector.fromList : char list -> string`という関数があります。
これを使い、`char list`型で構築して、最後に文字列に変換すれば良いです。

```sml:新たなtoString関数
fun toString datas =
    let val charList = foldr (fn (e, acc) => (elemToChar e) :: acc) nil datas
    in  CharVector.fromList charList end
```

この`toString`関数は、ざっくり言うと、以下のように展開されながら動きます。
なお、`#"A"`はSMLでのchar型のAを表します。

```:新たなtoString関数の展開例
   toString [A, B, C, D]
=> CharVector.fromList (#"A" :: #"B" :: #"C" :: "D" :: nil)
=> "ABCD"
```

このとき、生成されるデータは以下です。

```:新たなtoString[A,B,C,D]が生成するデータ
#"D"
#"C"
#"B"
#"A"
[#"A", #"B", #"C", #"D"]
```

今度は無駄なデータの生成がなくなりました。[^2]

[^2]: 正確には、リスト`[#"A", ... , #"D"]`の各要素も共有されており、新たな`#"A"`生成はされません。新たに生成されるデータは、このリストを表現するためのコンスセルになります。

# 実行時間の差の計測

実際のコンパイラで差が出るのかを確認します。
今回は、AtCoderなどでも利用されているMLtonコンパイラと、自分が好きなSML#コンパイラを使って、速度差が出るかを検証しました。
使ったテストコードを以下に示します。
このテストコードでは、長さ10,000のテストデータを作り、文字列へ変換してプリントします。
時間の計測にはtimeコマンドを使います。

## 問題のあるテストコード

```sml:test1.sml
structure S
          : sig
            datatype elem = A | B
            type t
            val toString : t -> string
          end
= struct
  datatype elem = A | B
  type t = elem list
  fun elemToString A = "A"
    | elemToString B = "B"
  fun toString datas = foldl (fn (e, acc) => (elemToString e) ^ acc) "" datas
end

fun main () =
    let
      (* n個のAを持つデータをプリントする *)
      val n = 10000
      val input : S.t = List.tabulate (n, fn _ => S.A)
      val format = S.toString input
    in
      print format
    end
val () = main ()
```

## 改善したテストコード

```sml:test2.sml
structure S
          : sig
            datatype elem = A | B
            type t
            val toString : t -> string
          end
= struct
  datatype elem = A | B
  type t = elem list
  (* char listにしてからCharVector.fromListでstringにする *)
  fun elemToChar A = #"A"
    | elemToChar B = #"B"
  fun toString datas =
      let val charList = foldr (fn (e, acc) => elemToChar e :: acc) nil datas
      in  CharVector.fromList charList end
end

fun main () =
    let
      (* n個のAを持つデータをプリントする *)
      val n = 10000
      val input : S.t = List.tabulate (n, fn _ => S.A)
      val format = S.toString input
    in
      print format
    end
val _ = main ()
```

## 計測結果

MLtonコンパイラでもSML#コンパイラでも如実に時間差が見られます。
特にMLtonコンパイラでは時間差が顕著となりました。

```shell-session:MLtonコンパイラによる実行時間の差
$ mlton
MLton 20130715 (built Fri Apr 28 06:06:34 UTC 2017 on lcy01-11)
$ make && time ./test1 > /dev/null && time ./test2 > /dev/null
mlton test1.sml
mlton test2.sml

real    0m0.123s
user    0m0.118s
sys     0m0.000s

real    0m0.002s
user    0m0.000s
sys     0m0.000s
```

```shell-session:SML#コンパイラによる実行時間の差
$ smlsharp
SML# 3.5.0 (2019-12-24 17:29:31 JST) for x86_64-pc-linux-gnu with LLVM 7.0.0
$ make && time ./test1 > /dev/null && time ./test2 > /dev/null
smlsharp -c -O2 test1.sml
smlsharp test1.smi -o test1
smlsharp -c -O2 test2.sml
smlsharp test2.smi -o test2

real    0m0.030s
user    0m0.013s
sys     0m0.026s

real    0m0.011s
user    0m0.014s
sys     0m0.000s
```

# 今回しなかった話

今回は例が簡単なデータ構造のため、一方向からの挿入さえ早ければよく、一時変数はリストで十分でした。
より複雑なデータ構造になり、複数の結合や削除を行う場合には、ツリー構造など適したものを選定する必要があります。

使う言語がBufferやSeqやArrayのようなものを持っており、そこから文字列を構築する方法があれば、より簡単に

# まとめ

- 文字列は素朴なデータではないので、再帰などのループで扱うときには注意が必要
    - `^`を`fold`などのループ内で使ってはいけない
    - コストの低い一時変数を選び、最後に結合する方法を使う

# 追記

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">MLtonとかSML#の標準ライブラリを眺めた感じだと、stringを作りたいときはリストに詰めておいてString.concatするのが速いっぽい（MLtonだとcocatは最初に必要なだけ領域を確保してunsafeCopyで埋めてくれる <a href="https://t.co/4b8QJPWclh">https://t.co/4b8QJPWclh</a></p>&mdash; でこれき (@dico_leque) <a href="https://twitter.com/dico_leque/status/1230059990120927232?ref_src=twsrc%5Etfw">February 19, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

`CharVector.fromList`や同じ動作をする`String.implode`以外にも便利な関数が。
SML#の実装も眺めて見ましたが、やはりMLtonと同じく先にバッファを確保するため効率がよいです。
`String.concat : string list -> string`も活用していきましょう。