Haskellで蟻本 2-3

はじめに

• シリーズ一覧
• 初回の記事

この記事のmemoizeを使用します。

2-3 動的計画法

純粋関数型言語としては、扱いにくいところですね。

探索のメモ化と動的計画法

01 ナップサック問題

愚直

どうせ遅いので、リストの添え字アクセスもそのままにしています。

solve n goods w = f 0 w where
  f i j
    | i == n = 0
    | j < wi = f (i+1) j
    | otherwise = max (f (i+1) j) (f (i+1) (j-wi) + vi)
    where (wi, vi) = goods !! i

メモ化再帰

これがめんどくさくてmemoizeを作りました。memoizeにしか使っていないところは隠しておきます。

import Control.Monad
import qualified Data.Vector.Unboxed as U

solve :: Int -> [(Int,Int)] -> Int -> Int
solve n goods' w = f (0, w) where
  goods = U.fromList goods'
  f = memoize ((0,0), (n,w)) [(0,w)] f'
  f' f (i, j)
    | i == n = return 0
    | j < wi = nxt
    | otherwise = liftM2 max nxt nx'
    where
      nxt = f (i+1, j)
      nx' = (+vi) <$> f (i+1, j-wi)
      (wi, vi) = goods U.! i

ボトムアップ

foldlでもDPができます。

import Control.Monad
import qualified Data.Vector.Unboxed as U

solve n goods w = U.last $ foldl f initial goods where
  f acc (w, v) = U.zipWith max acc pick where
    pick = U.map (v+) $ U.replicate w (-v) U.++ acc
  initial = U.replicate (w+1) (0::Int)

最長共通部分列問題

カリー化されていない引数を持つのは慣れないですね。

import Control.Monad
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as U

solve :: Int -> Int -> String -> String -> Int
solve n m s' t' = f (n-1, m-1) where
  f = memoize ((-1,-1), (n-1, m-1)) f'
  f' _ (-1, _) = return 0
  f' _ (_, -1) = return 0
  f' f (i, j)
    | s!i == t!j = succ <$> f (i-1, j-1)
    | otherwise = liftM2 max (f (i-1, j)) (f (i, j-1))
  [s, t] = map U.fromList [s', t']

漸化式を工夫する

個数制限なしナップサック問題

memoize、けっこう便利です。

import Control.Monad
import qualified Data.Vector.Unboxed as U

solve :: Int -> [(Int, Int)] -> Int -> Int
solve n goods w = f (n, w) where
  f = memoize ((0,0), (n,w)) f'
  f' f (i, j)
    | i == 0 = return 0
    | j < wi = pre
    | otherwise = liftM2 max pre pr'
    where
      pre = f (i-1, j)
      pr' = (+vi) <$> f (i, j-wi)
      (wi, vi) = U.fromList goods U.! (i-1)

配列再利用とか添え字を交互に使うとかはfoldlの出番ですね。01ナップサック問題のボトムアップで書いたのと同じ。

01ナップサック問題その2

Data.Functor.<&>を使ってみました。ちょっと見やすいかも。

import Control.Monad
import Data.Functor
import qualified Data.Vector.Unboxed as U

solve :: Int -> [(Int,Int)] -> Int -> Int
solve n goods w = ans where
  ans = maximum [v | v <- [0..mv*n], f (n, v) <= w]
  mv = maximum $ map snd goods
  f = memoize ((0, 0), (n, mv*n)) f'
  f' f (i, j)
    | i == 0 = return $ if j == 0 then 0 else w+1
    | j < vi = pre
    | otherwise = liftM2 min pre pr'
    where
      pre = f (i-1, j)
      pr' = f (i-1, j-vi) <&> (+wi)
      (wi, vi) = U.fromList goods U.! (i-1)

個数制限付き部分和問題

import Control.Monad
import qualified Data.Vector.Unboxed as U

solve :: Int -> [(Int, Int)] -> Int -> Bool
solve n am k = f (n, k) >= 0 where
  f = memoize ((0, 0), (n, k)) f'
  f' _ (0, j) = return $ -j
  f' f (i, j) = do
    a <- f (i-1, j)
    if a >= 0 then return mi
    else if j < ai then return $ -1
    else pred <$> f (i, j-ai)
    where (ai, mi) = U.fromList am U.! (i-1)

最長増加部分列問題

Data.Vector.Algorithms.Search.binarySearchL の説明がわかりやすかったです。

