Haskellのseqについて

Haskellの計算は遅延評価なので,気軽にループを書くとスペースリークに悩まされることがある. 人はseqを使えというが, 初心者からするとその挙動が結構トリッキーで何度も苦しめられた.

ので,整理してみる.

小手調べ

まずは評価戦略の整理から.:sprintコマンドで評価済みの値を表示できる.

何もしなければ一切評価されない.

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> x = [1, 2, 3] :: [Int]
Prelude> :sprint x
x = _

必要な部分だけが評価されていく. 今回はGHCiの画面表示で評価をコントロールする.

Prelude> last x
3
Prelude> :sprint x
x = [_,_,3]

ちょっとしたトラップ.各要素は前の要素+1で生成されるので,最後を評価する過程で途中も評価されている.

Prelude> x = [1 .. 10] :: [Int]
Prelude> last x
10
Prelude> :sprint x
x = [1,2,3,4,5,6,7,8,9,10]

seq関数

seq a bは値としてはbを返すが,評価戦略としてaの評価をbの評価の前に挟むことができる.

Prelude> x = 1 :: Int
Prelude> seq x ()
()
Prelude> :sprint x
x = 1 -- 直接表示せずともseq越しにxが評価される

「前に挟む」というのがポイントで,seq a b自体が評価されなければaは(ましてやbも)評価されない.seq a bをコード上に書くだけではaを評価できないことに注意しよう*1

Prelude> x = 1 :: Int
Prelude> _ = seq x () -- 代入するだけで評価はしないでおく
Prelude> :sprint x
x = _ --- 評価されていない

二つ目の注意点.seqの評価は浅い. 代数的データ型のインスタンスはコンストラクタまでしか評価されない*2

Prelude> x = [1, 2, 3] :: [Int]
Prelude> seq x ()
()
Prelude> :sprint x
x = _ : _ -- Listの場合は`(_:_)`か`[]`なのかが判明する

深く評価するには

深く評価する際にはdeepseqというライブラリ(関数名でもある)を使うと良さそう.

Prelude Control.DeepSeq> x = [1, 2, 3] :: [Int]
Prelude Control.DeepSeq> deepseq x ()
()
Prelude Control.DeepSeq> :sprint x
x = [1,2,3]

役に立つかはわからないが,深めのseqを自分で書くこともできる.

eval :: [a] -> ()
eval [] = ()
eval (x:xs) = x `seq` eval xs

この場合,evalの返り値を評価すれば、引数のリストを深さ1まで評価できる.

Prelude> x = [[1, 2], [3, 4], [5, 6]] :: [[Int]]
Prelude> eval x
()
Prelude> :sprint x
x = [(_ : _),(_ : _),(_ : _)]  -- 途中まで評価されている

以上.

*1:ただの関数にはそんなことはできない(と思う).マクロの範疇である.

*2:より一般にはweak head normal form (WHNF)まで評価される,らしいが意味はよくわかっていない.

HaskellでProject Euler #51

List comprehensioが便利だった.ideoneで<0.3secぐらい.

import           Data.List

-- PE #51
main :: IO ()
main = do
  let n = 8
  -- Suffice to check (11 - n) digits for n primes families
  let chars = take (11 - n) "0123456789"
  let primes = 2 : filter isPrime [3, 5 ..]
  let cands =
        [ variants
        | p <- primes
        , let repr = reverse (show p)
        , let idxMax = length repr - 1
        -- Do not alter ones digit
        , let places c = map fst . filter ((== c) . snd) . tail $ zip [0 ..] repr
        , c <- chars
        , idxs <- filter (not . null) $ subsequences (places c)
        , let variants =
                [ num
                | d <- [0 .. 9]
                -- Do not put zero in the first digit
                , d > 0 || maximum idxs < idxMax
                , let num = replaceDigits p idxs d
                , isPrime num
                ]
        ]
  let answer = head . filter ((== n) . length) $ cands
  print answer

isPrime :: Int -> Bool
isPrime q = q >= 2 && all notFactorOfQ (2 : [3, 5 .. s])
    where
      notFactorOfQ = (/= 0) . mod q
      s = ceiling $ sqrt (fromIntegral q :: Double)

