2011-12-25
■[Scheme][Gauche][あなごる] Scheme golf tips
あなごる用
Haskell golf の教科書を読んで「俺もこういうの書きたい！」と思って書いてみた．(思ってから書くまでに1年くらい経ってるけど)
アマチュアゴルファーなので至らぬ所もありありだけど，今後のScheme界とあなごる界の盛り上がりを願ってこの文章を公開する．
(教科書を参考にさせていただきました．)
危険なので golf 以外では真似しないで下さい！
あなごるの基本
- 余計な空白は除去
- 改行はLF
- エラーで止めてよい
- 出力の末尾に余計な空白，改行があっても構わない
Scheme(Gauche) golfの基本
よく使うのは 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! とかは #<undef> を返すようなので都合よく縮んだりしない．最初から使える一文字の識別子には ^ や ~ がある． ^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)
と書ける．
2011-12-21
■[Scala]Scalaでidを書こうとした
最初，無名関数で書こうとしたら，どうすれば多相的になってくれるのかわからなくて，ぐぐってたら名前を付ければいいということだった．
ところが，
scala> def id[T](x: T) = x id: [T](x: T)T scala> id _ res0: Nothing => Nothing = <function1> scala> (id _)(42) <console>:9: error: type mismatch; found : Int(42) required: Nothing (id _)(42) ^
( ﾟДﾟ)
(追記 12/23 11:59)
scala> ((identity _):Int => Int)(42) res8: Int = 42 scala> (((identity _):(Int => Int) => (Int => Int))(identity _))(42) res9: Int = 42
型を書けば動く．手前に書いた場合は推論してくれる．
2011-10-06
■[Scheme][Gauche]Gaucheで素数ストリーム
エラトステネスの篩
(define (divisor? x y) (eqv? 0 (remainder x y))) (define-constant +primes+ (stream-cons 2 (stream-filter prime? (stream-iota -1 3 2)))) ;; (define (prime? n) ;; (not (stream-any (cut divisor? n <>) (stream-take-while (cute >= (sqrt n) <>) +primes+)))) (define (prime? n) (let1 limit (sqrt n) (let loop ((srm +primes+)) (let1 x (stream-car srm) (or (< limit x) (if (divisor? n x) #f (loop (stream-cdr srm)))))))) ;(time (stream-ref |+primes+| 10000)) ; real 0.868 ; user 0.840 ; sys 0.020 ; => 104743
stream-take-while を使った版は 5.132s かかった．
Gaucheでエラトステネスの篩で素数ストリーム(世間一般のやつより速い) - Gemmaの日記 のと比較してみたら，向こうのは 7.792s かかったのでこちらの方が大分速い．
でもこれを Haskell に移植して Haskell 版で比較すると 0.179s と 0.123s で向こうの方が速かった．
ところが，-O つけてコンパイルするとどちらも 0.104s くらいで同じになった…
takeWhile を使うと 0.695s と遅くなっていたのが -O 付きでは 0.078s と一番速くなった．
HaskellのtakeWhile展開版
primes = 2 : filter isPrime [3,5..] {- isPrime n = not $ any (isDivisor n) $ takeWhile (limit >=) primes where limit = floor $ sqrt $ fromIntegral n -} isPrime n = loop primes where loop (x:xs) | limit < x = True | isDivisor n x = False | otherwise = loop xs where limit = floor $ sqrt $ fromIntegral n isDivisor n m = rem n m == 0 main = print $ primes !! 10000
2011-09-05
■[Scheme]「F#をまねる」をまねる
F# の |> 演算子がかっこよいので、Haskell で作ってみた。
infixl 0 |> (|>) :: a -> (a -> b) -> b a |> f = f a以下のようにシェルのパイプのような感じで使う。
foo :: String foo = [1..100] |> map (*2) |> filter (\x -> x `mod` 6 == 0) |> sum |> showhttp://d.hatena.ne.jp/kazu-yamamoto/20110218/1297992233
(define-syntax >> (syntax-rules () ((_ value) value) ((_ value (proc args ...) expr ...) (>> ((cut proc args ... <...>) value) expr ...)))) (define-syntax >>* (syntax-rules () ((_ value) value) ((_ value (proc args ...) expr ...) (>>* (call-with-values (lambda () value) (cut proc args ... <...>)) expr ...))))
名前は適当，>>*は多値対応版だけどGaucheでは遅くなってしまった．気にする所じゃなさそうだけど．
使い方は
(>> (iota 100) (filter odd?) (map (pa$ * 2)) (fold + 0)) ; => 5000 (>> (iota 100) (filter odd?) (map (pa$ * 2)) (take <> 10)) ; => (2 6 10 14 18 22 26 30 34 38) (>>* (values 7 2) (quotient&remainder) (+)) ; => 4
(追記6:46)
@dico_leque さんにGaucheではcall-with-valuesよりreceiveの方が少し速いと教わったので書いてみた．速くなった．Gaucheではreceiveの方がプリミティブでcall-with-valueはただの手続きとのこと．
(define-syntax >>+ (syntax-rules () ((_ value) value) ((_ value (proc args ...) expr ...) (receive vars value (>>+ (apply (cut proc args ... <...>) vars) expr ...)))))
名前はますます適当である．
Gauche 0.9.2 で計測．コード適当だけど受け渡し部分を計りたいんだからこれでいいよね？
;(time (dotimes (_ 100000) (>> 1 (+ 2) (+ 3) (+ 4) (+ 5) (+ 6) (+ 7)))) ; real 0.231 ; user 0.220 ; sys 0.000 ;(time (dotimes (_ 100000) (>>* 1 (+ 2) (+ 3) (+ 4) (+ 5) (+ 6) (+ 7)))) ; real 0.395 ; user 0.380 ; sys 0.010 ;(time (dotimes (_ 100000) (>>+ 1 (+ 2) (+ 3) (+ 4) (+ 5) (+ 6) (+ 7)))) ; real 0.341 ; user 0.330 ; sys 0.000
(追記19:53)
(define-syntax $> (syntax-rules (=>) ((_ value) value) ((_ value => proc expr ...) ($> (proc value) expr ...)) ((_ value (proc args ...) expr ...) ($> ((cut proc args ... <...>) value) expr ...))))
($> 3 => (^x (+ x x)) (- <> 1)) ; => 5