Finds the lowest index in a given sorted vector at which the given element could be inserted while maintaining the sortedness.

sortedness を保った状態で挿入できる最小のインデックスを求める、という感覚はなかったかも。

import Control.Monad
import Control.Monad.ST
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.Vector.Algorithms.Search

solve n a = runST $ do
  dp <- UM.replicate n (10^6+1)
  forM_ a $ \a -> do
    i <- binarySearchL dp a
    UM.write dp i a
  binarySearchL dp (10^6+1)

計算問題に対するDP

分割数

import Control.Monad

solve :: Int -> Int -> Int -> Int
solve n m mo = f (n, m) where
  f = memoize ((0, 0), (n, m)) f'
  f' f (i, j)
    | i == 0 = return $ if j == 0 then 1 else 0
    | i > j = f (i-1, j)
    | otherwise =
      (`mod` m) <$> liftM2 (+) (f (i, j-i)) (f (i-1, j))

重複組み合わせ

liftM3までするぐらいならdo構文を使ってもよさそうですね。

import Control.Monad
import qualified Data.Vector.Unboxed as U

solve :: Int -> Int -> [Int] -> Int -> Int
solve n m a mo = f (n, m) where
  f = memoize ((0, 0), (n, m)) f'
  f' f (i, j)
    | j == 0 = return 1
    | i == 0 = return 0
    | j-1-ai < 0 = (`mod` mo) <$> liftM2 (+) p q
    | otherwise = (`mod` mo) <$> liftM3 (+-) p q r
    where
      p = f (i, j-1)
      q = f (i-1, j)
      r = f (i-1, j-1-ai)
      ai = U.fromList a U.! (i-1)
      (+-) a b c = a + b - c

おわり

めんどくせーと思って抽象化したmemoizeがとてもよく働きましたね。関数を含んだ抽象化がやりやすいのは関数型言語の強味だと思います。ところでそろそろ本に載っているサンプル１つでチェックするのはどうなの、という感じがしてきました。まあいいや。

Haskellでメモ化再帰

はじめに

Haskellでメモ化再帰が楽にできるようにしてみたかったので、やってみた。競技プログラミングに使えればいい、というぐらい。

型

Ixは Data.Ix.Ix で、Unboxableは Data.Vector.Unboxing.Unboxable です。

memoize ::
  (Ix i, Unboxable e) =>
  (i, i) ->
  (forall m. Monad m => (i -> m e) -> i -> m e) ->
  i -> e

使用例

型を見ればなんとなくわかると思います。Data.Function.Fix.fix とほぼ同じです。Mintは modint です。

fib = memoize (0, 10^6) $ \fib n ->
  if n <= 1 then return $ Mint n
  else liftM2 (+) (fib $ n-1) (fib $ n-2) 

実装

本当はSTUArrayとかを使いたかったんですが、値が unboxed であるという制約を課すのが面倒で、Ixだけ拝借しました。ついでに、メモには modint をのせたいことが多いので、newtype フレンドリーな unboxed vector を使いました。

そこまで凝ったことはしていないので、特に解説はありません。

本質

高速化のための書き方は、実装を眺める上ではノイズになりがちです。省いたやつを書いてみます。どうだろう、修飾なしは逆にわかりにくいところもあるかもしれない。遅いはずですが、計測していません。

import Prelude hiding (read, replicate)
import Data.Vector ((!), freeze)
import Data.Vector.Mutable
import Data.Ix

memoize ::
  (Ix i) =>
  (i, i) ->
  (forall m. Monad m => (i -> m e) -> i -> m e) ->
  i -> e
memoize ran fun i = memo ! index ran i where
  size = rangeSize ran
  memo = runST $ do
    memo <- new size
    memd <- replicate size False
    forM_ (range ran) $ calc memo memd
    freeze memo
  calc memo memd i = do
    written <- read memd ix
    unless written $ do
      write memo ix =<< fun (calc memo memd) i
      write memd ix True
    read memo ix
    where ix = index ran i

実際の実装

高速化と修飾をしたやつです。unsafe まみれですが、memd がチェックしているので、あまり危険ではないはずです。

import qualified Data.Ix as I
import qualified Data.Vector.Unboxing as U
import qualified Data.Vector.Unboxing.Mutable as U

memoize ::
  (I.Ix i, U.Unboxable e) =>
  (i, i) ->
  (forall m. Monad m => (i -> m e) -> i -> m e) ->
  i -> e