replaceDigits :: Int -> [Int] -> Int -> Int
replaceDigits n [] _ = n
replaceDigits n (i:is) d = let
  unit = 10 ^ i
  d0 = (n `mod` (unit * 10)) `div` unit
  n1 = n + unit * (d - d0)
  in replaceDigits n1 is d

HaskellでProject Euler #11

tailsの使い方の勉強になったのでメモ.

tailsが特別便利と言うよりは,Haskellにはfor文とかwhile文などの繰り返し構文がないので,そもそもiterate系全般がありがたいっぽい. 他にData.List特有のiterate系関数としては,subsequences, permutations, nub(重複排除)あたりが使えそうだと思った.

import           Data.List

main = do
    let array = map (map read . words) $ lines input :: [[Int]]
    -- 候補の列挙
    let horiz = concatMap parse4 array
    let vert = concatMap parse4 (transpose array)
    let diag = parseD4 array
    let adiag = parseD4 (reverse array)
    -- 探索
    let answer = maximum . map product $ vert ++ horiz ++ diag ++ adiag
    print answer

-- リスト中の連続する4要素を組にして列挙
parse4 :: [a] -> [[a]]
parse4 xs = let
    ys = map (take 4) (tails xs)
    in takeWhile ((== 4) . length) ys

-- 二重リスト中の対角方向に連続する4要素を組にして列挙
parseD4 :: [[a]] -> [[a]]
parseD4 arr = let
    squares = concatMap (parse4 . transpose) (parse4 arr)
    in map takeD squares

-- 正方行列の対角要素を抜き出す          
takeD :: [[a]] -> [a]
takeD ((x:_):xss) = x : takeD (map tail xss) 
takeD _ = []

input = "\
\ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\
\ 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\
\ 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\
\ 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\
\ 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\
\ 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\
\ 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\
\ 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\
\ 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\
\ 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\
\ 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\
\ 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\
\ 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\
\ 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\
\ 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\
\ 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\
\ 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\
\ 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\
\ 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\
\ 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"

理想のプログラミング言語と副作用

副作用

最近思うに,プログラミングの「副作用」という用語は結構ミスリーディングだ.

確かに副作用を持つコードはバグの温床になりやすいと言うしその実感もあるけど,じゃあ副作用なんてやめて全部主作用にしよう,全部引数と戻り値に書いちゃおう,とはならない. それはおそらく,ある程度大きいプログラムになってくるとすべての情報のやり取りを明示的に書くのが面倒だし,読む方も大変だからだ.

その辺「副作用」なら暗黙的に事を済ませられるのでありがたい. つまり,それは薬の副作用と違って,扱いにくいけれど必要なものだ.

PythonHaskell

ところで,オブジェクト指向や関数型といったプログラミングパラダイムは副作用をストレスフリーに扱うための技術とみなすこともできる.

例えば,オブジェクト指向的なPythonでは関数の代わりにメソッドを利用する.このときオブジェクト指向によれば,副作用のスコープを各メソッドの紐付くオブジェクト(self)内に限定しなければならない.こうすることで副作用の及ぶ範囲がコントロールされ,バグの特定が簡単になったりする.

一方,純粋関数型言語と呼ばれるHaskellでは,副作用を明示的に表現する. と言っても,ただ副作用の情報をどこかにベタ書きするのではなく(それでは副作用の暗黙性が失われてしまう),副作用の種類に応じて用意されているモナドを利用する*1.これによって,すべての副作用は暗黙的でありながらコンパイラのチェックを受けることができるので,バグが減る.

こんな観点から眺めると,2つの対立させられがちなパラダイムが目指す共通の方向性が見えてくる気がする.

理想のプログラミング言語

やっと本題に入るわけだが,個人的な理想のプログラミング言語の要件として, ストレスフリーに副作用を扱えること,というのがある. 上に挙げたPythonHaskellは自分が触ったことのある範囲で一位二位を争う好きな言語だが, どちらにしてもまだ惜しいところがあると思う.

HaskellからPythonを見ると,スコープ以外無差別に副作用を扱おうというのはちょっと無謀だし,コードを読む側やドキュメントをメンテするコストもバカにならない.最近はtypingモジュールも導入されて型検査はしやすくなっているが,副作用の型付けにはまだ程遠そうに思われる.

