はじめに
定数倍程度のオーバーヘッドは気にせず、書きやすさを重視しています。
GitHub
入力
入力として使えるreadは、標準入力からS式を構成する最後の文字までを読みます(※)(https://practical-scheme.net/gauche/man/gauche-refj/Ru-Chu-Li-.html#g_t_5165_529b)
(※ readによる入力は、以下のような動きもできるということです)
gosh> (eval (read) (interaction-environment))
(+ 1 2)
3
カッコで閉じられていない入力に対しては型を以下のように解釈するみたいです。
| 入力 | 型 |
|---|---|
| 整数 | <integer> |
| 小数点数 | <real> |
| 文字列 | <symbol> |
文字列の入力はsymbolとなるので、解くときはstringに変換したほうが扱いやすいです。
また、###のような入力については、#がサポートされていない記号になるのでread-lineで文字列を取得する必要があります。
しかし、read-lineは改行まで文字列を改行抜きで読み込みますが、「readからのread-line」のような流れの入力になると、readで改行が取り残された結果空文字だけが読まれる場合があります。
; 入力
; 1 3
; ###
(let ([x (read)]
[y (read)]
[g (read-line)])
(print (list x y g)))
; 1 3 (空文字)
以上のことを考慮した入力の関数が以下です。
(define (my-read)
(let ([a (read)])
(if (symbol? a)
(symbol->string a)
a)))
(define (my-read-line)
(let ([line (read-line)])
(if (string=? "" line)
(my-read-line)
line)))
入力を楽にするマクロ(solve)を作りました。
(solve
x y s ; x y s それぞれを読み込んで代入
[l : list x] ; x 個の入力をリストとして
[v : vec x] ; x 個の入力をベクターとして
[m : vec x y] ; y 個の x要素ベクター (リストバージョンは用意してません)
[g : grid y] ; 「#」が壁、 「.」が道になるような入力
(print (list x y s l v m g))) ; S式は普通に評価する。
; 入力
; 2 3 aaa
; 6 6
; 7 7
; 8 8
; 9 9
; 10 bb
; #.###
; #...#
; ###.#
; 出力
; (2 3 aaa (6 6) #(7 7) #(#(8 8) #(9 9) #(10 bb)) #(#(# . # # #) #(# . . . #) #(# # # . #)))
(define-syntax solve
(syntax-rules (: list vec grid)
((_ [var : list n])
(define var
(let loop ([i n])
(if (zero? i) () (cons (my-read) (loop (- i 1)))))))
((_ [var : vec n])
(define var
(let ([v (make-vector n)])
(dotimes (i n)
(vector-set! v i (my-read)))
v)))
((_ [var : vec n m])
(define var
(let ([v (make-vector m)])
(dotimes (i m)
(solve [u : vec n])
(vector-set! v i u))
v)))
((_ [var : grid h])
(define var
(let ([v (make-vector h)])
(dotimes (i h)
(let ([row (list->vector (string->list (my-read-line)))])
(vector-set! v i row)))
v)))
((_ (expr ...))
(expr ...))
((_ var)
(define var
(my-read)))
((_ expr1 expr2 ...)
(begin
(solve expr1)
(solve expr2 ...)))))
出力
displayがありますが、gaucheでは改行をしてくれるprintもあります。
(display ans) ; 改行なし
(print ans) ; 改行あり
リファレンス
特記すべき組み込みライブラリや標準ライブラリです。
整数
- gcd
- lcm
リスト
- delete-duplicates
シーケンスに関するライブラリ
(use gauche.sequence)
ベクターやリストなどのシーケンスに対してジェネリックに使えるライブラリです。
- map
- filter
- fold
- 部分適用
- map$
- fold$
- map-with-index
- など
ソート
- sort
リスト、ベクタ、文字列だけでなく、あらゆるシーケンス (<sequence>のインスタンス)をソートできます。
遅延シーケンス
遅延評価
- lrange (範囲)
遅延シーケンスユーティリティ
R7RS遅延シーケンス
(use gauche.lazy)
- lmap
- lfilter
- lfilter-map
- lconcatenate
- ltake
- ltake-while
- lslices
(use scheme.lseq)
- lseq-zip
エイリアス
エイリアス(自作含む)を紹介します。
lambda
(lambda (x) (+ x 1))
(^ (x) (+ x 1))
; 変数名が一文字であれば以下のように書ける
(^x (+ x 1))
アクセサ
万能アクセサ(~)です。
後述する自作エイリアスをよく使うのでこちらはあまり使わないですが便利です。
(vector-ref! v 1)
(vector-set! v 1 3)
(hash-table-get! t "a")
(hash-table-set! t "a" 3)
; それぞれ以下のように書ける
(~ v 1)
(set! (~ v 1) 3)
(~ t "a")
(set! (~ t "a") 3)
vector, hash-table
make-vectorやvector-set!などは長いので短くしました。
ClojureやScalaのベクターやハッシュマップは関数として振舞うので、そのような書き方ができると記述がスッキリします。
; vector
(define-inline mv make-vector)
(define-inline vs! vector-set!)
(define-method object-apply ((vec <vector>) (i <integer>) :optional fallback)
(vector-ref vec i fallback))
(vector-ref v i)
; は次のように書ける
(v i)
; hash-table
(define-inline mt make-hash-table)
(define-inline ts! hash-table-set!)
(define-method object-apply ((table <hash-table>) key :optional default)
(hash-table-get table key default))
(hash-table-get t k d)
; は次のように書ける
(t k d)
よく使う関数
目次
インクリメント
デクリメント
剰余
(define-inline (++ x) (+ x 1))
(define-inline (-- x) (- x 1))
(define-inline % remainder)
たまに使う関数
目次
ビット
丸め
キャスト
; bit
(define-inline << ash)
(define-inline & logand)
(define-inline lor logior)
(define-inline xor logxor)
; 丸め
; floorだけだと小数点数のままなので (exact (floor x)) が必要。
; この糖衣構文 floor->exactがある。 ceilも同様。
; それをさらに短く
(define-inline flint floor->exact)
(define-inline ceint ceil->exact)
; キャスト
; number->string
; x->integer
; string->number
(define-inline int x->integer)
パターンマッチ
パターンマッチは便利ですが、SchemeはHaskellやF#などと比べると少しめんどくさいです。
(use util.match)
(define factorial
(match-lambda*
[(1) 1]
[(n) (* n (factorial (- n 1)))]))
defnという名前で簡単に書けるようにしました。
(use util.match)
(define-syntax defn
(syntax-rules ()
((_ f expr ...)
(define f
(match-lambda* expr ...)))))
; (defn fac
; [(1) 1]
; [(n) (* n (fac (-- n)))])
遅延評価×部分適用
(use gauche.lazy)
(define (lmap$ f) (pa$ lmap f))
(define (lfilter$ f) (pa$ lfilter f))
優先度付きキュー、ヒープ
(use data.heap)
(define-inline mh make-binary-heap)
(define-inline hpush! binary-heap-push!)
(define-inline hpop-min! binary-heap-pop-min!)
(define-inline hpop-max! binary-heap-pop-max!)
(define-inline heapify build-binary-heap)
Deque 両端キュー、リングバッファ
(use data.ring-buffer)
(define-inline mdq make-ring-buffer)
(define-inline add-front! ring-buffer-add-front!)
(define-inline add-back! ring-buffer-add-back!)
(define-inline remove-front! ring-buffer-remove-front!)
(define-inline remove-back! ring-buffer-remove-back!)
その他便利ライブラリ リンク集
スタック、キュー
スタックはリスト、キューは上記Dequeで十分な気がします。
一応リンクは載せます。
- キュー: https://practical-scheme.net/gauche/man/gauche-refj/kiyu.html
- (スタック: なし)
組合せ
- combinations(組み合わせ)
- permutations(順列)
- power-set(べき集合)
- cartesian-product(直積、デカルト積)
トポロジカルソート
素数、素因数分解
自作ライブラリ
約数列挙
$\mathrm{O}(\sqrt{N})$になっています。(多分)
(use gauche.lazy)
(define (ldivisors n)
(lconcatenate
(lfilter-map
(lambda (i)
(cond
[(= n (* i i)) (list i)]
[(zero? (remainder n i)) (list i (exact (/ n i)))]
[else #f]))
(ltake-while
(lambda (i) (>= n (* i i)))
(lrange 1)))))
(define (divisors n :optional (sort? #t))
(let ([divs (ldivisors n)])
(if sort? (sort divs) (apply list divs))))
Counter
PythonのCounter的な
(use gauche.sequence)
(define (counter seq :optional (comp 'equal?))
(fold
(lambda (x col)
(hash-table-set! col x (+ 1 (hash-table-get col x 0)))
col)
(make-hash-table comp)
seq))
メモ化
(define (memoize f)
(let ([cache (make-hash-table equal-comparator)])
(lambda x
(or (hash-table-get cache x #f)
(let ([result (apply f x)])
(hash-table-put! cache x result)
result)))))
(define-syntax define-memo
; パターンマッチ
(syntax-rules ()
((_ f expr ...)
(define f (memoize
(match-lambda* expr ...))))))
; (define-memo fib
; [(0) 0]
; [(1) 1]
; [(n) (+ (fib (- n 1)) (fib (- n 2)))])
おわりに
やる気があれば随時更新します。