memoize ran fun i = res where
  res = U.unsafeIndex memo I.index ran i
  size = I.rangeSize ran
  memo = runST $ do
    memo <- UM.unsafeNew size
    memd <- UM.replicate size False
    forM_ (I.range ran) $ calc memo memd
    U.unsafeFreeze memo
  calc memo memd i = do
    written <- UM.unsafeRead memd ix
    unless written $ do
      UM.unsafeWrite memo ix =<< fun (calc memo memd) i
      UM.unsafeWrite memd ix True
    UM.unsafeRead memo ix
    where ix = I.index ran i

おわりに

まだ実用していないのに記事に仕立て上げてしまった。

言語拡張を書くのを忘れていたことに気づきました。RankNTypes が必要です。

Haskellで蟻本 2-2

はじめに

• シリーズ一覧
• 初回の記事
• 前回の記事

2-2 貪欲法

硬貨の問題

硬貨の問題

貪欲は畳み込み、という感じがする。

solve cs a = snd $ foldl f (a, 0) cs' where
  f (r, a) (n, v) = (r - v*q, a + q) where
    q = min n $ div r v
  cs' = reverse $ zip cs [1, 5, 10, 50, 100, 500]

区間の問題

区間スケジューリング問題

貪欲は畳み込み。普段はfoldlとか使わずにアキュムレータを持たない再帰関数を書くことも多いです。

import Data.List

solve n s t = snd $ foldl f (0, 0) st where
  st = sortOn snd $ zip s t
  f (a, c) (s, t)
    | a < s = (t, c + 1)
    | otherwise = (a, c)

辞書順最小の問題

Best Cow Line

これが意外と速いんですよね。遅延評価と最適化がすごいんでしょう。AtCoderのコードテストでランダム10000文字が845msでした。

solve n s = go s (reverse s) where
  go [] [] = []
  go s@(c:_) s'@(c':_)
    | s < s' = c : go (tail s) (init s')
    | otherwise = c' : go (init s) (tail s')

その他の例題

Saruman's Army

import Data.List

solve n r xs = go (sort xs) where
  go [] = 0
  go (x:xs) = 1 + go (f x xs)
  f x xs = g $ span (<= x+r) xs
  g ([], b) = b
  g (a, b) = dropWhile (<= last a + r) b

Fence Repair

うーん、O(N²)のほうがむしろめんどくさそうなのでヒープを使います。こういうのはStateモナドがかっこよく使えてお気に入り。

import Control.Monad.State
import qualified Data.Heap as H
import Data.Maybe

solve n l = (`evalState` H.fromList l) $ do
  cs <- replicateM (n-1) $ do
    l1 <- pop
    l2 <- pop
    push (l1+l2)
    return (l1+l2)
  return $ sum cs

pop :: Ord a => State (H.Heap a) a
pop = state $ fromJust . H.uncons

push :: Ord a => a -> State (H.Heap a) ()
push x = modify $ H.insert x

おわりに

いろんな書き方があって楽しいですね。問題を解きながらhoogleを見回ると、たくさん発見があって面白いです。

Haskellで蟻本 2-1

はじめに

前回の続き。

2-1

階乗

こう書くと勝手に多倍長整数を扱っていると推論されるので、10000の階乗ぐらいなら一瞬で吐き出してくれます。

fact 0 = 1
fact n = n * fact (n-1)

フィボナッチ数

単純な再帰。

fib n
  | n <= 1 = n
  | otherwise = fib (n-1) + fib (n-2)

メモ化再帰。今やってみたらいけたんですが、これ問題ないのかな……？

import Data.Vector (Vector, (!))
import qualified Data.Vector as V 

fib = (memo !) where
  memo = V.generate (10^6 + 1) f
  f 0 = 0
  f 1 = 1
  f n = fib (n-1) + fib (n-2)

スタック

まあ、一応、書きました。popの仕様はこのほうが好きですね。

import Control.Monad.State

push :: a -> State [a] () 
push x = modify (x:)

pop :: State [a] a
pop = state (\(x:xs) -> (x,xs))

test = (`evalState` []) $ do
  push 1
  push 2
  push 3
  a <- pop
  b <- pop
  c <- pop
  return (a,b,c)

キュー

スタックと同じく。これ両端キューですけどね。

import Control.Monad.State
import Data.Sequence

push :: a -> State (Seq a) ()
push x = modify (x <|)

