マージソート

ReasonMlによるマージソートの実装。
今まではよくわかんなかったけど、マージソートの意味がやっとわかった。

/* 目的：2つのリストを受け取ってくっつける */
/* merge: list(`a) => list(`a) => list(`a) */
/* 先頭の要素同士を比較して、小さい方を前につける */
let rec merge = (lst1, lst2) =>
  switch (lst1, lst2) {
  | ([], _) => lst2
  | (_, []) => lst1
  | ([h1, ...rest1], [h2, ...rest2]) =>
    h1 < h2 ? [h1, ...merge(rest1, lst2)] : [h2, ...merge(lst1, rest2)]
  };

  /* 目的：リストを受け取ってそれを半分ずつに分けたタプルを返す */
  /* halve: list(`a) => ( list(`a),list(`a) ) */
let rec halve = lst =>
  switch (lst) {
  | [] | [_] => (lst, [])
  | [h, ...rest] =>
    let (t1, t2) = halve(rest); 
    /* halve(rest)には要素が半分ずつ入っているとしてクロスに追加してく*/
    ([h, ...t2], t1);
  };

/* lstを分割してからマージする */
let rec merge_sort = lst =>
  switch (lst) {
  | [] | [_] => lst
  | _ =>
    let (l1, l2) = halve(lst);
    merge(merge_sort(l1), merge_sort(l2));
    /* ひたすらl1の方をたどっていくと要素が1個になるからそこまで行ったらmergeが始まる */
  };

まだfuncは未完成なのに、func(rest)が期待通りに動くとして...って考えるの面白いな。