読者です 読者をやめる 読者になる 読者になる

停止するall

Haskell

foldrでallを書くと、全てのリストが評価されるから

while (it != end) {
  if (!pred(*it))
    return false;
  ++it;
}

みたいな途中で停止する動作にすることはできないんじゃないかと思い込んでいたのですが、どうやらちゃんと停止するようです。


allの定義を見てみましょう。

all :: (a -> Bool) -> [a] -> Bool
all p = and . map p

ふむふむ、ここではわからない。
andはどう書かれているのか。

and :: [Bool] -> Bool
and = foldr (&&) True

なるほどなるほど。
foldrの定義に沿って、

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

andを置き換えると以下のようになるので、

and []     = True
and (x:xs) = x && and xs

mapによって[True, True, False, True]のようになったリストを再帰して、Falseになった時点で再帰が終了してるので停止するということでした。
&&の2項演算をfoldrするというのはおもしろいですね。