正格フラグ、バンパターン、正格版関数・データ構造

Haskellスペースリーク Advent Calendar 2015 9日目

Haskellerとて、時には厳しくならなければいけないこともある―― @fumieval, 2015

Haskellは遅延評価を基本としているため、場合によっては未評価の式が積もり非効率な状況に陥ることがある。これを防ぐため、部分的に正格評価にするための仕組みが用意されている。もちろんこれらは闇雲に使えばよいというものではない。使うべきポイントを把握し、これらを見逃さないようにしよう。

この記事では、それらの機能の正しい使い方、間違った使い方を紹介していこう。

カウンター・カウンターズ・サンクス

条件を満たす要素の個数とそうでない要素をそれぞれカウントするプログラムについて考える。アキュムレータ(ループの中で積み上げていく変数)は正格にしないといけないらしいので、BangPatterns拡張を使ってみた。どんなパターンでも、感嘆符をつけることによってあらかじめ評価を強制できるすごい拡張機能だ。

{-# LANGUAGE BangPatterns #-}

data Counter = Counter Int Int

count :: (a -> Bool) -> [a] -> Counter -> Counter
count p (x:xs) !(Counter m n)
   | p x = count p xs (Counter (m + 1) n)
   | otherwise = count p xs (Counter m (n + 1))

残念ながらこれは意味がないどころか、スペースリークを解決できていない。というのも、countに渡しているのはCounterのコンストラクタ、つまり評価する必要のない値である一方、Counterの中身にはサンクが溜まってしまっているからだ。コンストラクタではなく、中身にバンパターンをつけよう。

{-# LANGUAGE BangPatterns #-}

data Counter = Counter Int Int

count :: (a -> Bool) -> [a] -> Counter -> Counter
count p (x:xs) (Counter !m !n)
   | p x = count p xs (Counter (m + 1) n)
   | otherwise = count p xs (Counter m (n + 1))

データ型のフィールドのほうに感嘆符をつけると、そのフィールド自体が正格になる。こちらは拡張いらずで、関数定義にいちいちバンパターンをつけなくてもよいので便利だ。

data Counter = Counter !Int !Int

count :: (a -> Bool) -> [a] -> Counter -> Counter
count p (x:xs) (Counter m n)
   | p x = count p xs (Counter (m + 1) n)
   | otherwise = count p xs (Counter m (n + 1))

遅延評価を含めた意味論にこだらわないのなら、すべてのデータ型のフィールドを正格にするのが無難な選択だろう。

data Maybe' a = Nothing' | Just' !a

instance Functor Maybe' a where
    fmap f (Just' a) = Just' (f a)
    fmap _ Nothing' = Nothing'

この正格版Maybeは、fmapしても中身にサンクが溜まらないのでいいことずくめに見えるが、fmapが厳密には則を満たさなくなってしまうという欠点がある。fmap id (Just undefined)はJust undefinedと等しいが、fmap id (Just' undefined)はundefinedになってしまう。

もっとも、日常ではここまで気にしなければいけない場面は少ないので、ほとんどの場合は気にせず感嘆符をつけて大丈夫だろう。GHC 8.0からは、全フィールドをデフォルトで正格にするStrictDataという拡張が入るため、こちらを使おう。

Strictに早合点

Lazyだとトラブルを起こしやすいということで、「正格版」の関数やデータ構造を提供している場合もある。Data.Map.Strictはその一例だ。

import Data.Map.Strict

data AppState = AppState {
   ...
   buzz :: Map (Int, Int) Int
   ...
   }

しかし、Strictがついているからといって油断してはいけない。このAppStateにおけるbuzzを繰り返し更新するとスペースリークが発生する。実はモジュール名のStrictが意味するのは、挿入時などに要素(Int)が評価されるというだけで、Map全体は正格にはなってくれないのだ。やはりフィールドは正格にする必要がある。

import Data.Map.Strict

data AppState = AppState {
   ...
   buzz :: !(Map (Int, Int) Int)
   ...
   }

関数適用を伴って更新する値は正格にしておこう。これさえ守っていればまずスペースリークは発生しない。