Haskell Golf 入門
この発言
@dekosuke なんか 僕は最近全然 Haskell ゴルフをしていなくて腕が衰えていて悲しいので、 @notogawa さんあたりが解説記事を書いてくれないかと期待しています! [石持浅海先生講演会 11/6(土) URL ]
2010-10-07 20:18:44 via YoruFukurou to @dekosuke
書きつつ思ったが,こんなものでよいのだろうか?これらの前に一段あるような気がする.
とりあえず注意書きを書いておくかー.
このエントリはHaskell入門ではありません.普通にコーディングする場合,あんまり真似しないほうが良いです.
(anarchy) golfの基本
- 余計な空白は除去(Haskellは関数適用があるので割と空白があるほう)
- 改行はLF
- エラーで止めてよい
Haskell Golf 特有の基本
- modulesとか書かない
- 曖昧とか怒られるまでType Signatureとか書かない
- とにかくまずは適当に書いてプログラム運算していく
- 削って答えを作るより足して作るほうが安いことが多い
- パターンマッチよりコンストラクト
- divより(*)
- take/dropより(++)
- 他の言語よりgcdが安いので素数・整数系の解き方が少し違うことがある
- scan/foldを制するものゲームを制す…ことが稀によくある
- モナドは(>>=)でつなげるかdo記法にするかは状況依存
- 通常は(>>=)が安い
- 複製する,内包表記の中で使う,など一旦何か記号に落とす必要があるならdo記法(ミス修正thx @1to100pen)
[1..n]>>=f;f x=[x,x] [1..n]>>= \x->[x,x] do x<-[1..n];[x,x]
- returnを書かずに済むようにすべき
- if/case式は使わない
- ifの書き替えは後述
- 関数のパターンマッチで分岐させる
- 前後に置く空白の関係上使うならlet-inよりwhere
- importは高いのできるだけしない
- それでもよくimportすることになるのは…
- List (sortが必要だったりすると)
- Numeric (基数変換が必要だったりすると)
- Text.Printf (整形が必要だったりすると)
入出力
入力全体を処理に使う問題
main=interact f
一行毎に入出力を行って済む問題なら
main=interact$unlines.map f.lines
となるが,これよりエラー止めでよいならこっちのほうが短い,
main=getLine>>=putStrLn.f>>main
さらにasパターンを利用して次の形までいける.
m@main=getLine>>=putStrLn.f>>m
ただし,処理の中で行末改行の付与が安く可能であれば,
main=interact$(>>=f).lines
に有利が付く.
他,入出力がらみのよくある変換は,
getLine>>=f.read readLn>>=
putStrLn.show
print
putStr.unlines
mapM putStrLn
ifの変換
まず基本
if p then a else b last$b:[a|p]
よくあるケース1
if 0<x then a else b last$b:[a|0<x] [a,b]!!(0^x) -- xがIntegralで非負ならば a+(b-a)*0^x -- a,bがNumならば
よくあるケース2
if p then xs else[] [x|p,x<-xs]
再帰
基本は遅延評価で無限に回してtakeで欲しいだけ取る,もしくは,(!!)で取る.
take 10z;z=0:z
規定数再帰して止めるなら,エラー止めでいいならパターンマッチ失敗させる.
f(a:x)=print a>>f x -- []になったら停止 f(n+1)=print n>>f n -- 0になったら停止
停止条件まで入れるならパターンマッチの記述順で短かくなることがある.
f[]=[];f(a:x)=g a:f x f(a:x)=g a:f x;f x=x -- 型が変わらない場合
融合変換
map/map fusion
map f.map g map(f.g)
foldr/map fusion
foldr f e.map g foldr(f.g)e
scanrも同様
scanr f e.map g scanr(f.g)e
Hylomorphism
foldr f e.b;b x|p x=[]|0<1=x:b(h x) g;g x|p x=e|0<1=f x$g(h x)
その他よくある変換
Trueの置き替え
otherwise True 0<1
リストモナドは有効に使う.
concat.map f concatMap f (>>=f)
xが非負のとき以下の変形ができるがxが大きいとtimeoutの危険がある.
[1..n]!!mod x n cycle[1..n]!!x
何かの条件でソートする時はsortByは案外弱い
sortBy(\a b->f a`compare`f b);f x=expr sortBy((.f).compare.f);f x=expr map snd.sort.map(\x->(expr,x))
最後の形にしておくと,さらに前後の処理と融合できたりするのでなおさら辛い.
mapM print.sortBy((.f).compare.f);f x=expr mapM(print.snd).sort.map(\x->(expr,x))
filterは単体ではリスト内包表記より有利だが,
filter p xs [x|x<-xs,p x]
他の処理と合成すると大概不利になる.
map f.filter p xs [f x|x<-xs,p x]
lengthは前処理如何ではsumに置き換えたほうが短いことがある.
length xs sum[1|x<-xs] length$filter p xs sum[1|x<-xs,p x]
リスト内包表記とwhereを使う場合内包表記内のみで済ませることができる.
f x=[g a|a<-xs,g a]where g a=expr x a f x=[a|a<-xs,a<-[expr x a],a] --なんかうまくないな
replicateはたぶんいらない子.
replicate n x [1..n]>>[x]
単体のtakeWhile/dropWhileはspanで.
takeWhile p fst.span p dropWhile p snd.span p
一定個数以上の文字列リテラルのリストが必要な場合,可能ならばひとつに連結しておいてwordsやlinesで切る.
["a","b","c"] words"a b c"