pop :: State (Seq a) a
pop = state (\(sq :|> x) -> (x, sq))

test = (`evalState` empty) $ do
  push 1
  push 2
  push 3
  a <- pop
  b <- pop
  c <- pop
  return (a,b,c)

深さ優先探索

部分和問題

アルゴリズムはコードの見た目に現れないこともあります。

solve n a k = k `elem` sums where
  sums = map sum $ mapM (\a -> [a,0]) a

Lake Counting

制約がゆるいので、O(NM log (NM))で……。

import Data.Map (Map, (!))
import qualified Data.Map as M

solve n m garden = count $ scanl f (False, gardenMap) points where
  count = length . filter fst
  gardenMap = genGardenMap garden
  points = concatMap ((`zip` [1..m]).repeat) [1..n]
  f (_, gm) p
    | gm!p == 'W' = (True, dfs gm p)
    | otherwise = (False, gm)

dfs gm p@(x,y)
  | p `M.notMember` gm = gm
  | gm!p == 'W' = gm'
  | otherwise = gm
  where
    gm' = foldl dfs (M.insert p '.' gm) np
    np = [(i,j) | i<-[x-1..x+1], j<-[y-1..y+1], (i,j) /= p]

genGardenMap garden = M.fromList
    $ concatMap (\(i, row) -> zip (repeat i) [1..]  `zip` row)
    $ zip [1..] garden

幅優先探索

迷路の最短路

Lake Counting と同じく。

import Data.Map (Map, (!))
import qualified Data.Map as M
import Data.Sequence (Seq(..), (<|))
import qualified Data.Sequence as S

solve n m s g maze = dist ! g where
  dist = go (S.singleton (s,0)) M.empty
  mazeMap = genMazeMap maze
  go Empty dist = dist
  go (que :|> (p@(x,y), d)) dist
    | outOfMaze || p `M.member` dist = go que dist
    | otherwise = go que' (M.insert p d dist)
    where
      outOfMaze
        = x<1 || n<x || y<1 || m<y || mazeMap!p == '#' 
      que' = foldr (<|) que next
      next = [ ((x+dx, y+dy), d+1) | (dx, dy) <- dr]
      dr = [(1,0), (-1,0), (0,1), (0,-1)]

genMazeMap = genGardenMap

特殊な状態の列挙

順列全探索

操作によって書き方も変わってくるので、適当に。これ辞書順じゃないんですね。

import Data.List

solve = map f . permutations where
  f = id

おわりに

迷路と庭しんど……

Haskellで蟻本 CHAPTER 1

はじめに

プログラミングコンテストチャレンジブック（通称「蟻本」）を買ったので、Haskellのコードに落とすチャレンジをしようと思います。解説は基本的にしないつもりです。

目標とする計算量が達成できたらOKということにします。バージョンはGHC8.8.3です。

CHAPTER 1

1-1

くじびき

replicateMがとても便利ですね。

import Control.Monad

main = do
  [n, m] <- map read . words <$> getLine
  k <- map read . words <$> getLine
  putStrLn $ if solve n m k then "Yes" else "No"

solve n m k = m `elem` [ sum abcd | abcd <- replicateM 4 k ]

1-3

くじびき

出力も省略します。ついでに、YesかNoならBoolにしてしまいます。

import Control.Monad

solve n m k = m `elem` [ sum abcd | abcd <- replicateM 4 k ]

1-6

三角形

sublistがけっこうきれいに書けて嬉しい。

import Data.List

solve n a = maximum $ 0 : [
  sum es | es <- sublist 3 a, 2 * maximum es < sum es]

sublist 0 _ = [[]]
sublist k xs
  = [ y:zs | (y:ys) <- tails xs, zs <- sublist (k-1) ys]

Ants

solve l n x = (minT, maxT) where
  minT = maximum [ min x (l-x) | x <- x ]
  maxT = maximum [ max x (l-x) | x <- x ]

くじびき

二分探索はめんどくさかった……。これがO(n³ log n)

import Control.Monad
import Data.Set

solve n m k = any pred [ sum abc | abc <- replicateM 3 k ] where
  pred x = (m-x) `member` fromList k

これがO(n² log n)です。

import Control.Monad
import Data.Set

solve n m k = any pred kk where
  pred x = (m-x) `member` fromList kk
  kk = [ sum ab | ab <- replicateM 2 k ]

おわりに

とりあえずここまで。続く、かも。

