Scheme golf tips

Scheme Gauche あなごる

あなごる用
Haskell golf の教科書を読んで「俺もこういうの書きたい！」と思って書いてみた．(思ってから書くまでに1年くらい経ってるけど)
アマチュアゴルファーなので至らぬ所もありありだけど，今後のScheme界とあなごる界の盛り上がりを願ってこの文章を公開する．
(教科書を参考にさせていただきました．)


危険なので golf 以外では真似しないで下さい！

あなごるの基本

  • 余計な空白は除去
  • 改行はLF
  • エラーで止めてよい
  • 出力の末尾に余計な空白，改行があっても構わない

Scheme(Gauche) golfの基本

  • とにかくまずは適当に書いてプログラム運算していく
  • 他の言語よりgcdが安いので素数・整数系の解き方が少し違うことがある
  • use はしない方が短いことも多い

よく使うのは srfi-1，特に iota．
srfi-1 で簡単に書けても書き下した方が短いこともあるので，とにかくいろいろ書いてみることが重要

S式の短縮記法を活用する

(quote x)
'x

(list x y)
`(,x,y)

(dotimes(i 10)(print'hoge)
(dotimes,10(print'hoge))

(dotimes(i 10)(print(+ i 1))
(dotimes,10(print(+ . ,1)))
(dotimes,10(print(+ .,1))) ; 0.9.2以降

(let((f proc))(f x)(f y))
(let('proc)'x'y)

Gauche0.9.1ではunquoteを束縛してもquasiquote中のunquoteは動くので安心して使える．

(let(,print)`(,(list 1 2 3))) ; => ((1 2 3))

(修正 12/26 8:29)
安心して使えないバグが判明．

(let (,1 (x 2)) `(,x)) ; => 2

そもそも上記のようにunquoteが使えてしまうのがバグなので，最新の開発版ではquasiquote自体が健全なように修正された．

(let (,1) `(,(+ 1 2))) ; => (,(+ 1 2))

共有構造(SRFI-38)

(print(read-line)(read-line))
(print #0=(read-line)#0#)

generic function や短縮名を活用する

^ ~ .$ は Gauche 0.9.1 から．
^ は lambda の短縮名．

(lambda(x y)...)
(rec(_ x y)...)
(^(x y)...)

場合によってはさらに

(^'y ...)

(lambda(x)...)
(rec,x ...)
(^x ...)

let1 よりも短くなる．

(let1 x(foo)(bar x))
((^x(bar x))(foo))

~ は ref* の短縮名で， ref* は ref のネストをまとめたもの． ref は list-ref や vector-ref のgeneric版．

(list-ref l i)
(ref l i)
(~ l i)

(ref(ref l i)j)
(~ l i j)

.$ は compose の短縮名．

(map f(map g l))
(map(.$ f g)l)

その他

(string->number s)
(x->number s)

文字列はシンボルで代用できることがある

(print"hoge")
(print'hoge)

'("foo""bar""baz")

もシンボルでよければ

'(foo bar baz)

string-interpolation

文字列の構成はこれか format ですることが多い．

(x->string x)
#`",x"

共有構造はread単位でしか共有されないため，

#`",#0=x,#0#"

とはできない．

正規表現と object apply

文字列処理手続きは string- がついて高いので，なるべく正規表現+object applyで済ませる．
文字列の分解は大体これでやる．

(substring x 1(-(string-size x)1))
((#/.(.*)./x)1)

(string-copy x 1)
((#/.(.*)/x)1)

set!の返り値

(現在の)Gaucheでは(多分)，R5RS形式の set! は代入される値を返す．SRFI-17形式の set! は setter が返す値を返す． vector-set! とかは # を返すようなので都合よく縮んだりしない．最初から使える一文字の識別子には ^ や ~ がある． ^x がとても安いので使う機会は減ったが，空白の関係で縮むことがある．
anarchy golf - NABEATSU of the world

順次実行

順次実行する時は大体 print とかなので ， begin は if や and で代用できる．

(begin(print x)x)
(if(print x)x)

(begin(print x)(set! y z)x)
(and(print x)(set! y z)x)   ; z が #f でないとき

分岐

他言語と違って普通に if or and が安い．cond や case もたまに使う．
文字は(Gaucheでは) eq? で比較できるが，数で扱えば = で比較できる．
文字列化して正規表現でマッチするかどうか調べると縮む場合がある．
null? よりは eq?() ．Gaucheでは () はquoteしなくても動く．

(null? l)
(eq?()l)

入力

read で済むなら read ．文字単位の処理は read-char か read-byte ．
たまに read-block も使うが，これは incomplete string を返すので使いにくい(正規表現やrefが使えない)ので気をつける．

出力

基本は print ．リストを出力する場合，(apply print ...)の形も有効．
文字列の構成は #`"..." か format が多い．

再帰/ループ

(for-each(^x ...)l)
(map(^x ...)l)

for-each は勿論使わない．

(while(read-line)=> x ...)
(port-map(^x ...)read-line)

(while(read-line)...) はエラー止めが必要なので，できない場合は port-map を使う．
束縛する必要がなければ

(while(print(~(read-line)0)))

等．

入力に対するループはdo dotimes rec while until port-map port-fold等，選択肢が多い．
目安は (修正 1/17 17:58)

  • ただの反復は while か port-map
  • 入力に対する反復で状態変数を一つ持つ場合は rec
  • 入力に対する反復で状態変数を一つ持ちつつエラー止めできない場合は port-fold
  • 綺麗に当てはまるものがなければ do

do は

(do('car,cdr`print(x 1)(i 0(+ i 1)))(#f)...)

といろいろできるので強い．
整数に対する繰り返しは dotimes や iota，srfi-42 を使う場合と，他のループと inc! dec! を合わせて使う場合がある．

入力を一度リストにしたい時は

(port-map(^x x)read-line)

となるが，+ や * が一引数の時に引数をチェックせずそのまま返すので

(port-map + read-line)

と書ける．