一方で,PythonからHaskellを見ると,モナドという何でもできる型クラスの担当範囲が節操なく,節操ないがゆえに一つのことをやるのに二つ以上の書き方ができてしまう(一番単純には全部IOでいいじゃん的なやり方を許してしまう)ことがHaskellの書き味・読み味にオーバーヘッドを生んでいる気がする*2

おそらく自分はPythonicなコードの書き方が好きだけど,Haskellの純粋さも欲しいという人間なのだ. そんな自分は,頻出モナドを仕様レベルでサポートしてくれるようなプログラミング言語がほしいと思ってしまう.

*1:自分で作ることもできるが,ライブラリ開発者でなければ普通はやらない気がする.

*2:言語仕様のコンパクトさはHaskellの美点の一つなので,コンパクトゆえ書き方に自由度が残るのは仕方のないことでもあると思う.

Haskellの繰り返し制御

Haskellでは手続き型言語の繰り返しに相当する制御構文がないかわりに、fold系が強力な道具となる1。 実際、簡単なfor文に相当するものはfoldで書けてしまう。例えば2

import           Control.Monad
import           Control.Monad.ST
import           Data.List
import           Data.STRef

-- | forの定義
for :: (Monad m) => [a] -> (a -> m ()) -> m ()
for iterator process = foldl' (\m x -> m >> process x) (pure ()) iterator

-- | for文による足し算の使用例:総和
sum' :: (Num a) => [a] -> a
sum' xs = runST $ do
  acc <- newSTRef 0 -- ^ 初期化
  for xs $ \x -> do
    modifySTRef acc (+ x) -- ^ 要素の足し算
  readSTRef acc -- ^ 合計値のreturn

ただしbreak文に相当するものの実装となるととたんに難しい。 イテレータのみを見て判断できるならfor (takeWhile pred xs) $ \x -> do ...などと書けば良いが、 状態に依存してbreakしたい場合はどうすればきれいに書けるだろうか。

こうなった。

import           Control.Monad
import           Control.Monad.ST
import           Data.List        hiding (break)
import           Data.STRef
import           Prelude          hiding (break)


data Control m a = Do (m a) | Break (m ())

extract :: (Monad m) => Control m a -> m ()
extract (Do ma)   = void ma
extract (Break m) = m

break :: (Monad m) => Control m a
break = Break $ return ()

instance Functor m => Functor (Control m) where
  fmap f (Do ma)   = Do $ fmap f ma
  fmap _ (Break m) = Break m

instance Monad m => Applicative (Control m) where
  Do mf <*> Do ma = Do $ mf <*> ma
  _ <*> Break m = Break m
  Break m <*> Do ma = Break $ ma >> m
  pure a = Do $ pure a

instance Monad m => Monad (Control m) where
  ca >>= f = undefined
  Do ma >> Do mb = Do $ ma >> mb
  Do ma >> Break m = Break $ ma >> m
  Break m >> _ = Break m

for' :: (Monad m) => [a] -> (a -> Control m ()) -> m ()
for' iterator process = extract $ foldr (\x c -> process x >> c) (pure ()) iterator

sum'' :: (Ord a, Num a) => [a] -> a
sum'' xs = runST $ do
  acc <- newSTRef 0
  for' xs $ \x -> do
    Do $ modifySTRef acc (+ x) -- ^ For文中の普通の命令には Do をつける
    when (x >= 10) break -- ^ break文
  readSTRef acc

うまく実装できている証拠に、sum'' [1..1000000000]が最初の10項の計算で打ち切られて一瞬で終わる。

追記: 後から他の方法を調べてみたところ、継続モナドを使う例を紹介する記事もあった。


  1. 第5節参照

  2. 基本的にforM_の再実装なので実践的な意味はない。

pythonでcurryワンライナー

pythonを書いていて、急にcurry化したくなったときはこうする:

import functools
curry = lambda n: lambda f: lambda x: (curry(n - 1)(functools.partial(f, x)) if n > 1 else f(x))

そんでもってこう:

@curry(3)
def func(x, y, z):
    return x + y * z

print(func(42)(4)(-5))  # -> 22

Injective Functional Dependency

マルチパラメタクラスの型変数間に一対一の対応関係をもたせたいとする。 このとき、型変数の間に相互にfuncitonal dependency をもたせればよい。

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

-- | this typechecks
class Foo a b | a -> b, b -> a where
  foo :: a
  bar :: b