ABC161 D を Haskell で解く

ABC161 D - Lunlun Number が Haskell できれいに解けたので簡単な解説を書いておきます．

問題概要

隣り合う 桁の数字の差の絶対値が 以下であるような正の整数を L数 といいます． 番目に小さい L数 を求めてください．

解答

（提出）

main = readLn >>= print . (lnum!!) . pred where
 lnum = [1..9] ++ concatMap f lnum
 f x
  | r == 0 = [x*10, x*10+1]
  | r == 9 = [x*10+8, x*10+9]
  | otherwise = [x*10+r-1 .. x*10+r+1]
  where r = mod x 10

解説

考察

小さいほうから 9 つの L数 は当然 です． の次は，と続きます．その続きは， ですね．

ここで， が L数 であれば も L数 であることに注目します．これを言い換えると， 以上の L数 は，ある L数 を用いて と表すことができる，ということです．ここで， は の 一の位との差の絶対値が 以下の，一桁の数です．

以上の L数 を上記のように表したとき， が小さいほど小さい L数であることは明らかです．そして が同じならば の大小に依存します．（異なる L数 は異なる組 に対応することも確認しておきましょう．）

実装

考察が途中ですが，ここからは Haskell の話題が入るので実装部分としてしまいます．

さて，求めるべきは昇順ソートされた L数 のリストです．これを lnum としておきます．実装するときは，この時点で

main = readLn >>= print . (lnum!!) . pred where

まで書いてしまうことをおすすめします．

さて， 未満の L数 を smallLnum = [1..9] としましょう． 以上の L数 largeLnum は，ある L数 を用いて と表すことができます．lnum が昇順ソートされた のリストですから，lnum のそれぞれに を足します．

largeLnum = map f lnum where
  f x = map (10*x+) a where
    a = [r-1 .. r+1]
    r = mod x 10

おっと， は一桁の数，でしたね．それに，これだと largeLnum は [[Int]] になってしまいますから，concatMap を使いましょう．

largeLnum = concatMap f lnum where
  f x
    | r == 9 = [10*x+8, 10*x+9]
    | r == 0 = [10*x, 10*x+1]
    | otherwise = [10*x+r-1 .. 10*x+r+1]
   where r = mod x 10

これでいいですね．

未満の L数 と， 以上の L数 をすべて求めることができたので，L数 はすべて求まりました！lnum = smallLnum ++ largeLnumとして，おしまいです．smallLnum や largeLnum をそれらの定義に置き換えると

lnum = [1..9] ++ concatMap f lnum where

（以下略）となります．

lnum の定義中で lnum が使われていますね．しかし実は，これで問題なく動作するのです．

動作確認

コンパイルして最大ケースを実行すればよいです！！！......というのは半ば冗談ですが，間違ったことはしていないはずなので，動けば正しいです．念のため，どのように評価されていくかを確認しましょう．（評価戦略には詳しくないので、かなり雑にやっています，コンパイルして最大ケースを実行すればよいです，のほうが正しい主張かもしれません．）

lnum = [1..9] ++ concatMap f lnum

この段階で head lnum は 1 だとわかっているので

lnum = [1..9] ++ f 1 ++ concatMap f (tail lnum)

この段階で head (tail lnum) は 2 だとわかっているので

lnum = [1..9] ++ f 1 ++ f 2 ++ concatMap (tail (tail lnum))

この段階で head (tail (tail lnum)) は 3 だとわかっているので......面倒なので不正確な表記をします．... は間の L数 を補います．

lnum = [1 ... last (f 3)] ++ concatMap [4,5,6 ...]
lnum = [1 ... last (f 4)] ++ concatMap [5,6,7 ...]
lnum = [1 ... last (f 9)] ++ concatMap [10,11,21 ...]
lnum = [1 ... last (f 21)] ++ concatMap [22,23,32 ...]

このように無限の長さをもつリスト lnum が計算されていきます．Haskell は標準で遅延評価を採用しているため，このような無限リストを簡単に扱うことができます．" 番目を出力せよ"と命令が下ってから 番目までだけを計算するわけですね．

Haskell で競技プログラミング

ここでは長々と書きましたが，再帰的に定義される無限リストの扱いに慣れていると，「L数 は最初が 1~9 で，残りは L数×10 + 一の位 だから......」と言いながら

lnum = [1..9] ++ concatMap f lnum where

