Haskell競技プログラミング入門

最近HaskellでAtCoderとかProject Eulerとか解いたりして学んだことのまとめ。

# 入出力
入力の形式はだいたい決まっているのでいつもこれを書く。

```hs
import Control.Applicative

main = do
  -- "L M N" ---> [L,M,N]
  n <- fmap (read :: String -> Int) . words <$> getLine
  -- 複数行バージョン
  ns <- fmap (fmap (read :: String -> Int) . words) . lines <$> getContents
```

出力は場合によりけり。

```hs
import Text.Printf

main = do
  printf "%04d" 10 -- 4桁0詰め
  mapM_ print [1,2,3] -- リストの中身を1行ずつ出力
```

# データ構造
普通にアプリケーション作っているときは気にしなかったけど、競プロだと時間がないとかドキュメント読んでる場合じゃないとかオンラインジャッジの環境が古いとかいう理由でデータ構造の選択にはほとんど余地がないことが多い。
自分の場合はだいたいこう：

- 速度にこだわらない/先頭への追加しかしない: `List`
- メモ化再帰のメモ: `Array`使う人が多いけど`IntMap`でも別にいいんじゃない？(と個人的には思っている)
- それ以外(ランダムアクセス・挿入・削除・優先度付きキューを使いたい)： `IntMap`

ABCとかだと実際`List`と`IntMap`くらいあれば十分なことが多い印象。他の言語でアルゴリズムとかを学んだことがあって、そういうアルゴリズムを使いたいから「破壊的代入がしたい」みたいな人がいれば`MArray`とか`IOArray`とか使えばいいんじゃないですかね。私がそういうのを全く知らないのでIOなしでも困ってないというだけかも。

# 実装

個人的によく使うのは以下の3つの実装

- 全探索(+枝刈り)
- DP
- メモ化再帰

## 全探索+枝刈り
普通に再帰。ガードが便利。問題によってはこれで十分。

```hs
solve = iter 0 where
  iter n
    | f n == True = False
    | otherwise = iter ...
```

## DP
終了条件付きのアルゴリズムでDPしたいときは`unfoldr`で大体なんとかなる(なんとかならない難しい問題もあるけど)。ある操作をn回繰り返したときの値が欲しい(予めnがわかっている時)は`iterate`や`scanl`で十分なこともある。

```hs
import Data.List

solve = head $ unfoldr next b where
  next :: b -> Maybe (a,b)
  next n
    | f n == True = Nothing -- 終了条件のところでNothing
    | otherwise = Just (a,n') -- aが答え, n'はnの次の値
```

## メモ化再帰
最近は`unfoldr`がお気に入りなのであんまりメモ化再帰はしなくなったけど、たまに使う。
メモ化には(標準パッケージに入っているという理由で)`Data.Array`がよく使われている印象。

```hs
import Data.Array

solve n = iter i where
  memo = listArray (0,n) $ fmap iter $ [0..n]

  iter 0 = False
  iter i = f $ memo ! i
```
`memo`を作っておいて、`iter`の中では`iter i`の代わりに`memo ! i`とすることでメモ化された値を参照してくれる。
何も考えずに再帰を書いてしまい、「やっぱメモ化するかー」となったときには書き換える範囲が少なくて済むのが利点。

# 実装例
### フィボナッチ数

```hs
fib n = fst $ iterate (\(a,b) -> (b,a+b)) (1,1) !! n
```

### 素数列
エラトステネスじゃないので注意。めっちゃ速くはないけどめっちゃ遅くもないので大体これ。

```hs
primes = 2:3:[x|i<-[1..], j<-[-1,1], let x = 6*i+j, isPrime x] where
  isPrime n = null [i|i<-takeWhile (\x -> x*x <= n) primes, rem n i == 0]
```

## 組み合わせ数(combination)
パスカルの三角形を使う。`n,r`がかなり小さくて下の実装が思いつかなければ`product [n-r+1..n]/product [1..r]`でもいいけれど。

```hs
comb n r = iterate (scanl1 (+)) [1,1..] !! (n-r) !! r
```
## Collatz数列
普通に`unfoldr`。
`fmap collatz [1..n]`の最大値を求めるような問題で`n`が十分大きい時は適当にメモ化した方がいいかも。

```hs
collatz n = unfoldr next n where
  next k
    | k == 0 = Nothing
    | k == 1 = Just (k,0)
    | k `mod` 2 == 0 = Just (k,k `div` 2)
    | otherwise = Just (k,3*k+1)
```

# Tips
知ってると微妙にお得な感じ。

### ペアのリストをソート
`Ord a => [(a,b)]`を`a`の値をキーにしてソートしたい

```hs
import Data.Function (on)
-- on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

sortBy (compare `on` fst) ...
sortBy (comparing fst) ...  -- これも同じ
```

### 辞書順ソート
`(Ord a,Ord b) => Ord (a,b)`というinstanceがあって、辞書順になるように定義されているので辞書順ソートしたかったらとりあえずタプルのリストにしてしまう。

### 順列と組み合わせ
ただの順列。

```hs
import Data.List

-- ["abc","bac","cba","bca","cab","acb"]
permutations "abc"
```

重複ありの、長さrの部分リストの順列。最初に見た時は覚えておくと便利そうだなと思ったけど今まで役に立ったことがない。

```hs
import Control.Monad

-- ["aa","ab","ac","ad","ae","ba","bb","bc","bd","be","ca","cb","cc","cd","ce","da","db","dc","dd","de","ea","eb","ec","ed","ee"]
replicateM 2 "abcde"
```

部分リストの組み合わせはこう。

```hs
import Data.List

-- ["","a","b","ab","c","ac","bc","abc"]
subsequences "abc"
```