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

F#1.9

こんにちは、嗣永モモコーラです。好きなコーラは特にありません……。今月も元気に進めていきたいと思います。
練習問題を解く前に、写経(本文中に記されたコードをただ打ち込む作業)をしています。通常、自分に厳しく接しようと改めて決意を固めた直後でさえ、写経が最後まで成功する可能性はとても低いのですが、この本の場合、練習問題中で写経の結果を要求されるので練習問題を全て解くと決めた以上、しっかり写経せざるを得ない。練習問題に必要な分だけ写経しようとすると、そのコードが必要かどうか判定するという余分なステップに労力を割かざるを得なくなり、また、その判断を頻繁に誤りストレスが発生するため、最初から全て写経するのが正しいのでは、という結論に達しました。そして、今回は写経が終わった段階で、150行程でした。練習問題をすべて解いた時点では、360行ほどです。

  • P113。この章で一番衝撃的だったのは、レコードのフィールド名は他のレコードのフィールド名とかぶってはいけない、ということです
  • P128。忠実に写経していると、addの名前がかぶる
  • P131。mapが未定義ですよエラー。OCamlだと普通にmapが定義されてるのか、以前の章で定義したmapを使っているのかよくわからない。とりあえず、List.mapに置き換えておく
  • 133。"let Br (a, left, Lf) = tree_of_rtree rtree"のところが、FS0062警告。()つけてね、みたいなメッセージが出るので、"let (Br (a, left, Lf)) = tree_of_rtree rtree"に変更したら大丈夫っぽい
  • P137。練習問題
  • 6.2 ほぼ確実に間違えている自信がある……。途中で場合分けしていて相当意気を阻喪した。本当にこうするしかないのだろうか……。
let overlap fw1 fw2 =
  (* SquareからRectangleに変換 *)
  let sr = function Square x -> Rectangle (x, x) | f -> f in
  (* 二点間の距離が、r以下かどうか *)
  let ci x1 y1 r x2 y2 =  float r >= Math.Sqrt ((x1 - x2) ** 2. + (y1 - y2) ** 2.) in
  match (fw1.loc_x, fw1.loc_y, sr fw1.body, fw2.loc_x, fw2.loc_y, sr fw2.body) with
    (* Square -> Rectangleに変換してるのでmatchしない *)
    (_, _, Square _, _, _, _) | (_, _, _, _, _, Square _) -> false
  | (x1, y1, Point, x2, y2, Point)
    -> x1 = x2 && y1 = y2
  | (x1, y1, Point, x2, y2, Circle r) | (x2, y2, Circle r, x1, y1, Point)
    -> ci x1 y1 r x2 y2
  | (x1, y1, Point, x2, y2, Rectangle (l1, l2)) | (x2, y2, Rectangle (l1, l2), x1, y1, Point)
    -> x1 <= x2 + float l2 && x1 >= x2 - float l2 && y1 <= y2 + float l1 && y1 >= y2 - float l1
  | (x1, y1, Circle r1, x2, y2, Circle r2)
    -> float (r1 + r2) >= Math.Sqrt ((x1 - x2) ** 2. + (y1 - y2) ** 2.)
  | (x1, y1, Circle r, x2, y2, Rectangle (l1, l2)) | (x2, y2, Rectangle (l1, l2), x1, y1, Circle r)
    -> x2 < x1 && x2 + float l2 > x1 && y2 - float r < y1 && y2 + float l1 + float r > y1 ||
       x2 - float r < x1 && x2 + float l2 + float r > x1 && y2 < y1 && y2 + float l1 > y1 ||
       ci x1 y1 r x2 y2 || ci x1 y1 r (x2 + float l2)  y2 ||
       ci x1 y1 r x2 (y2 + float l1) || ci x1 y1 r (x2 + float l2)  (y2 + float l1)
  | (x1, y1, Rectangle (l11, l12), x2, y2, Rectangle (l21, l22))
    -> x1 < x2 + float l22 && x1 + float l12 > x2 && y1 < y1 + float l21 && y1 + float l11 > y2
  • 6.6 Q 5.6で死ぬほど悩んだので楽勝。
  • 6.9 死んだ……。冗談抜きにこれだけで一週間ほど止まった。ちゃんと動いてはいるけど、もっと根本的に異なるいい書き方があるのでは？ という疑いはぬぐいきれない。詰まっていたのは、まずパターンマッチングで Open ot :: Close ct :: rest のような書き方が思いつかず、すべて、Open、Close、PCDATA、3ケースのパターンマッチングでやろうとしていたのが一点。というか、主にこれ。付随して、どうしても3ケースのパターンマッチングでやろうとすると現在処理中のタグについて、状態を覚えておかなければいけないので、それをどうするのか、とか。
