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_の再実装なので実践的な意味はない。