Problem 14

今日は 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

今日は Problem 8。

　cf. Project Euler – 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

今日は 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

今日は 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 を覚えたので，こないだの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ファイルを作り，意図したのと違うことになる。