はじめに
末尾呼び出しの再帰
列挙可能なもの（リスト、ビットストリング、文字列）を再帰で辿っていくとき、しばしば2つの懸念が生じます。
- 再帰的な関数呼び出しの連なりを保持するのに、どれだけのメモリが必要か
- どうすれば解答を効率よく組み立てられるか
こうした懸念に対処するために、_アキュムレーター_を使うことがあります。
アキュムレーターとは、データに加えて渡される変数のことです。関数の実行の現在の状態を、関数呼び出しから関数呼び出しへと受け渡し、_ベースケース_に到達するまで運びます。ベースケースでは、このアキュムレーターを使って、再帰的な関数呼び出しの最終的な値が返されます。
アキュムレーターは、関数の利用者ではなく、関数の作者が初期化するものです。これを実現するには、2つの関数を定義します。必要なデータだけを引数に取り、アキュムレーターを初期化する公開関数と、アキュムレーターも受け取る非公開関数です。Elixirでは、非公開関数の名前の先頭にdo_を付けるのが一般的なパターンです。
# Count the length of a list without an accumulator
def count([]), do: 0
def count([_head | tail]), do: 1 + count(tail)
# Count the length of a list with an accumulator
def count(list), do: do_count(list, 0)
defp do_count([], count), do: count
defp do_count([_head | tail], count), do: do_count(tail, count + 1)
アキュムレーターを使うことで、再帰関数を_末尾再帰_関数に変えられます。関数によって_最後_に実行されるのが自分自身への呼び出しであれば、その関数は末尾再帰です。
説明
DNA研究所では、研究データを圧縮して保存容量を節約するためのさまざまな方法を検討してきました。ある同僚が、DNAデータをバイナリ表現に変換することを提案します。
| 核酸 |
コード |
| 空白 |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
そうすれば必要なデータ保存コストを半分にできる可能性がありますが、その代わりに人が読むにはわかりにくくなります。そこで、どれだけ節約できるかを確かめるために、データをエンコード・デコードするモジュールを書くことにします。
1. 核酸をバイナリ値にエンコードする
encode_nucleotide/1を実装して、核酸のコードポイントを受け取り、エンコードされたコードの整数値を返すようにします。
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. バイナリ値を核酸にデコードする
decode_nucleotide/1を実装して、エンコードされたコードの整数値を受け取り、核酸のコードポイントを返すようにします。
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. DNAの文字リストをエンコードする
encode/1を実装して、核酸と空白を表す文字リストを受け取り、エンコードされたデータのビット列を返すようにします。
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. DNAのビット列をデコードする
decode/1を実装して、核酸と空白を表すビット列を受け取り、デコードしたデータを文字リストとして返すようにします。
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
学習演習
