Zenn
Open10

OCaml って、どう？

AtCoder
toyboot4etoyboot4e

うおお

Zenn のマークダウンエディタがめちゃめちゃ格好良くなっています！　最高！！

Inline styling って相当難しいんじゃないでしょうか

toyboot4etoyboot4e

編集キャンセル時に承認ダイアログが出るようになって事故も減りました。ありがたい

toyboot4etoyboot4e

ML ファミリーへの偏見

学習前の狭い視野をメモしておきます。

注. マイナスイメージをそのまま書きました
  • 非純粋関数型言語
  • メソッドチェイン党
  • 推論は強いが関数の型を書けない
  • 面白みは無いが規格化された言語
  • Fortran と同じような辛さを内包している

もちろん 遠からずこんな視点は覆る ことと思いますので、 ML 派の人は馬鹿だなーと笑ってお見過ごしください 🙇‍♂️

toyboot4etoyboot4e

環境構築 (1)

ocaml, opam, dune を home-manager でグローバルインストールの上、環境構築してみました。

Quickstart (dune)

プロジェクトを作成します:

$ dune init project coml
Entering directory '/home/tbm/dev/ocaml/coml'
Success: initialized project component named coml
$ cd coml
$ ls
bin/  _build/  coml.opam  dune-project  lib/  test/

デフォルトの main.ml を実行します:

$ cat bin/main.ml
let () = print_endline "Hello, World!"
$ dune exec coml
Hello, World!

以降、プロジェクトの設定変更には dune-project を編集します。 dune build 時に <project>.opam が更新されます。

opam がパッケージマネジャ、 dune がビルドツールだそうです。

Emacs

LSP の話が全然見つからず、 merlin を使う のが簡単そうです。最も簡素な設定を試します:

(progn ;; OCaml (`tuareg-mode` + `merlin-mode`)
    (add-to-list 'auto-mode-alist '("\\.ml\\'" . tuareg-mode))
    (autoload 'merlin-mode "merlin" "Merlin mode" t)
    (add-hook 'tuareg-mode-hook #'merlin-mode))

(leaf dune)

tunareg-mode および merlin-mode は共に builtin のパッケージです。 Emacs はデカい。この時点でエラー表示するものの、インライン表示されません:

代わりに flycheck-ocaml によってエラー表示してみます:

(leaf flycheck-ocaml
    :custom (merlin-error-after-save . nil)
    :hook ((tuareg-mode-hook . flycheck-ocaml-setup)
           (tuareg-mode-hook . flycheck-mode)))

lsp-ui-mode が動いていないため、やはりエラー内容のインライン表示がありません。 flycheck-inline を入れてマシになりました:

(leaf flycheck-inline
    :hook (tuareg-mode-hook . flycheck-inline-mode))

エラー一覧は consult-flycheck で見れば良いでしょう:

TODO: キーバインディング

toyboot4etoyboot4e

外部ライブラリの追加

dune ファイルに依存を追記します:

dune-project
(package
 (name coml)
 (synopsis "A short synopsis")
 (description "A longer description")
 (depends
   ocaml
   dune
+  core
  )
 (tags ("competitive")))
bin/dune
(executable
 (public_name coml)
 (name main)
 (libraries
   coml
+   core
))

core パッケージを開いてみます:

bin/main.ml
open Core

let () = print_endline "Hello, World!"

$ dune build
File "bin/dune", line 8, characters 3-7:
8 |    core
       ^^^^
Error: Library "core" not found.

こけました。 NixOS のせいなのでしょうか？

Nix

OCaml - NixOS Wiki に OCaml スクリプトが載っていて面白かったです。

#!/usr/bin/env nix-shell
(*
#!nix-shell --pure -i ocaml -p ocaml
*)

print_string "Hello world! 🚀 \n";;

それはともかく、 ocamlPackage.findlib を導入した場合、 ocamlPackages.* で指定したライブラリが見えるようになるようです。 flake-utils で作った適当な flake.nix を nix-direnv でロードしました:

flake.nix
{
  description = "A basic flake with a shell";
  inputs.nixpkgs.url = "github:NixOS/nixpkgs/nixpkgs-unstable";
  inputs.flake-utils.url = "github:numtide/flake-utils";

  outputs = { nixpkgs, flake-utils, ... }:
    flake-utils.lib.eachDefaultSystem (system:
      let
        pkgs = nixpkgs.legacyPackages.${system};
      in
      {
        devShells.default = with pkgs; mkShell {
          packages = [
            # atcoder-cli is from npm
            online-judge-tools
            python311Packages.selenium
            nodejs

            ocaml
	    opam
	    dune_3
	    ocamlPackages.merlin
	    ocamlPackages.findlib

	    ocamlPackages.num
	    ocamlPackages.containers
	    ocamlPackages.core
	    ocamlPackages.iter
	    ocamlPackages.batteries
          ];
        };
      });
}

.envrc は テンプレートで生成 しました:

.envrc
if ! has nix_direnv_version || ! nix_direnv_version 3.0.4; then
    source_url "https://raw.githubusercontent.com/nix-community/nix-direnv/3.0.4/direnvrc" "sha256-DzlYZ33mWF/Gs8DDeyjr8mnVmQGx7ASYqA5WlxwvBG4="
fi
use flake

これで実行できました:

$ git add flake.nix
$ dirnev allow
$ dune build
$ dune exec
Hello, World!

もっとやりようはあると思いますが、今は動けばいいので……！

toyboot4etoyboot4e

REPL (utop)

Real World OCaml の序盤を読んでいると整理が付きました。

整理

ツール類:

  • opam
    パッケージマネジャ
  • dune
    opam に依存したビルドツール
  • utop
    REPL (ocaml コマンドで起動される toplevel よりも高機能)

ライブラリ:

  • (std?)
    bootstrapping のための極小のライブラリ
  • base
    Jane Street 社の汎用だが最小限のライブラリ
  • core
    base に色々追加したライブラリ

utop

utop をインストールして実行してみました。

凄い。独自 UI を実装しており、単体で補完が効きます。 REPL は #quit;; または Ctrl-D で脱出できます。

utop (Emacs)

Evil と相性が悪いし、補完も動いていませんでした。設定が悪いかもですが、 utop はターミナルから使うことにします。

toyboot4etoyboot4e

AtCoder Beginners Selection

まずは簡単な問題で雰囲気を見てみます。

懸念

コンパイラの最適化オプションが指定されておらず、 ？ iter などで顕著な低速化が見られるようです。

型を元に関数を検索したい

OCaml tool: type sig -> list of names? - Learning - OCaml

if 関数が欲しかったのですが、 OCaml の典型的なシグネチャが分からず見つけられませんでした。

1. ABC086A - Product

@@ 演算子が Haskell の $ に相当するようです。書き方は lmdexpr/contest を参考にします。

open Core
open Scanf

let a, b = scanf "%d %d" Tuple2.create
let () = print_endline @@ if a * b % 2 = 0 then "Even" else "Odd"

2. ABC081A - Placing Marbles

Batteries のドキュメントが比較的良かったので使ってみました。 GitHub のリポジトリ では About がリンク切れになっていますが、このライブラリは大丈夫なんだろうか……

open Batteries
open Batteries.IO

let () =
  read_line stdin
    |> String.to_list
    |> List.map (fun c -> Char.code c - Char.code '0')
    |> List.sum
    |> String.of_int
    |> print_endline

3. ABC081B - Shift only

Batteries に不信感があり、 core と iter の併用を試すことにします。

open Core
open Scanf

let ints1 = scanf "%d" Fn.id
(* let ints2 = scanf "%d %d" Tuple2.create *)
let array_n n = Array.init n ~f:(fun _ -> scanf " %d" Fn.id)

let rec countDiv2 = function
  | n when n %2 = 0 -> 1 + countDiv2 (n / 2)
  | _ -> 0

let n = ints1
let xs = array_n n

let () = Iter.of_array xs
  |> Iter.map countDiv2
  |> Iter.min_exn ~lt:Int.(<)
  |> string_of_int
  |> print_endline

引数を function .. の形で受け取ることで、引数に対するガードを書くことができました。

~f: とか ~lt: の部分ですが、なぜか高階関数は名前付き引数 (?) の形で渡す必要があるようです。型に ? が付いている値は名前付きにする必要があるのかも？　コンパイルエラーは謎です。

未使用の関数があると、無言で RE になる ようです (提出) 。このジャッジ環境は改善の余地がありますね (未使用の関数の存在を許して欲しいし、せめてコンパイルエラーにしてほしいです) 。 ints2 が関数ではなく定数になっていたのが問題でした (ご指摘ありがとうございます！)

4. ABC 087 B - Coins

全探索の問題が来ました。 3 重ループの代わりに flat_map を使います。

open Core
open Scanf

let a, b, c, x = scanf "%d %d %d %d" (fun a b c d -> (a, b, c, d))

let xss =
  Iter.(0 -- a)
  |> Iter.flat_map @@ fun na ->
     Iter.(0 -- b)
     |> Iter.flat_map @@ fun nb ->
        Iter.(0 -- c) |> Iter.map @@ fun nc -> (na, nb, nc)

let res =
  xss
  |> Iter.filter_count @@ fun (na, nb, nc) ->
     (500 * na) + (100 * nb) + (50 * nc) = x

let () = print_endline @@ string_of_int res

Iter.( >>= ) を使うとより簡潔になりました。正直リストモナドが欲しいのですが、 OCamlらしい書き方はどうなんでしょう:

open Core
open Scanf

let ( >>= ) = Iter.( >>= )
let a, b, c, x = scanf "%d %d %d %d" (fun a b c d -> (a, b, c, d))

let xss =
  Iter.(0 -- a) >>= fun na ->
  Iter.(0 -- b) >>= fun nb -> Iter.(0 -- c) |> Iter.map @@ fun nc -> (na, nb, nc)

let res =
  xss
  |> Iter.filter_count @@ fun (na, nb, nc) ->
     (500 * na) + (100 * nb) + (50 * nc) = x

let () = print_endline @@ string_of_int res

フォーマッタが欲しくなりました。 ocamlformat をインストールの上で空の .ocamlformat を作成すると、自動で整形されるようになりました。

(leaf ocamlformat
    :init
    (defun reserve-ocaml-format-on-save ()
        (add-hook 'before-save-hook 'ocamlformat-before-save))
    :hook (tuareg-mode-hook . reserve-ocaml-format-on-save))

scanf は読んだ入力を捨てない気がします。入力をちょっとずつ読み進める方法を知りたいです。 前述の ints2 と同じハマり方をしていました。

5. ABC 083 B - Some Sums

今までの手札で解けました。

open Core
open Scanf

let n, a, b = scanf "%d %d %d" (fun a b c -> (a, b, c))

let rec digit_sum = function
  | x when x = 0 -> 0
  | x ->
      let q = x / 10 and r = x % 10 in
      r + digit_sum q

let res =
  Iter.(1 -- n)
  |> Iter.filter (fun x ->
         let s = digit_sum x in
         s >= a && s <= b)
  |> Iter.sum

let () = print_endline @@ string_of_int res

6. ABC088B - Card Game for Two

未使用の関数などのエラーで警告が出ないように設定を追加しました:

bin/dune
(executable
 (public_name coml)
 (name main)
+ (flags
+  (:standard -warn-error -A))
 (libraries coml num containers core iter batteries))

暫定ライブラリです:

open Core
open Scanf

let ( >>= ), ( -- ) = (Iter.( >>= ), Iter.( -- ))
let read_line () = In_channel.input_line_exn In_channel.stdin

(* let read_int () = read_line () |> Int.of_string *)
let ints1 () = scanf " %d" Fn.id
let ints2 () = scanf " %d %d" Tuple2.create
let ints3 () = scanf " %d %d %d" Tuple3.create
let ints4 () = scanf " %d %d %d %d" @@ fun a b c d -> (a, b, c, d)
let ints5 () = scanf " %d %d %d %d %d" @@ fun a b c d e -> (a, b, c, d, e)
let ints6 () = scanf " %d %d %d %d %d %d" @@ fun a b c d e f -> (a, b, c, d, e, f)
let array_n n = Array.init n ~f:(fun _ -> scanf " %d" Fn.id)
let print_yn b = print_endline @@ if b then "Yes" else "No"

解答はこちら:

let solve xs =
  let n = Array.length xs in
  let rec inner = function
    | i when i >= n -> 0
    | i when i = n - 1 -> xs.(i)
    | i -> xs.(i) - xs.(i + 1) + inner (i + 2)
  in
  inner 0

let () =
  let n = ints1 () in
  let xs =
    let xs = array_n n in
    Array.sort ~compare:(fun x y -> Int.compare y x) xs;
    xs
  in
  print_endline @@ string_of_int @@ solve xs

こうして問題を解いていけば、 ML は地に足を付けたソリッドな言語だと思う日が来るのでしょうか。問題無く読める日は近そうです。

7. ABC085B - Kagami Mochi

Array を Iter 経由で sort_uniq してみましたが、 6 ms とかなり無駄がありそうです。

let () =
  let n = ints1 () in
  let xs = array_n n in
  Array.sort ~compare:Int.compare xs;
  (* TODO: Is this efficient sorting? *)
  let xs = xs |> Iter.of_array |> Iter.sort_uniq |> Iter.to_array in
  print_endline @@ string_of_int @@ Array.length xs

8. ABC085C - Otoshidama

String.concat は同名関数がヒットしますが、 core のドキュメントの方を見るとラベル名が分かりました。

let () =
  let n, y = ints2 () in
  (* 10000, 5000, 1000 *)
  let ns =
    0 -- (y / 10000) >>= fun n10000 ->
    0 -- (n - n10000) |> Iter.map @@ fun n5000 -> (n10000, n5000, n - n10000 - n5000)
  in
  let a1, b1, c1 =
    ns
    |> Iter.find_pred (fun (n10000, n5000, n1000) ->
           (10000 * n10000) + (5000 * n5000) + (1000 * n1000) = y)
    |> Option.value ~default:(-1, -1, -1)
  in
  [ a1; b1; c1 ] |> List.map ~f:string_of_int |> String.concat ~sep:" " |> print_endline

9. ABC049C - 白昼夢

List.map のシグネチャが思っていたのと違いました:

val map : 'a list -> f:('a -> 'b) -> 'b list

オブジェクト指向と同じシグネチャです。使い方は map xs f または xs |> map ~f:f です。

WIP

10.

Genki SATO(佐藤玄基)Genki SATO(佐藤玄基)

ABC081B で未使用の関数があると無言で RE になる件ですが、未使用の関数が怒られているというよりは、OCamlにはIOモナドも遅延評価もないので、int2を定義した瞬間に入力を無意味に2個食われており、それで入力が足りなくてエラーが出ているだけという気がします。int2 : int*int ではなく int2 : unit -> (int*int) を考えたらいいのでは。

toyboot4etoyboot4e

ありがとうございます！　unit を引数に取って解決しました。ジャッジ環境のせいにして申し訳ない気持ちでいっぱいです。

他にも変な挙動があったのですが、全て同じ原因で解決しました 🙏