「プログラミング in OCaml」をF#で(3)

F#1.9

今週も元気に進めたいと思います。
普段のエディタはKaoriYa様版GVIMを使用しており、F#のソース(*.fs)も色分けされているので微妙な違和(letとか明らかに重要なキーワードがハイライトされない、drop、maxとかはなぜかハイライトされる)を感じつつも、なんとなくそのまま使っていたのですが、そのシンタックスハイライトはForth用のものだったことが判明しました……。ちゃんと、filetype.vimでocaml用の設定が適用されるように変更したらだいぶ見やすくなった。色分けされているからといって安心してはいけない。
今週は5章、再帰的多相的データ構造：リスト、の練習問題を解きました。黄色チャートをといているときの無力感を思い出した……。まぁ、数学は高一で挫折しているので、微かな記憶との比較ですが、全体に数学の参考書っぽい。このペースだといつ終わるのか全く想像もつかない……。

  • P105の練習問題。5.1、5.2はすんなり解けた
  • 5.3。集合とか出てきた。が、ここもまぁ出来た感じ
  • 5.4。map (fun x -> f (f x)) l かな？
  • 5.5。これもすんなり
  • 5.6。これを解くのに2時間以上かかった……。
let rec qsort s = function
    []  -> s
  | [x] -> x :: s
  | pivot :: rest ->
    let rec partition left right = function
        [] -> qsort (pivot :: (qsort s right)) left 
      | y :: ys -> if pivot < y then partition left (y :: right) ys
                                else partition (y :: left) right ys
  in partition [] [] rest
  • しかもこれ全部書いたわけではなく、一部分手を入れただけ。今見ると、ちゃんとヒントあるし、そこまではまる問題でもない気がするんだけど、「なんで値を二つの配列に分けた段階なのに、整列済みリストを渡せるんだ？？」というところで詰まってしまった。@もでてこないし多分これであってるのでは、と思うが……。10回まわしてMeasure-Commandしたら、737msから708msで微妙に短くなってたし
  • 5.7。配列の章なので、[1..48612265]とかって配列を作ってから計算始めたら、それだけで800MBくらいメモリを使うし、そのうえ、めちゃめちゃ時間がかかる、ということに気付き、引数でチェック中の数字を渡すように変えたらすごく速くなった
  • 5.8。再帰してる部分が再帰関数の呼び出しのみになっていれば良い、のでこうだと思うんだが……。reverseは本文中で定義されてる関数。
let map2 f a = 
  let rec rec_map n = function
      [] -> n
    | x :: rest -> rec_map (f x :: n) rest in
  reverse (rec_map [] a)