let rec split_token n = function
    [] -> 0
  | Open t :: rest -> (split_token (n + 1) rest) + 1
  | Close t :: rest -> if n = 1 then 1 else (split_token (n - 1) rest) + 1
  | PCDATA p :: rest -> (split_token n rest) + 1

let rec xml_of_tokens = function
    Open ot :: Close ct :: rest -> XBr (ot, [XLf None])
  | Open ot :: PCDATA p :: rest -> XBr (ot, [XLf (Some p)])
  | Open t :: rest as arr -> let n = split_token 0 arr in XBr (t, taglist_of_tokens (take (n - 2) rest))
  | _ -> XLf None
and taglist_of_tokens a =
  let n = split_token 0 a in
    if n < 1 then [] else xml_of_tokens (take n a) :: taglist_of_tokens (drop n a)
  • take と drop は配列の章で作った関数。というか、標準にはないのだろうか……。
  • 6.10-11 やけに簡単だな、と思ったら続き物。分配則がわからなかったので調べると、分配法則 - Wikipediaのことっぽい。しかし、これをみても、問題文中の数式の意味が全くわからないので間違っているかもしれない。
  • 6.12 1, 2, 3, 4を格納する二分探索木のパターンをすべて列挙し、それぞれ空の木からどの順番で要素を add していけばよいか示せ、って問題。最初は手で二分探索木書いてたんだけど予想外に多そうだったので、PowerShell使ってすべての追加順組み合わせを列挙、全部探索木に変換して結果をまたPowerShellで集計してみたら、追加順の組み合わせが24パターン、結果の二分探索木は14パターンだった。葉より大きい値と小さい値が残った場合は、どちらを先に追加しても同じ二分探索木になるので、そこで重複するのかな
  • 6.13 でた！ フィボナッチ数……。この本を読み始めてから、数々のそれぞれ別なやり方で、フィボナッチ数を表現している。これも一問解くのに三十分以上かかった……。解けたとき、俺は天才だ！ と思ったが、しかし練習問題(答え一行)が解けただけなのでもちろん天才ではない……。練習問題を解くために本文を読み直すとやっと内容がわかる感じ
  • 6.14 3000番目の素数を計算するのに、どうすると速くなるか実際試す問題。2以降は速すぎてわからないので、各々十回ループをコンパイルして Measure-Command で計測した
    • ノーマル : 40秒ちょい
    • 1. 小さい数から割ってく : 6.4秒前後
    • 2. 割る数の上限を平方根以下に : 0.5秒前後
    • 3. 割る数として素数のみを試す : 9.4秒前後
    • 4. 2 + 3 : 2.1秒前後
  • 普通に考えると4が一番速いはずなので、これはソースが間違っているのではないか？ という気がする。しかし、どこが間違っているのかわからない……
(* 2 *)
let is_prime_2 x =
  let rec is n = (float n <= Math.Floor (Math.Sqrt (float x))) && ((x % n = 0) || is (n + 1))
  in not (is 2)
let rec prime_seq_2 x =
  if is_prime_2 (x + 1) then
    Cons(x + 1, prime_seq_2)
  else
    prime_seq_2 (x + 1)
(* 4 *)
let rec is_prime_4 x = function
    [] -> true
  | p :: rest -> if float p > Math.Floor (Math.Sqrt (float x)) then true else if x % p = 0 then false else is_prime_4 x rest
let rec prime_seq_4 primes x =
  if is_prime_4 (x + 1) primes then
    Cons(x + 1, prime_seq_4 (primes @ [(x + 1)]))
  else
    prime_seq_4 primes (x + 1)
  • もしソースが間違っていないのなら、どういうことになるか。(2)は(4)に比べて、素数じゃない数で割ってしまう点が不利。逆に、4は配列の操作でいろいろやっておりそこが遅い？
    • primes @ [(x + 1)] はぱっと見なんか遅そうだが、ここは3000回しか実行されないのであまり関係ないのではないか、という気がする。ここを、(x + 1) :: primesにすると、素数の配列が降順になってしまい、平方根とってのチェックが無意味になる。というか、平方根を毎回計算しているのはいいのだろうか……。まぁここはどっちも同じなのでいいけど。むしろ(2)が不利。素数を取り出すときにパターンマッチングで後ろの値を取り出せればいいのだが……
    • (2)の場合でも、2で割った段階で偶数は全滅、3、5辺りでも相当減るので、そのせいで(2)でもそれほど無駄な計算が発生しないので速い？ しかし、やはりソースがどこかおかしいのでは……
  • 6.15 パズル。6で相当悩んだ。F#は関数の定義自体と、関数の型の表記法が似てるようで似ていないのがどうなの、と思ったけど、よく考えたらすべての関数は引数を一つしかとれない、のがどうとかなんとかあったなーと思って、その辺を読んだのが遙か昔になってしまっているのが恐ろしい……