関数型プログラミングで解く:初級問題-12問目- (約5分)

　関数型プログラミングによるリスト操作の練習問題の12問目です。問題は、OCaml公式ページのものを使いました。
　内容は、問題と答案です。答案の作成時間は、約5分でした。

問題12.

　ランレングス復号化を行う関数decodeを書け。
　ただし、ランレングス符号は、出現回数が1のときは要素のみで表され、2以上のときは出現回数と要素の組で表されるものとする。

※OCamlで解く場合は、独自型
type 'a rle = | One of 'a | Many of int * 'a
を使ってランレングス符号化されたリストを対象とします。
　例えば、符号化リストは、[Many (3, "a"); Many (2, "b"); One "c"]になります。これを["a"; "a"; "a"; "b"; "b"; "c"]に復号します。
　

答案

基本的な考え方

　関数型プログラミングによるリスト操作の基本的な流れは、以下の1から3になります。
　　1. 引数のリストをheadとtailに分離する
　　2. tailを引数として再帰呼び出すると共に、その返り値とheadを適当に組み合わせる
　　3. 以上を引数のリストが停止条件に達するまで繰り返す

本問の解き方

　符号化の逆処理を行うだけです。
　具体的には、引数のリストをheadとtailに分離します。
　headがOneのときは、保持されている要素と、tailを引数とした再帰呼び出しの返り値とを::演算子で結合します。
　headがManyのときは、別関数にてリストに展開し、そのリストと、tailを引数とした再帰呼び出しの返り値とを@演算子で結合します。

コード

type 'a rle =
| One of 'a
| Many of int*'a

let rec decode =
let rec expand = fun kurikaesi youso -> if kurikaesi < 1 then [] else youso::expand (kurikaesi-1) youso in
fun lisuto -> match lisuto with
| [] -> []
| head::tail -> match head with
| One hitotsu -> hitotsu::decode tail
| Many (kurikaesi, youso) -> expand kurikaesi youso@decode tail

---

感想

　今回の答案も直ぐに終わりました。
　12問目にして早くもネタ切れと言うか、水増し感がすごいです。
　あと87問あるはずなのですが、はたして大丈夫なのでしょうか？

　まさか、約1000体のモンスターが登場！と謳っておきながら、実際には20体x50色のカラーバリエーションみたいなことにならなければよいのですが…

　次回は、第13問です。