Haskell Golf 入門

Haskell Golf

この発言

を受け，ちょっとまとめてみようかと，とりあえず思い付きをつらつらと書いてみる．

書きつつ思ったが，こんなものでよいのだろうか？これらの前に一段あるような気がする．

とりあえず注意書きを書いておくかー．
このエントリは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"