Problem 12

今日は Problem 12をやってみた。

cf. Project Euler - Problem 12
via 自堕落系徒然日記 - Problem 12 三角数の約数

 import Data.List
 
 triangleNumbers :: [Integer]
 triangleNumbers = snd $ mapAccumL (\a x -> (a+x, a)) 1 [2..]
 
 divisors :: Integer -> [Integer]
 divisors n = concat [ z | x <- [1..floor (sqrt (fromInteger n))]
                     , let (y,r) = n `divMod` x
                     , r == 0
                     , let z = if x == y then [x] else [x,y]]
 
 euler012 :: Integer
 euler012 = f $ euler012'
   where
     euler012' = find (\x -> (length . divisors) x > 500) triangleNumbers
     f (Just x) = x
 
 main :: IO ()
 main = print euler012

約数を求める関数 divisors はこないだの nobsun さんのやつにちょっと手を入れた。
コンパイルしてから実行して数秒といったところ。もっと工夫できるのかも。

 ^o^ >ghc -o euler012 euler012.hs
 
 ^o^ >euler012
 76576500

unfold で1から10までのリスト

unfold を覚えたので，こないだの1から10までのリストを unfold を使ってやってみる。
と思ったら unfold が見つからないのでまずはその定義から。

 # let rec unfold f init =
     match f init with
       Some (a, b) -> a :: unfold f b
     | None        -> []
   ;;
 val unfold : ('a -> ('b * 'a) option) -> 'a -> 'b list = <fun>

で，リストを作る関数。

 # let list_of_int i j =
     unfold (fun x -> if x + 1 = j then None else Some (x, x+1)) i
   ;;
 val list_of_int : int -> int -> int list = <fun>
 # list_of_int 1 10;;
 - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Sys.argv

コマンドライン引数は Sys.argv に配列として格納される。インデックス0がプログラム名で，以下引数の数だけ続く。
インデックス0を出力する例：

 let () = print_endline Sys.argv.(0)

 ^o^ >ocamlc -o argv.exe argv.ml
 
 ^o^ >argv
 argv

インデックス1を出力する例：

 let () = print_endline Sys.argv.(1)

 ^o^ >ocamlc -o argv.exe argv.ml
 
 ^o^ >argv foo
 foo

引数を与えないとエラーになる。

 ^o^ >argv
 Fatal error: exception Invalid_argument("index out of bounds")

Array.iter

Array.iter は配列に対して 'a -> unit 型の関数を順に適用する関数。List.iter の配列版。これを使えばコマンドライン引数の数だけ繰り返せる。

 let () = Array.iter (fun s -> print_endline s) Sys.argv

 ^o^ >argv2 foo bar buz
 argv2
 foo
 bar
 buz

unfold

なるほど，unfold ってこういうふうに使えるのか。

cf. ZOETROPEの日記 - Foundations of F#を読む(3)

Haskellでやってみる。

 *Main> take 10 $ Data.List.unfoldr (\(n0,n1) -> Just (n0, (n1, n0+n1))) (1, 1)
 [1,1,2,3,5,8,13,21,34,55]
 

unfoldr に与える関数は b -> Maybe (a, b) 型で，Nothing が返ると終端になるらしい。だから上の例では無限リストになって，最初の10個だけ取り出している。

インターフェイスファイル

ソースファイル（=モジュール）と同名で拡張子が .mli のファイルを用意しておくことで，モジュールにシグネチャを与えることができる。
前にも例に挙げた Table モジュールを例にとると，
table.mli

 type ('a, 'b) t
 val empty : ('a, 'b) t
 val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
 val retrieve : 'a -> ('a, 'b) t -> 'b option
 val dump : ('a, 'b) t -> ('a * 'b) list

table.ml

 type ('a, 'b) t = Empty | Entry of 'a * 'b * ('a, 'b) t
 
 let empty = Empty
 
 let add key content table = Entry (key, content, table)
 
 let rec retrieve key = function
   Empty -> None
 | Entry (key', content, rest) -> 
   if key = key' then Some content else retrieve key rest
 
 let rec delete key = function
   Empty -> Empty
 | Entry (key', content, rest) ->
   if key = key' then delete key rest
                 else Entry (key', content, delete key rest)
 
 let rec dump = function
   Empty -> []
 | Entry (key, content, rest) ->
   (key, content) :: (dump (delete key rest))

こういう風にtable.mliとtable.mlを書く。これで

 module type TABLE =
   sig
     ...
   end
 
 module Table : TABLE =
   struct
     ...
   end

と書いたのと同じになる。

コンパイルするときは，インターフェイス(mli)ファイルを先にコンパイルする。手順としては

1. 各mliファイルを ocamlc でコンパイル（cmiファイルができる）
2. 各mlファイルを ocamlc -c でコンパイル（cmoファイルができる）
3. 全cmoファイルを ocamlc でリンク

となる。mlファイルよりもmliファイルを先にコンパイルしておくことに注意。でないとcmiファイルがないので，コンパイラが推論して勝手にcmiファイルを作り，意図したのと違うことになる。

コンパイラがcmiを探すディレクトリ

次のディレクトリを順に検索する。

1. ocamlc コマンドを起動したディレクトリ
2. ocamlc コマンドの -I オプションで指定したディレクトリ
3. 標準ライブラリのディレクトリ

Problem 2

今日は Problem 2。フィボナッチ数列のうち4,000,000以下で偶数のみを合計せよ，という問題。

cf. http://projecteuler.net/index.php?section=problems&id=2

Haskell ではやってる人がいるので，OCaml でやってみた。

 let fibs_under_n n =
   let rec fibs a b x =
     let c = a + b in
     if c > x then [] else c :: fibs b c x
   in
   1 :: 2 :: fibs 1 2 n
 
 
 let even n = if n mod 2 = 0 then true else false
 
 
 let sum lis = List.fold_left (+) 0 lis
 
 
 let euler002 n = sum (List.filter even (fibs_under_n n))
 
 
 let () = print_int (euler002 4000000)

even とか sum とかありそうな関数なんだけど，マニュアル見ても見つからなかったから自分で定義した。
コンパイルして実行：

 ^o^ >ocamlc -o euler002.exe euler002.ml
 
 ^o^ >euler002
 4613732

追記：

_さんに教えてもらった方法で。

 # let fibs_under_n2 n =
     let rec fibs a b x =
       let c = 4 * b + a in
       if c > x then [] else c :: fibs b c x
     in
     2 :: 8 :: fibs 2 8 n
   ;;
 # fibs_under_n2 5000;;
 - : int list = [2; 8; 34; 144; 610; 2584]

元の関数を使うと

 # List.filter even (fibs_under_n 5000);;
 - : int list = [2; 8; 34; 144; 610; 2584]

1から10までのリスト

って OCaml ではどう書けばいいんだろう。
Haskell では簡単に [1..10] と書ける。

 Prelude> [1..10]
 [1,2,3,4,5,6,7,8,9,10]

これなら10といわずいくつまででも簡単だ。だけど OCaml こういう書き方はできないらしい。

 # [1..10];;
 Characters 4-6:
   [1..10];;
       ^^
 Syntax error
 # [1;;10];;
 Characters 2-4:
   [1;;10];;
     ^^
 Syntax error

ともかく関数を書いてみた。

 # let rec list_of_int f t =
     if f > t then [] else f :: list_of_int (f+1) t
   ;;
 # list_of_int 1 10;;
 - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

分割コンパイル

ソースファイルは1つじゃなくてもいい。次の例では，fact関数を定義している fact.ml と，それを呼び出す main.ml に分けている。

fact.ml

 let rec fact n = if n = 0 then 1 else n * fact (n-1)

main.ml

 let () = print_int (Fact.fact 5)

OCamlではファイル＝モジュール（ストラクチャ）なので，fact.mlに定義されているfact関数は，Fact.fact として呼び出すか，open Fact してから使う。

さて，それぞれを（リンクせずに）コンパイルするには -c オプションを使う。

 ^o^ >ocamlc -c fact.ml
 
 ^o^ >ocamlc -c main.ml
 
 ^o^ >ls
 fact.cmi  fact.cmo  fact.ml  main.cmi  main.cmo  main.ml

.cmo と .cmi という2種類のファイルができている。 .cmo がオブジェクトファイルだ。
これらをリンクして実行形式のファイルを作るには，ソースファイルから直接コンパイルするときと同じようにすればいい。

 ^o^ >ocamlc -o fact5.exe fact.cmo main.cmo
 
 ^o^ >ls *.exe
 fact5.exe

単にリンクする.cmoファイルを並べるだけだけど，参照される側（ここではfact.cmo）を先に書くことに注意。逆にするとエラーになる。

 ^o^ >ocamlc -o fact5.exe main.cmo fact.cmo
 Error while linking main.cmo: Reference to undefined global `Fact'

さて，うまくいってるだろうか。

 ^o^ >fact5
 120