AtCoder 用 Haskell 逆引き (失敗編)
この記事は
Haskell 入門者あるあるをまとめたものです。
予備知識
- TLE: time limit exceed (時間制限超過)
- MLE: memory limit exceed (メモリ制限超過)
芝刈り・しばかれ
前提の import
です:
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
それではあるあるを挙げていきます。
1. HLS が動かない
エラー表示も、定義ジャンプも、型名表示すら無いままコンテストに挑みます。ひもじい気分を味わいます。
2. リストへのランダムアクセスで TLE
連結リストへのランダムアクセスは
xs !! i
xs VU.! i
3. 永遠に処理が戻ってこない (タイポ再帰)
Haskell では遅延評価ができます。再帰的な変数を作ってしまうと、制御が戻らなくなることがあります。
let xs = 3 : xs
in 0 : xs
let ys = 3 : xs
in 0 : ys
4. 永遠に処理が戻ってこない (無限リスト)
無限リストをフィルタリングすると無限リストが返ってきます。どこかで切り落としましょう。
filter (<= boundary) [1..]
takeWhile (<= boundary) [1..]
Vector.Unboxed
で 2 次元配列が持てない
5. 型が合わないときは謎のコンパイルエラーを食らいます。エラーメッセージの癖を掴みましょう。
mat <- VU.replicateM n getLineIntVec
mat <- V.replicateM n getLineIntVec
UArray
でタプルが持てない
6. 同上です。逆に Vector.Unboxed.Vector
でタプルが持てるのは、内部的に Vector
2 本になるためです。
table <- newArray @IOUArray bounds_ (0, 0)
table <- newArray @IOArray bounds_ (0, 0)
7. Boxing により MLE
テーブルサイズの大きな DP で起きました。 Unboxed なデータ型を使いましょう。また DP では遅延評価に頼らないようにしましょう。
table <- newArray @IOArray bounds_ e0
table <- newArray @IOUArray bounds_ e0
NPlusKPatterns
でエラー
8. 言語拡張 言語拡張を有効にして ghci
を起動します:
$ ghci -XNPlusKPatterns
Prelude>
一見 N + K パタンは問題なく動きます:
Prelude> let x = 1
Prelude> let (n + 1) = x
Prelude> n
0
しかし n
が負の数になるとエラーが発生します:
Prelude> let x = 0
Prelude> let (n + 1) = x
Prelude> n
*** Exception: <interactive>:2:5-15: Non-exhaustive patterns in n+1
使わないほうが無難かもしれません。
runST
の中から複数の値を返せない
9. ST (state thread) モナドの範囲で別の変数を書き換えようとして失敗しました。モナドをほぼ理解していなかった頃ですね。
対策としては、
- モナドを合成する
- それぞれの可変変数を IO モナドに入れる
- 『別の変数』は
foldM
のループで更新する
Unbox
を実装できない
10. 昔の vector
は Unbox
の実装が異様に難しいです。そのため他のパッケージを頼るのが無難です。
-
vector
の代わりに unboxing-vector を使う
Sum type に対してはUnboxable
を実装できない 点は留意します。 -
vector-th-unbox を使う
Template Haskell でコード生成します。
-- vector-th-unbox: https://www.stackage.org/lts-16.11/package/vector-th-unbox-0.2.1.7
import Data.Vector.Unboxed.Deriving (derivingUnbox)
newtype UnionFind = UnionFind (VU.Vector UFNode)
-- | `Child parent | Root size`
data UFNode = UFChild {-# UNPACK #-} !Int | UFRoot {-# UNPACK #-} !Int
_ufrepr1 :: UFNode -> (Bool, Int)
_ufrepr1 (UFChild x) = (True, x)
_ufrepr1 (UFRoot x) = (False, x)
_ufrepr2 :: (Bool, Int) -> UFNode
_ufrepr2 (True, x) = UFChild x
_ufrepr2 (False, x) = UFRoot x
derivingUnbox "UFNode" [t|UFNode -> (Bool, Int)|] [|_ufrepr1|] [|_ufrepr2|]
終わりに
自力で Haskell が書けなくて挫折感を味わいました。今でも型関連のエラーが直せないときは質問します。 AtCoder に絞っても相当難しい言語なので、完全な習得には年単位で時間が必要なのではないかと思います。
その分だけ得るものは多いと感じています。快適な AC を!
Discussion