takatoh's blog – Learning programming languages.
どう書く？org のこのお題，はじめはHaskellで書いた。
modular n l h = l + n `mod` (h - l + 1)
すでに投稿があったのでOCamlで書き直したんだけど，そのまま移植したんではうまくいかない。
# let modular n l h = l + n mod (h - l + 1);; val modular : int -> int -> int -> int = <fun> # modular (-1) 100 200;; - : int = 99
しばらく悩んだけど，要するに mod の引数に負数が現れた場合の振る舞いが Haskell と OCaml で違う。思わぬ盲点だよな。
Haskellの場合：
Prelude> mod (-1) 10 9 Prelude> mod 1 (-10) -9
OCamlの場合：
# (-1) mod 10;; - : int = -1 # 1 mod (-10);; - : int = 1
さて，算術的にはどっちが正しいんだろうか。
cf. どう書く？org – METHINKS IT IS A WEASEL
ずいぶん前に「ブラインドウォッチメイカー」を読んだ書いてみたもの。出遅れだし，お題ともちょっと違うので投稿せずにここにさらしておく。
IDEAL = "METHINKS IT IS LIKE A WEASEL" class Individual def initialize(phenotype) @phenotype = phenotype.upcase end attr_reader :phenotype def delivery next_phenotype = @phenotype.dup next_phenotype[rand(@phenotype.size)] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ".slice(ra nd(27), 1) Individual.new(next_phenotype) end def breed(n) next_generation = [] n.times do next_generation << delivery end next_generation end def to_s @phenotype end end class Nature def initialize(ideal) @ideal = ideal end def select(group) r = [] max = 0 group.each do |i| s = evaluate(i) if s > max max = s r = [i] elsif s == max r << i end end r[0] end def evaluate(ind) phenotype = ind.phenotype score = 0 0.upto(@ideal.size - 1) do |i| score += 1 if phenotype[i] == @ideal[i] end score end end if __FILE__ == $0 require 'optparse' def err_exit(msg) $stderr.print msg exit end options = {:number => 100} opts = OptionParser.new opts.banner = "Usage: ruby miilaw.rb [option] initial\n" opts.on_tail('-h', '--help', 'show this massage.') {puts opts; exit(0)} opts.on('-n', '--number=NUM', Integer, 'set number of children.') {|options[:numbe r]|} opts.parse! err_exit(opts.help) if ARGV.empty? len = IDEAL.size init = ARGV.shift.upcase if init.size < len init = "%-#{len}s" % init elsif init.size > len init = init[0,len] end individual = Individual.new(init) nature = Nature.new(IDEAL) genaration = 0 print "#{genaration} : #{individual}\n" while true do genaration += 1 next_gen = individual.breed(options[:number]) individual = nature.select(next_gen) print "#{genaration} : #{individual}\n" break if individual.phenotype == IDEAL end end
プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。
wc コマンドはなんか難しいのでこっちを先に。
UNIX の fold コマンドは，ファイル名の列を引数として，その内容を，長い行を複数の短い 行（デフォルトでは80文字）に分割しながら表示します。これを OCaml で実装し，実行可能 ファイルを作成しなさい。オプションとしては，行の長さを整数で指定する –width を実装 しなさい。
let version = "0.1" let filenames = ref [] let width = ref 80 let spec = [("--width", Arg.Int (fun n -> width := n), "Set line width"); ("--version", Arg.Unit (fun () -> Printf.printf "fold in OCaml ver.%s\n" version), "Display version")] let rec fold_line n str = let len = String.length str in if len > n then ( print_endline (String.sub str 0 n); fold_line n (String.sub str n (len - n))) else print_endline str let rec each_line ic = fold_line !width (input_line ic); each_line ic let fold_file filename = let infile = open_in filename in try each_line infile with End_of_file -> close_in infile let () = Arg.parse spec (fun s -> filenames := s :: !filenames) "Usage: fold [--width width] [--help] [--version] filename ..."; List.iter fold_file (List.rev !filenames)
^o^ >ocamlc -o fold.exe fold.ml
^o^ >fold --width 40 fold.ml
let version = "0.1"
let filenames = ref []
let width = ref 80
let spec = [("--width",
Arg.Int (fun n -> width :=
n),
"Set line width");
("--version",
Arg.Unit (fun () -> Printf
.printf "fold in OCaml ver.%s\n" version
),
"Display version")]
let rec fold_line n str =
let len = String.length str in
if len > n then
( print_endline (String.sub str 0 n)
;
（以下略）
プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~のp.215より。
UNIXの cat コマンドは，ファイル名の列を引数として，その内容を順次表示する（標準出力 に書き込む）ものです。これを OCaml で実装し，実行可能ファイルを作成しなさい。オプシ ョンに関しては少なくとも行番号を表示するための -n オプションを実装すること。
let version = "0.1" let display_linenum = ref false let filenames = ref [] let spec = [("-n", Arg.Set display_linenum, "Display line number."); ("-version", Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" version), "Display version.")] (* print each lines *) let rec output_file ic = print_endline (input_line ic); output_file ic (* print each lines with line number *) let rec output_file_n n ic = Printf.printf "%5d %s\n" n (input_line ic); output_file_n (n+1) ic let cat_file filename = let infile = open_in filename in try if !display_linenum then output_file_n 1 infile else output_file infile; with End_of_file -> close_in infile let () = Arg.parse spec (fun s -> filenames := s :: !filenames) "Usage: cat [-n] [-help] [-version] filename ..."; List.iter cat_file (List.rev !filenames)
^o^ >ocamlc -o cat.exe cat.ml
^o^ >cat -n cat.ml
1 let version = "0.1"
2
3 let display_linenum = ref false
4
5 let filenames = ref []
6
7 let spec = [("-n",
8 Arg.Set display_linenum,
9 "Display line number.");
10 ("-version",
11 Arg.Unit (fun () -> Printf.printf "cat in OCaml ver.%s\n" ve
sion),
12 "Display version.")]
13
（以下略）
cf. Project Euler – Problem 31
cf. Life Goes On – ３１問目
id:rst76さんのをちょっと改良して1pのコインがない場合にも対応できるようにしてみた。問題の解答には必要ないんだけど。
module Main (main) where
euler031 :: [Int] -> Int -> Int
euler031 (x:[]) m | m `mod` x == 0 = 1
| otherwise = 0
euler031 (x:xs) m = sum $ map (\n -> euler031 xs (m - x*n)) [0..(m `div` x)]
main :: IO ()
main = putStrLn $ show $ euler031 [200,100,50,20,10,5,2,1] 200
^o^ >runhaskell euler031.hs 73682
1pのコインがない場合：
*Main> euler031 [200,100,50,20,10,5,2] 200 1784
今日は Problem 14。
cf. Project Euler – Problem 14
コラッツ問題の数列を求めるのは以前にやったのを流用。あとは力任せに…
module Main (main) where
collatz :: Int -> [Int]
collatz 1 = 1 : []
collatz n | n `mod` 2 == 0 = n : collatz (n `div` 2)
| otherwise = n : collatz (n * 3 + 1)
euler014 :: Int -> [Int]
euler014 n = snd $ foldl g (0, []) $ map f [1..n]
where
f x = ((length.collatz) x, x)
g (x,zs) (l,z) | x < l = (l, z:[])
| x == l = (x, z:zs)
| otherwise = (x, zs)
main :: IO ()
main = mapM_ (putStrLn.show) $ euler014 1000000
やったらあえなくスタックオーバーフローに。ありゃ。
^o^ >runhaskell euler014.hs *** Exception: stack overflow
100,000までだったらうまくいったので間違ってはいないと思う。たぶん数列がすごく長くなる数があるんだろうな。再挑戦はまた今度。
あと，ついでに書いておくと，各数の数列にはおなじ部分列が何度も出現する。これを覚えておけば計算量を少なくできるんだけど，メモ化のやり方がわからない。
今日は Problem 8。
module Main (main) where
import Data.List
import Data.Char
euler008 :: [Char] -> Int
euler008 n = maximum $ map euler008' $ nums n
where
nums = filter (\x -> length x > 4) . map (take 5) . tails
euler008' = foldl1 (*) . map digitToInt
main :: IO ()
main = do n <- getContents >>= return . concat . lines
putStrLn $ show $ euler008 n
^o^ >runhaskell euler008.hs < euler008.txt 40824
今日は Problem 13 をやってみた。これは簡単。
cf. Project Euler – Problem 13
nums :: [Integer]
nums = [37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
...
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690]
euler013 :: String
euler013 = take 10 $ show $ sum nums
main :: IO ()
main = putStrLn euler013
^o^ >runhaskell euler013.hs 5537376230
数字をファイル（euler013.txt）から読み込むようにしてみた。
euler013 :: [Integer] -> String
euler013 = take 10 . show . sum
main :: IO ()
main = do nums <- getContents >>= return . lines
putStrLn $ euler013 $ map read nums
^o^ >runhaskell euler013a.hs < euler013.txt 5537376230
今日は Problem 12をやってみた。
cf. Project Euler – Problem 12
via 自堕落系徒然日記 – Problem 12 三角数の約数
module Main where 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 を使ってやってみる。
と思ったら 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]