関数型プログラミングの初級問題-28問目その2- 「長さの頻度による整列」

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

問題28.その2

　リストを要素とする入れ子リストについて、各要素を、その長さの出現頻度を基に並べ替える関数frequency_sortを書け。（昇順、降順の指定はありませんが、本記事では昇順としました）

※ 例えば、frequency_sort [["a"; "b"; "c"]; ["i"]; ["x"]]は、[["a"; "b"; "c"]; ["i"]; ["x"]]になります。

答案

基本的な考え方

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

本問の解き方

　前回と同様に、本答案ではソートアルゴリズムにクイックソートを用いました。

　ソート関数を用意すれば後は、要素（リスト）の長さの頻度に基づき昇順に並び替えるだけです。

　本答案では、効率を考えて長さの頻度を一度だけ求めることにしました。
　具体的には、所与のリストに対し
　1. 要素を、要素とその長さとからなるタプルに変換する
　2. 1のタプルを基に、長さとその頻度とからなるタプルを作成する
　3. 2のタプルにより、1のタプルを要素と長さの頻度とからなるタプルに変換する
　4. 頻度を基に3のタプルを並び替える
　5. 3のタプルを、要素に戻す
以上の工程を行っています。

コード

let rec sort comp =
 let rec divide pivot lst = match lst with [] -> (lst, [])
  | head::tail ->
 let (lower, upper) = divide pivot tail in
 if comp head pivot then (head::lower, upper) else (lower, head::upper ) in

 function [] -> []
  | head::tail ->
 let (lower, upper) = divide head tail in
 sort comp lower@(head::(sort comp upper))
----------------------------------------------------------------------------------
 let frequency_sort lst =
 let rec map f = function [] -> [] | head::tail -> f head::map f tail in

 let rec len = function [] -> 0 | head::tail -> 1+len tail in

 let rec freq_of key = function [] -> 0
  | (k, v)::tail -> if k = key then v else freq_of key tail in

 let rec update key value = function [] -> [(key, value)]
  | (k, v)::tail -> if k = key then (key, value)::tail else (k, v)::update key value tail in

 let rec freq_hash lst = function [] -> lst
  | (_, k)::tail -> freq_hash (update k ((freq_of k lst)+1) lst) tail in

 let tpl = map (fun x -> (x, len x)) lst in

 map (fun (a, _) -> a) (sort (fun (_, x) (_, y) -> x < y) (map (fun (x, y) -> (x, freq_of y (freq_hash [] tpl))) tpl))

　破線から上はクイックソート関数sortです。

感想

　今回の問題は面倒くさかったです。「本問の解き方」にも書いた通り、本答案の基になる発想は非常に単純なものです。
　それなのに、ハードウェアが足枷となり苦行を強いられることになりました。

　私の能力不足のせいでしょうか、OCamlはプログラムの最小構成単位が大きすぎるように思われます。

　本答案を一見すると、プログラムは小さな関数から構成されているように見えます。

　しかし、全ての関数は再帰呼び出しにより複雑に絡み合っており、実質的にはプログラムそのものが最小構成単位となっています。

　そのため、個々の関数ごとにデバックをするということが、まずできません。
　誤字脱字を除き、一部を修正などと言うことはありえず、修正とは即ちプログラムを一からの全部書き直すことになります。

　つまり、OCamlで楽しくプログラミングするには、本答案ぐらいの長さのコードならその全部を収納できるだけの脳内バッファが必要になるのです。

　と言うことは、関数型プログラミングを好きなあなたは、脳の容量が大きなエリートです、サンヘイリです。よかったですね！
　エジソンプラザに売ってないかな外部記憶ユニット…

　次回こそは、第29問です。暑さが和らいできたせいか、肉の写真がおいしそうに見えます。見出しにはやっぱり肉ですね。