EoPLのLetlangをocamllex/menhir/duneで実装してみた
前回の記事の構成に従って、簡単な言語のインタプリタを実装してみた。
Essentials of Programming Languagesという本の最初に出てくるLETという言語で、機能としては整数値の引き算、0チェック、if式による分岐、let式による変数束縛。関数定義などはできない。
一例:
let x = 5 in let y = if zero?(x) then 1 else 2 in -(x, y)
これは3に評価される。
ディレクトリ構成は以下の通り:
├── bin │ ├── dune │ └── ex.ml #ライブラリを呼び出して実行するプログラム ├── dune-project └── src #ライブラリ部分 ├── dune ├── env.ml #変数環境の実装 ├── env.mli #変数環境のインタフェース ├── eval.ml #評価器の実装 ├── eval.mli #評価器のインタフェース ├── exp.mli #AST式の型定義 ├── lexer.mll #OCamllexを使ったLexer ├── parser.mly #Menhirを使ったParser ├── val.ml #評価結果である「値」の実装 └── val.mli #「値」のインタフェース
式
LETには文は存在せず、式しかない。のでASTもすべて式だけで表現できる。
その式の型はsrc/exp.mli
に定義されている:
type t = | Const of int #数値リテラル | Diff of t * t #二つの式の評価値の差 | ZeroP of t #式の評価値が0か | If of t * t * t #If式 | Var of string #変数 | Let of string * t * t #letによる変数束縛
Exp
モジュールはこの一つの型のためのみに存在するので、モジュール内で定義される型はOCamlの慣習に則ってtype t
である。Exp
モジュールの外からはExp.t
などとモジュールを指定して使う。
また、Exp
モジュールには型の定義しか存在しないので、インタフェースである.mli
だけが書かれている。
値
式を評価した結果の値を表現する型はsrc/val.mli
とsrc/val.ml
で定義されている。
val.mli
:
type t = | Num of int | Bool of bool val to_str: t -> string
val.ml
:
type t = | Num of int | Bool of bool let to_str = function | Num n -> string_of_int n | Bool b -> if b then "True" else "False"
型定義が.ml
と.mli
で重複するのはよくあることらしい。
LET言語では、式を評価した結果は数値か真偽値のみとなる。それを表現する型と、それを文字列に変換する関数。
Parser
src/parser.mly
:
%token <int> INT %token <string> ID %token DIFF %token LPAREN %token RPAREN %token COMMA %token ZERO %token IF %token THEN %token ELSE %token LET %token EQ %token IN %token EOF %start <Exp.t> f %% f : e = expr; EOF { e } expr : | n = INT { Exp.Const n } | DIFF; LPAREN; e1 = expr; COMMA; e2 = expr; RPAREN { Exp.Diff (e1, e2) } | ZERO; LPAREN; e = expr; RPAREN { Exp.ZeroP e } | IF; e1 = expr; THEN; e2 = expr; ELSE; e3 = expr { Exp.If (e1, e2, e3) } | v = ID { Exp.Var v } | LET; v = ID; EQ; e1 = expr; IN; e2 = expr { Exp.Let (v, e1, e2) }
これは普通のOCamlではなく、Menhirというパーサジェネレータに与えるOCamlチックな独自表記である。なのでファイル拡張子もmly
である。まずparser.mly
が普通のOCamlに変換されてから全体がコンパイルされる。(そういったbuild指定はduneファイルで行われる)
Lexerから受け取れるトークンをまず指定し、そのトークンの組み合わせのパターンマッチでExp.t
型の戻り値を返す(パターンマッチは当然再帰的)。
最終的に%start <Exp.t> f
とf : e = expr; EOF { e }
の部分で定義されているf
がパーサ関数となる。
Lexer
LexerはOcamllexを使う。Parserと同じく、OCamlではなく独自表記の.mll
拡張子。
src/lexer.mll
:
{ open Parser } let digit = ['0'-'9'] let number = '-'? digit digit* let whitespace = ['\t' ' ' '\n'] let char = ['a'-'z' 'A'-'Z'] let identifier = char (char|digit)* rule tokenize = parse | whitespace+ { tokenize lexbuf } | number as n { INT (int_of_string n ) } | "-" { DIFF } | "(" { LPAREN } | ")" { RPAREN } | "," { COMMA } | "zero?" { ZERO } | "if" { IF } | "then" { THEN } | "else" { ELSE } | "let" { LET } | "=" { EQ } | "in" { IN } | identifier { ID (Lexing.lexeme lexbuf) } | eof { EOF }
このソースがOcamllexに変換されてOCamlコードになると、rule tokenize = parse ...
のtokenize
がlexer関数名となる。(これもf
でもよかったかも・・・)
変数環境
LETにはlet式による変数束縛があるので、式の中で変数が出てきた場合、なんの値に束縛されているかを評価時に調べなくてはいけない。
そのため、式の評価には式そのものの他に変数環境が必要である。src/env.mli
とsrc/env.ml
に定義されている。
env.mli
:
type t val empty: t val find: t -> string -> Val.t option val extend: t -> string -> Val.t -> t
env.ml
:
type t = (string * Val.t) list let empty = [] let rec find env s = match env with | [] -> None | (s', v)::env' -> if s = s' then Some v else find env' s let extend env s v = (s, v)::env
変数環境の実装は単なる(変数名 * 値)
のタプルのリストで、初期値empty
と関数find
、extend
が定義されている。.mli
ではtype t
としか定義されていないのでEnv
モジュールの外では(string * Val.t) list
をVal.t
型として扱うことはできない(型の実装が隠蔽されている)。
評価器
LET言語の評価器はsrc/eval.mli
とsrc/eval.ml
で定義されている。
eval.mli
:
val f: Exp.t -> Val.t
eval.ml
:
let rec eval' env = function | Exp.Const n -> Val.Num n | Exp.Diff (e1, e2) -> (match eval' env e1, eval' env e2 with | Val.Num n, Val.Num m -> Val.Num (n - m) | _ -> failwith "Diffing non-numeric values") | Exp.ZeroP e -> (match eval' env e with | Val.Num n -> Val.Bool (n = 0) | _ -> failwith "Zero-checking non-numeric value") | Exp.If (e1, e2, e3) -> (match eval' env e1 with | Val.Bool b -> eval' env (if b then e2 else e3) | _ -> failwith "If-condition on non-boolean value") | Exp.Var s -> (match Env.find env s with | Some x -> x | None -> failwith "Variable not in environment") | Exp.Let (s1, e1, e2) -> let v1 = eval' env e1 in let env' = Env.extend env s1 v1 in eval' env' e2 let f = eval' Env.empty
Eval
モジュールは一つの関数f
のみを外部に提供する。内部実装としては、式とともに変数環境を引数にとる再帰関数eval'
をまず定義し、eval'
に空の変数環境を渡したものがf
になる。
Build指示
Buildの指示は前述の通りsrc/dune
に書いてある:
(menhir (modules parser)) (ocamllex lexer) (library (name letlang) (modules_without_implementation exp))
- Parserはmenhirで前処理すること
- Lexerはocamllexで前処理すること
- Expモジュールはインタフェース
.mli
のみであること - ライブラリ全体の名前は
Letlang
であること
が指定されている。
実行プログラム
bin/ex.ml
:
open Letlang let _ = Lexing.from_channel stdin |> Parser.f Lexer.tokenize |> Eval.f |> Val.to_str |> print_endline
stdinをパーサに渡し(パーサはParser.fにLexer.tokenizeを第一引数として渡したもの)、評価し、結果を文字列化して出力する。
これのbuild指示はbin/dune
にある:
(executable (name ex) (libraries letlang))
それ以外
ついでにsrc
とbin
の上のディレクトリにdune-project
というファイルがある:
(lang dune 1.0) (using menhir 1.0)
duneとmenhirのバージョン指定。
実行
実行するにはdune exec
というコマンドを使う。
たとえば
> echo "let x = 5 in -(x, 1)" | dune exec bin/ex.bc 4
あるいは記事冒頭にあるサンプルプログラムのtest.txt
ファイルを作って:
let x = 5 in let y = if zero?(x) then 1 else 2 in -(x, y)
cat
で流し込む:
> cat test.txt | dune exec bin/ex.bc 3
成功。
OCamlで言語処理系覚え書き ocamllex/menhirパーサをduneでビルドする
OCamlでocamllexとmenhirを使ったパーサを書き、duneでビルドする場合の構成を調べていて、ようやく少しわかってきたので備忘録的に書き留めておく。
例として整数のたし算をパースして評価する非常に簡単な計算プログラムを実装する。
ディレクトリ構成
. ├── dune-project ├── src │ ├── ast.ml │ ├── parser.mly │ ├── lexer.mll │ └── dune └── bin ├── ex.ml └── dune
トップレベル
dune-project
が以下のように定義されている:
(lang dune 1.0) (using menhir 1.0)
src
ディレクトリ内
src/ast.ml
でAST定義:
type expr = | Int of int | Plus of expr * expr
そのAST定義を使ってMenhir Parserをsrc/parser.mly
で定義:
%{ open Ast %} %token LPAREN %token RPAREN %token EOF %token <int> INT %token PLUS %left PLUS %start <Ast.expr> prog %% prog: | e = expr EOF { e } expr: | LPAREN; e = expr; RPAREN { e } | i = INT { Int i } | e1 = expr; PLUS; e2 = expr { Plus (e1, e2) }
parserで定義されているtokenを出力するsrc/lexer.mll
:
{ open Parser } let digit = ['0'-'9'] let number = '-'? digit digit* let whitespace = ['\t' ' ' '\n'] rule tokenize = parse | whitespace+ { tokenize lexbuf } | "(" { LPAREN } | ")" { RPAREN } | "+" { PLUS } | number as n { INT (int_of_string n ) } | eof { EOF }
src
ディレクトリにあるast.ml
、parser.mly
、lexer.mll
をadder
というライブラリとしてビルドするためのsrc/dune
ファイル:
(menhir (modules parser)) (ocamllex lexer) (library (name adder))
bin
ディレクトリ内
adder
ライブラリを使うmain関数的なものが定義されているex.ml
:
open Adder let rec pprint = function | Ast.Int n -> string_of_int n | Ast.Plus (n, m) -> Printf.sprintf "(Plus %s %s)" (pprint n) (pprint m) let rec eval = function | Ast.Int n -> n | Ast.Plus (n, m) -> eval n + eval m let _ = let lexbuf = Lexing.from_channel stdin in let expr = Parser.prog Lexer.tokenize lexbuf in Printf.printf "%s = %d\n" (pprint expr) (eval expr)
bin/dune
ファイル:
(executable (name ex) (libraries adder))
実行
shellで:
> echo '1+2+(3+4)+5' | dune exec bin/ex.bc (Add (Add (Add 1 2) (Add 3 4)) 5) = 15
参考資料
lambda関数だけのPython世界で四則演算
お察しかもしれないがラムダ計算についての話である。
最近あったPyConで気になるチュートリアルがあった:
このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、
Pythonのlambdaキーワードで作る無名関数だけで、ラムダ計算の世界をのぞいてみよう
という趣旨。
かなり面白かったので、備忘録的にメモってみる&内容を少しだけ発展させて自然数のわり算まで実装してみる。
ルール
Pythonのlambda関数しかない世界。
なのでできるのはlambda関数の作成と呼び出しのみ。
さらにいうと単一引数のみ。
例えばこんな感じ:
X = lambda x: x Y = lambda y: y(X) Z = lambda x: lambda y: lambda z: z(x)(y)
Z関数ではcurryingにより、単一引数ながらも複数の値を入力として受け取る関数が定義できることがわかる。記述がややこしくなるのを避けるため、今後このようなcurryingされている関数のことを「ある関数がn個の引数をとる」「ある関数の第一引数、第二引数」などという表現をする。
便宜上トップレベルでは変数への代入をしているが、あくまで名前付けのためのみ許される。
言い換えると、変数を値の式ですべて書き直すことが可能である必要がある。
このルールでどうすれば計算を表現することができるか。
真偽値
まずはTRUE/FALSE:
TRUE = lambda x: lambda y: x FALSE = lambda x: lambda y: y
この世界では
- 「真」は「引数xとyを順番に受け取り、xを返す関数」
- 「偽」は「引数xとyを順番に受け取り、yを返す関数」
に対応づけられる。
そうするとNOT, AND, ORも以下のように定義できる:
NOT = lambda x: x(FALSE)(TRUE) AND = lambda x: lambda y: x(y)(x) OR = lambda x: lambda y: x(x)(y)
データ構造
複数のデータをひとつのオブジェクトとしてまとめて、単一引数に渡せるようにしたい。
LispでもおなじみのCONSセルの出番である:
CONS = lambda x: lambda y: lambda f: f(x)(y) CAR = lambda x: x(TRUE) CDR = lambda x: x(FALSE)
CONSは引数二つをとって、ある関数を返す。その関数にTRUEを与えるとCONSの第一引数、FALSEを与えると第二引数を返す。
CARとCDRはその関数を受け取ってTRUE/FALSEを与えるだけ。
数字
ここから数字と対応づけられる関数が何か、を考えていく。話を簡単にするために0からはじまる自然数のみ。
考えていく、と言ったがそれは嘘で、昔から知られているチャーチ数を使うだけ。
ZERO = lambda f: lambda x: x ONE = lambda f: lambda x: f(x) TWO = lambda f: lambda x: f(f(x))
数字はすべて二つの引数をとる関数で、「第二引数に第一引数をn回適用した結果を返す関数」を自然数nに対応させる。
任意の自然数を作れるように、「ある数より1大きい数を作る関数」SUCCを定義する:
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))
fが適用される回数が一回上がる。
SUCCを使えばたし算ができる:
ADD = lambda n: lambda m: n(SUCC)(m)
この関数は実は少し単純化できる:
ADD = lambda n: n(SUCC)
というのも、この世界だとすべてのものが関数なので、以下の等式が(ほとんどの場合)あてはまる:
lambda x: X(x)
=X
(先行評価・遅延評価の関連であてはまらないケースについては後述する)
なので
lambda n: lambda m: n(SUCC)(m)
=lambda n: n(SUCC)
となる。
たし算を使ってかけ算を定義:
MUL = lambda n: lambda m: n(ADD(m))(ZERO)
次にひき算を定義したいのだが、そのためには「一個前の数」を返すPRED関数が必要になる。
ここで以前定義したCONSを使う:
PRED = ( lambda n: CDR (n(lambda x: CONS(SUCC(CAR(x)))(CAR(x))) (CONS(ZERO)(ZERO))))
(横幅が足りなくなってきたので()内では複数行に分割できるというPython構文を利用している)
この定義は:
自然数n-1は
(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), ...
という無限列のn番目のCONSセルのCDR
という考察がベースとなっている。ちなみにこの定義だとZEROのPREDはZEROのままであることに注意。
PREDがあればSUBは簡単:
SUB = lambda n: lambda m: m(PRED)(n)
さらに比較用の関数:
ISZERO = lambda n: n(lambda _: FALSE)(TRUE) LE = lambda n: lambda m: ISZERO(SUB(n)(m)) EQ = lambda n: lambda m: AND(LE(n)(m))(LE(m)(n)) LT = lambda n: lambda m: AND(LE(n)(m))(NOT(LE(m)(n)))
さて、残る四則演算はわり算のみとなったのだが・・・
考え方としては
nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数
を返す関数を作りたい。この「繰り返し」を実装するために再帰ができるようにしたい。
再帰
まずはルール違反な例を挙げる:
BADFACT1 = lambda n: ISZERO(n)(ONE)(MUL(n)(BADFACT1(PRED(n)))) BADFACT2 = lambda n: ISZERO(n)(ONE)(lambda _: MUL(n)(BADFACT2(PRED(n)))(_))
BADFACT1はそもそも無限再帰になってしまいうまくいかない。ISZERO(n)(m)(p)
でIF分岐しているのだが、nもmもpもすべて評価してからnの値によってmかpかを選ぶ、という評価戦略になっているのが理由だ。
無限再帰を避けるため、BADFACT2では
lambda x: X(x)
=X
があてはまらないケースを利用している。関数の中に入れることでXの評価を遅延させることができる。最終的にすべて評価されれば値は同じになるはずだが、これだと無限再帰を起こさない。
しかし、このようにBADFACT2の定義の中でBADFACT2という名前を利用するのはルール違反である。
この定義を「名前なしで」書こうとするとやはり無限ループが起きて、式の長さが無限になってしまう。
Y = ( lambda f: (lambda x: lambda _: f(x(x))(_)) (lambda x: lambda _: f(x(x))(_)))
Yコンビネータに関しては解説できるほど理解が進んでいないのであらかた割愛するが、一点だけ。
普通はYコンビネータといえばlambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
のような形で出てくるのだが、やはり遅延評価して無限再帰を回避するために追加でlambda _: ...
というステップを追加している。
Yコンビネータを使えばFactorialやFibonacciがルール内で以下のように書ける:
FACT = ( Y (lambda f: lambda n: ISZERO(n) (ONE) (lambda _: MUL(n)(f(PRED(n)))(_)))) FIB = ( Y (lambda f: lambda n: LE(n)(TWO) (ONE) (lambda _: ADD (f(PRED(n))) (f(PRED(PRED(n))))(_))))
わり算
これでピースは全て揃った。あとは書くだけ:
DIV = ( lambda n: lambda m: Y (lambda f: lambda x: LT(CAR(x))(m) (CDR(x)) (lambda _: f(CONS(SUB(CAR(x))(m))(SUCC(CDR(x))))(_))) (CONS(n)(ZERO)))
考え方としては前述の通り
nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数
を返す関数。初期値がnとZEROのCONSセル(p, k)に対して再帰的に(p-m, k+1)に変えていき 、pがm未満になった時点でkを返す。
普通のPythonで書くならこんなロジック:
def divide(n, m): def f(p, k): return k if p < m else f(p-m, k+1) return f(n, 0)
使ってみる
まずは他にいくつか数字を定義しておく:
THREE = ADD(ONE)(TWO) FIVE = ADD(TWO)(THREE) TEN = ADD(FIVE)(FIVE) HUNDRED = MUL(TEN)(TEN)
この世界の数字に対応するPythonの数字をプリントする関数を定義:
def show(n): print(n(lambda x: x+1)(0))
この関数はラムダ計算世界の結果を、我々が理解できるように出力するためだけに使う(演算には使われていない)。のでルール外の存在。
この関数を使ってFACT, FIB, DIVを使った計算結果を出力してみる:
>>> show(FACT(FIVE)) 120 >>> show(FIB(TEN)) 55 >>> show(DIV(HUNDRED)(THREE)) 33
成功。
AtCoder Beginners SelectionをOCamlで(後編)
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
今回は最後の2問、白昼夢 / DaydreamとTravellingの解法とOCamlを使った所感。
ABC049C - 白昼夢 / Daydream
ある文字列が、"dream", "erase", "dreamer", "eraser"の四語のどれかを繰り返すことで作られているかを判定する
open Batteries let s = read_line () |> String.explode |> List.rev let rec f = function | [] -> true | 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs | 'r' :: 'e' :: 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs | _ -> false let ans = if f s then "YES" else "NO" let () = print_endline ans
"dream"と"dreamer"、"erase" "eraser"と先頭から読んでいくと候補が重複してしまう。バックトラックするようなロジックも考えられるが、この四語だったら一番楽なのは後ろからパースすることだろう(後ろから見ると重複する候補はないため)。
OCamlのリストと文字がパターンマッチ可能なことを利用した再帰関数でパースできる。
ABC086C - Traveling
格子上の点を特定のスケジュールで移動できるかどうかを判定する。
open Batteries let parse_triplet s = Scanf.sscanf s "%d %d %d" (fun a b c -> (a,b,c)) let diff ((_,_,_), (a,b,c)) (x,y,z) = ((x-a,y-b,z-c), (x,y,z)) let pred (a, b, c) = let d = abs b + abs c in a >= d && a mod 2 = d mod 2 let n = read_int () let x = Enum.init n (fun _ -> read_line ()) |> Enum.map parse_triplet |> Enum.scanl diff ((0,0,0), (0,0,0)) |> Enum.map fst |> Enum.for_all pred let ans = if x then "Yes" else "No" let () = print_endline ans
スケジュールは時間順に与えられるので、隣接するスケジュールの差だけを調べていけばいい。
スケジュールの差が可能かどうかの判定は以下の二点:
- 移動量は時間内に収まるか
- 移動量と時間の偶奇が一致するか(余った時間は2つずつ無駄に消費することが可能なため)
Enum.scanl
はfold
に似ているけど、fold
でいうところの中間結果をすべて要素として持つ遅延リスト。
Enum.scanl f x (a1; a2; a3)
は(x; f x a1; f (f x a1) a2; f (f (f x a1) a2) a3)
となる(ここでは(x;y;z)
はx``y``z
を要素に持つ遅延リストだとする)。
これを使って「差額の遅延リスト」を作成して、すべてが上記の二点を満たしているかをEnum.for_all
で判定している。
OCamlをAtCoderで使ってみて
OCamlは去年の10月くらいからかれこれ四ヶ月ほど(業務外で・・・)使っていて少しは慣れてきたと思うのだが、主に言語実装系のことばかりしていたので競技プログラミングは勝手がけっこう違った。言語処理系の実装だとASTなどの処理のために「再帰関数でパターンマッチ」が多くなるのだが、AtCoder Beginners Selectionではあまり木構造をどうこうすることもなく、直線的かつフラットにデータ変換のロジックを書いていくことが多かった。
OCamlは|>
演算子やEnum
の各関数などで十分そのような書き方もできる言語だとわかったのは嬉しい。
個人的にはOCamlの命令型でも記述できるところはすごく便利だと思っているのだが、振り返ると一度もref
、Array
、Hashtbl
などの破壊的代入が可能なデータやfor
ループなどの命令的な構文などを使う必要がなかった。Dynamic Programmingなどでは絶対必要になってくると思うが、Batteriesのモジュールや関数、とくにEnum
関連を使いこなせば関数型プログラミングのスタイルだけでもかなりの処理を(しかもそれなりに宣言的に)記述できることも実感できた。個人的にはこれはPythonなどでも感じていたことだが・・・
Pythonとは実行速度が比較にならないほど早い、という点もAtCoder向きだ。
比較のためにOtoshidamaをPythonとOCamlで同じ(意図的にアルゴリズムの良さよりも記述の明快さを重視した)ロジックで書いてみた:
Pythonの内包表記的なgenerator expressionは記法としてはやはりすごく好きだ・・・ がほぼ完全に一致するロジックのコードで、Pythonが719 ms、OCamlが58 msで十倍以上の差がある。コードが煩雑になるような定数倍最適化を行わなくてはならない、というケースが減りそうでとても魅力的。
というわけでこれからもちょくちょくOCamlでAtCoderの過去問を解いていこうと思う。Array
やHashtbl
などを使ってDPやUnion Find Treeなどの問題を解いていって、それらの記法にも馴染んできた時点で実際のコンテストにもまた参加したい。まずは最近開催されたEDPCの問題かな・・・
AtCoder Beginners SelectionをOCamlで(中編)
OCamlでAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた
(この記事はSome Sums, Card Game for Two, Kagamimochi, Otoshidamaの4問について)
ABC083B - Some Sums
0~Nまでの数で、各桁の合計がa以上b以下になるものを合計する。
open Batteries let add_digits x = string_of_int x |> String.explode |> List.map (fun x -> int_of_char x - 48) |> List.fold_left (+) 0 let n, a, b = Scanf.scanf "%d %d %d" (fun n a b -> n, a, b) let ans = Enum.range 1 ~until:n |> Enum.filter (fun x -> let y = add_digits x in a <= y && y <= b) |> Enum.reduce (+) |> string_of_int let () = print_endline ans
問題をそのままコード化できたように思うがどうだろうか。
ABC088B - Card Game for Two
交互に数字の書いてあるカードをとっていくゲームで、お互いに最善を尽くした場合の点差を計算する。
open Batteries let rec diff_two n = function | [] -> n | [x] -> n + x | x :: y :: zs -> diff_two (n + x - y) zs;; let _ = read_line () let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> diff_two 0 |> string_of_int let () = print_endline ans
降順にソートされた数字の奇数番と偶数番の和の差。
List.sort (flip compare)
で逆順ソートになるのは思いつけてよかった。(fun a b -> - (compare a b)
とか書くのかなー、いやだなーと思っていたので・・・
逆に再帰でdiff_two
を書いているのは少し不満がある。なんらかの高階関数を組み合わせて表現できないものか・・・
今ふとこんな解も思いついたが
let ans = read_line () |> String.split_on_char ' ' |> List.map int_of_string |> List.sort (flip compare) |> List.fold_left (fun (n, m) x -> (n + (m * x), - m)) (0, 1) |> fst |> string_of_int
これはちょっと問題固有の部分に引きずられすぎているだろうか?あまりテクニックとして汎用性がなさそうにも見える。
ABC085B - Kagami Mochi
いくつかの直径の餅を「下にある餅は必ず上にある餅よりも直径が大きい」という制約でいくつ積み重ねることができるか。
open Batteries module S = Set.Make(Int) let n = read_int () let ans = List.init n (fun _ -> read_int ()) |> S.of_list |> S.cardinal |> string_of_int let () = print_endline ans
ユニークな直径の数を求めればいいのでSet
を使う。OCamlだとSet
はFunctor(モジュールをうけとりモジュールを返す「関数」)なので、Batteriesで定義されているInt
モジュールを渡すことで整数を要素にとる集合を表すことができる。
あとはList.init n (fun _ -> read_int ())
でn
行に渡る整数の入力値をリスト化し、S.of_list
で集合化し、S.cardinal
で要素数を数えてstring_of_int
で文字列化する。
ABC085C - Otoshidama
10000円札、5000円札、1000円札を合計N枚使ってY円を作ることができるか。
open Batteries open Enum.Infix let n, y = Scanf.scanf "%d %d" (fun n y -> (n, y)) let f i = let z = (y - 10000*i - 1000*(n-i)) / 4000 in (i, z, n - i - z) let p (a, b, c) = y = a * 10000 + b * 5000 + c * 1000 && 0 <= a && 0 <= b && 0 <= c let xs = Enum.map f (0--(y / 10000)) let ans = let a, b, c = try Enum.find p xs with Not_found -> (-1, -1, -1) in Printf.sprintf "%d %d %d" a b c let () = print_endline ans
「5000円札、1000円札を合計N枚使ってY円を作る」というのはつるかめ算的なサムシングなので、それをまずf
関数で表す。
ただし、5000円札A枚、1000円札B枚のAとBが整数でなかったり片方が負数だったりする場合を排除しないといけないので、そのためのp
述語を定義する。
あとはEnum.Infix
に定義された--
演算子でrange
を手軽に表したものにf
でmap
し、`try
+Enum.find p
で合致する要素を探し、見つからなかった場合はNot_found
をキャッチして(-1, -1, -1)
を返している。Enum.Infix
は継続して使うか少し悩むところだ・・・ (関数でも同じことができるのと、ぱっと見で理解しやすいか微妙な気がするため)
あと今回も入力が一行のみなのでScanf.scanf
を使っている。
やはり長くなってきたので後編に続く。
AtCoder Beginners SelectionをOCamlで(前編)
以前DP問題を解いてみたこともあったように、親和性は高いように思う。
具体的には、関数型・命令型どちらでも表現力が高く、実行過程の予想がつきやすく、コンパイルされるので早い、という利点がある。いろんな方面から嫌がられそうな表現だが、「早いPythonとして使えそう」というのが個人的な思惑。
とはいってもいろいろと文法もライブラリも流儀も違うので、練習のためにまずAtCoder Beginners Selectionをやってみた
PracticeA - はじめてのあっとこーだー(Welcome to AtCoder)
まずはAtCoderでの入出力を試す練習問題。
OCamlだと入出力関数にread_int
, read_line
, Scanf
, print_int
, read_endline
, Printf
などいろいろあってどれをどう使うのがいいか、ちょっと考えどころかもしれない。
とりあえず現在の自分のスタイルだとこんな感じ:
let n = read_int () let a, b = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> (a, b)) let s = read_line () let ans = Printf.sprintf "%d %s" (n + a + b) s let () = print_endline ans
Scanf.scanf
という直接stdinから文字列をとってパースする関数もあるのだが、入力が複数行に渡る場合よく問題が起きるので使わないことにしている。多分改行のパースなどでエッジケースがあったりするのではないかと思うのだが・・・
なので単一の整数を取る場合はread_int
、複数の場合はいったんread_line
とった文字列をScanf.sscanf
でパースするようにする。
Scanf.sscanf
は第三引数に関数を取り、パースした値をさらにどのようにでも加工できる。が、それはできるだけ使わないほうが読みやすいと思う。単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。
あと最終的に答えをlet () = ...
で出力するのだが、そこはほぼ決め打ちでlet () = print_endline ans
にして、その上の方でans
の文字列を作成するようにしている。print_int
なども使いたくなるが、それだと改行が入らないのでどうせもう一手間必要になる。それよりは文字列を作成して、それを最後の行でprint_endline
で出力することに決めた方が考えることを減らせていい。
ABC086A - Product
一行の入力に含まれている二つの整数の積の偶奇を判定する。
let x = Scanf.scanf "%d %d" (fun a b -> a * b) let ans = if x mod 2 = 0 then "Even" else "Odd" let () = print_endline ans
はやくも自分の言った
単一の整数を取る場合は
read_int
、複数の場合はいったんread_line
とった文字列をScanf.sscanf
でパースするようにする。(
Scanf.sscanf
からは)単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。
という考えを破っているが、まあこれくらいはいいのではないか。受け取る入力が一行だけで、それに対する処理も一目でなにが起きているかわかるし。
ABC081A - Placing Marbles
三つの文字が1の値をとる回数を数える。
open Batteries let ans = read_line () |> String.explode |> List.map (fun c -> int_of_char c - 48) |> List.fold_left (+) 0 |> string_of_int let () = print_endline ans
文字が取り得る値が0か1なので各桁を足し合わせればいい。
- 入力を受け取り
- 文字列を文字のリストに変換し
- 各文字を数値に変換し
- 足し合わせ
- 数字を文字列化する
あとは今までどおりその文字列を出力するだけ。
OCamlの標準ライブラリ拡張のひとつであるBatteriesがAtCoderでも使えるので、open Batteries
してString.explode
とint_of_char
を利用する。あと|>
パイプ演算子でできるだけ直線的に計算の流れを表す。
ABC081B - Shift only
複数の数字を2で割り切りつづけられる回数を数える。
まずは再帰を使った解:
open Batteries let _ = read_line () let xs = read_line () |> String.split_on_char ' ' |> List.map int_of_string let rec f n = let m = Int.pow 2 (n+1) in if List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n let ans = string_of_int @@ f 0 let () = print_endline ans
入力を変更はせず、2 ** (n+1)ですべての数が割り切れたら次のnを調べる、という意味の
List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n
がキモになっている。
つぎに再帰ではなく無限の遅延リストを使った解:
open Batteries let _ = read_line () let xs = read_line () |> String.split_on_char ' ' |> List.map int_of_string let p n = let m = Int.pow 2 (n+1) in not (List.for_all (fun x -> x mod m = 0) xs) let ans = Enum.range 0 |> Enum.find p |> string_of_int let () = print_endline ans
Batteriesで定義されている遅延リストEnum
を利用している。
Enum.range 0
で0からはじまる無限の数列を作るEnum.find
でその無限リストからnot (List.for_all (fun x -> x mod m = 0) xs)
があてはまる最初の数を見つける
この問題だとまだそこまで有り難みがないが、無限リストとそれに対する処理、無限リストから他のデータ構造への変換などを多く定義しているEnum
モジュールはかなり便利。Pythonでいうところのgeneratorとitertoolsにあたる概念である。
ABC087B - Coins
500円A枚、100円B枚、50円C枚から合計X円になる組み合わせ方は何通りあるか。
open Batteries let a = read_int () let b = read_int () let c = read_int () let x = read_int () let p n = n mod 50 = 0 && n / 50 <= c let count n = Enum.init (b+1) (fun i -> n - i*100) |> Enum.take_while ((<=) 0) |> Enum.filter p |> Enum.hard_count let ans = Enum.init (a+1) (fun i -> x - i*500) |> Enum.take_while ((<=) 0) |> Enum.map count |> Enum.reduce (+) |> string_of_int let () = print_endline ans
- 「50円C枚からX円を作ることができるか」を判定する関数
p
を作成 p
を使って「100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算する関数count
を作成count
を使って「500円A枚、100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算
この解ではEnum
の各種関数を多用している。
Enum.init n f
で(f 0, f 1, ... f (n-1))
という遅延リストを作成Enum.take_while p xs
で遅延リストxs
の先頭から述語p
を満さない初めの要素までを含む新しい遅延リストを返す。(述語p
を満さない要素は含まれない)Enum.filter p xs
で遅延リストxs
の述語p
を満たす全ての要素を含む新しい遅延リストを返すEnum.hard_count xs
で遅延リストxs
の要素数を返す。Enum.map f xs
で遅延リストxs
の各要素に対して関数f
を適用した新しい遅延リストを返すEnum.reduce f xs
でxs
の第一要素を初期値としてfold
的にf
関数を累積的に適用した値を返す
と遅延リストやストリームでおなじみの関数群を使っている。
これらや他の遅延リスト関連の関数については
に詳細が載っていて、このページをずっと読み返しながら解いていた。はやく自然と使いこなせるようになりたい。
長くなってきたので後編中編に続く。
Concepts, Techniques and Models of Computer Programmingを読みはじめた
過去何回かぱらっとめくったくらいで置いておいたConcepts, Techniques and Models of Computer Programmingという本を去年の終わりあたりに少し真面目に読み始めた。
なぜか時々「ポストSICP」と言われる本で、CSの根幹部分の一つを書き表した大作・名著である。関数型や論理型やオブジェクト指向などのいわゆるプログラミング言語のパラダイム、あるいは並行性などの実行モデルなどが、どのような言語機構の組み合わせで可能になり、どのようなより粒度の細かい分類が可能で、どのような特性があり、どのような書き方・問題へのアプローチを可能とするのか、について書かれている。
どこらへんが「ポストSICP」なのかは個人的には謎だが。SICPと扱うテーマの範囲も違うし、プログラミング初心者向けとは到底思えないし、SICPを読み終わった後に必ず読むべき!という順序もあまりぴんとこないし・・・ 別に例えば先にCLRS読んでもいいしPAIP読んでもいいし、CTMCPがSICPの次にくるべき理由は思い当たらない・・・
ともあれCTMCPは面白そうな本である。
マルチパラダイム言語Ozとその実行環境Mozartを使って様々なプログラミング概念を提示しているのだが、そのOzというのも
- 抽象機械によるoperational semanticsが与えられている仕様が小さいOz kernel language
- Oz kernel languageの上にsyntax sugarを重ねた実用言語
の二層にわかれている。章を追うごとにkernel languageを拡張、あるいはsyntax sugarを追加していくことで新しいパラダイムに対応していく。それによってどのような原子的な言語要素から各言語機構が立ち上がってくるのかを明確にしている。
よっしゃとりあえずまずは実装だ!ということで例によってOCamlでkernel languageを書き始めている。
今のところ数字と関数定義のところまでできていて、次はレコードの実装。それが済んだら第2章で説明されているもっとも簡単なkernel languageはできあがる。その後はsyntax sugarを載せてみたり、先の章のkernel language extensionを実装したりしてみる。
とりあえずレコードができたら実装内容や言語の特徴についていったん振り返ってまた記事を書きたい。