と書くことができます．Haskell ではこのように実装上の余分な思考をかなり省けることがあります． そのぶん，公式解説とは異なる思考が求められることも多々ありますが，簡潔に解ける問題のほうが多いと感じています．何よりこういう実装は楽しいので，Haskell，おすすめです．（私は rated コンテストでは使わなくなりましたが.....）

ほかの実装

リスト内包記法を使うこともできます．考察で書いたものにより近いですね．（提出）

lnum = [1..9] ++ [10*x+a | x <- lnum, let r = mod x 10, a <- [r-1 .. r+1], 0 <= a, a <= 9]

Nim 競技プログラミング

最近 Nim 言語を用いて競技プログラミングをしている，私の環境を紹介します．

はじめに

Nim については，Nimを知ってほしい - Qiita とかを見てください．この記事では知っているものとします．

バージョンは AtCoder に合わせて 1.0.6 です．バージョン 1.0.6 の標準ライブラリのドキュメントは https://nim-lang.org/1.0.6/lib.html から閲覧できます．

基本的な事項

入力

以下のコードで文字列を受け取り，parseInt等で変換します．

import strutils
let get = iterator:string =
  for s in stdin.readAll.split: yield s

splitは文字列をWhitespace（空白とか改行とか）区切りで返す iterator です．実質的には inline iterator であるstdin.readAll.splitを closure iterator に変換しています．気持ちとしては

let get = stdin.readAll.split

のような感じです（ただし，これだとgetはseq[string]になります）．自然で短いので気に入っています．

また，配列の入力時にはnewSeqWith(N, get().parseInt)とすることができるのですが，見栄えが悪いので

template rep(a,b):seq = newSeqWith(b,a)
let v = get().parseInt.rep(N)

としています．

出力

たいがいechoを使っています．空白区切りはv.mapIt($it).join" "で，改行区切りはv.mapIt($it).join("\n")です．

入出力の自動生成

問題を解く際，入出力部分は atcoder-tools で自動生成しています．例として Welcome to AtCoder で生成されたファイルをおいておきます．

import strutils, sequtils, math, algorithm, sugar
template rep(a,b):seq = newSeqWith(b,a)

proc solve(a,b,c:int; s:string) =
  discard

when isMainModule:
  let get = iterator:string =
    for s in stdin.readAll.split: yield s
  let a,b,c = get().parseInt
  let s = get()
  solve(a,b,c,s)

カスタムコードジェネレータおよびテンプレートファイルは自作しました．ちなみに when isMainModule に今のところ意味はないです．見た目がちょっときれいかな～というぐらいですね．

ライブラリ管理

ライブラリは，VSCode のスニペットとして扱っています． Nim のコードからスニペット形式への変換のために，自作ツールのnim_snippetを使用しています．

応用的な事項

modint

定数Modで割った余りを扱う modint は，intの distinct type として定義し，使用しています．

const Mod = 1000000007
const LowZ = int.low div Mod*Mod
type fin = distinct int
converter toFin*(a: int): fin = fin((a-int(a<0)*LowZ)mod Mod)
proc `+`(a,b: fin): fin = a.int + b.int
proc `+=`(a: var fin; b: fin) = a = a + b

fin は Finite の頭です．3文字にしたくて検討した結果こうなりました．

converterは暗黙の型変換を可能にします．もちろん安全性は落ちるのですが，自然に書けるため使っています．

bit 操作

bit 全探索などの際に，次のように書くことがあります．

proc contains(s,key: int): bool = bool(s shr key and 1)
iterator items(s:int):int =
  var s = s
  for i in 0..<64:
    if bool(s and 1): yield i
    s = s shr 1; if s == 0: break

整数値を集合として扱う操作が自然に書けるので気に入っています．

最大値を更新する

最大値を更新するためのテンプレートとプロシージャです．chmax と呼ばれていることが多いですね．

template `max=`(a,b)= a = max(a,b)
proc setMax(a: var T; b: T): bool =
  result = a < b
  if result: a = b

a max= b ではなく a.max= b と使います．後者は更新されたかどうかを返します．

セグメント木

次のように定義しています．

type Monoid[T] = object
  op: proc(a,b: T): T
  id: T
type SegTree[T] = object
  tree: seq[T]
  size: int
  mon: Monoid[T]

こうするとなぜか

let intAddMonoid = Monoid[int](op: `+`, id: 0)

と書くことができます．+は関数の引数などに指定できないことが多く，これができる理由はよくわかりません．