これは何?
ここ1ヶ月くらい、Haskellで精進している。
下記の問題をfoldrを使ってACしたのだが、意図したものと異なる美しくないコードを実装してしまった。
反省札として本記事を執筆し、今回の失敗の解像度を上げたいと思う。
そもそも短絡とは?
Short-circuit folds
Examples of short-circuit reduction include various boolean predicates that test whether some or all the elements of a structure satisfy a given condition. Because these don't necessarily consume the entire list, they typically employ foldr with an operator that is conditionally strict in its second argument. Once the termination condition is met the second argument (tail of the input structure) is ignored. No result is returned until that happens. 1
短絡は英語だとShort-circuitと言う。
Haskellには、畳み込み(fold)に使う関数が多数存在するが、foldrは短絡ができる。
foldlなどの短絡ができない畳み込みを使用する場合にはリストの要素を全て走査する必要がある。
しかし、foldrのような短絡ができる畳み込みの場合、リスト全てを走査する前に条件が満たされた場合、残りの走査は実施されない。
これは、Haskellが遅延評価という、値が使用される際に評価する評価方法を採用しているため、実現できている。
例として、allという全てがTrueの時だけTrueを返す関数を使って説明する。
これは、簡略化して書くと以下のように書ける。
all :: (a -> Bool) -> [a] -> Bool
all f xs = foldr (\x e -> f x && e) True xs
これを使い、リスト[3,2,1]がすべて4より大きいかを調査してみる。
all (>4) [3,2,1]
これは以下のように展開される。
foldr (\x e -> (>4) x && e) True [3,2,1]
(\x e -> (>4) x && e) 3 (foldr (\x e -> (>4) x && e) True [2,1])
一番左のラムダ式を評価すると、
(>4) 3 && (foldr (\x e -> (>4) x && e) True [2,1])
つまり、このようになる。
False && (foldr (\x e -> (>4) x && e) True [2,1])
&&は遅延評価により、左側がFalseの場合、右側を評価せず、Falseを返す。
つまり、条件を満たさない要素が1つ見つかるまで評価は行われるが、1つ見つかって以降は評価が行われない。
これが短絡の強みである。
自分の良くない実装: foldrを使った短絡をしたつもりができていない
自分は、foldrを使うと短絡できることはなんとなく知っていたがうまく実装できていなかった。
以下のコードの何が良くないだろうか?
{-# LANGUAGE MonoLocalBinds #-}
{-# OPTIONS_GHC -Wno-x-partial #-}
{-# OPTIONS_GHC -Wunused-imports #-}
import Control.Arrow ((>>>))
import Data.Set qualified as Set
solve :: String -> String
solve s = if null result then "None" else result
where
-- foldrを使い、一つ見つかったら残りは評価しない(短絡)したつもりでnullチェックは毎回走ってしまう。
result = foldr (\c acc -> (if null acc && c `Set.notMember` sSet then c : acc else acc)) [] $ reverse ['a' .. 'z'] -- ['a'..]だとUnicode全域になってしまう
sSet = Set.fromList $ init s
main :: IO ()
main =
interact $
solve >>> (++ "\n")
確かに、Set.notMemberという$O(\log n)$の走査をnullチェックを入れることで全リスト(全てのアルファベットの文字)に対して実施しないようにはなっている。
しかし、このコードでは全てのリストに対してnullチェックが走ってしまっている。
うまく短絡することができれば、1つ見つかった以降はnullチェックは評価しなくて良いのにである。
では、なぜこの実装だと短絡ができていないのだろうか。
この実装の良くないところは、if null accの部分でaccの評価を強制しているところである。
accを返すだけのような評価を強制しない操作であれば、問題ない。
accの評価を強制する関数を正格な演算子と呼んだりする。
自分の過去記事で2正格な演算子である+を使い、foldrでリストの合計を求める際にどのように畳み込みが行われるかを説明した。
-- 再掲
foldr (+) 0 [1,2,3,4]
→ 1 + foldr (+) 0 [2,3,4]
→ 1 + (2 + foldr (+) 0 [3,4])
→ 1 + (2 + (3 + foldr (+) 0 [4]))
→ 1 + (2 + (3 + (4 + foldr (+) 0 [])))
→ 1 + (2 + (3 + (4 + 0))) 再帰展開終了
→ 1 + (2 + (3 + 4)) unwindフェーズ開始。サンク1つ消費
→ 1 + (2 + 7) サンク1つ消費
→ 1 + 9 サンク1つ消費
→ 10 サンク1つ消費
+をあえて、(\x acc -> x + acc)のようにラムダ式に書き換えてみるとわかりやすい。
foldr (\x acc -> x + acc) 0 [1,2,3,4]
→ (\x acc -> x + acc) 1 (foldr (\x acc -> x + acc) 0 [2,3,4])
この場合、xは1、accは(foldr (\x acc -> x + acc) 0 [2,3,4])となっているのがわかる。
つまり、正格な演算子を評価するためにはx、accの両方の評価が必要なのである。
そのため、先程の自分の解答は畳み込みに使用する関数が正格であるため、foldl同様に最後までリストを走査しており、foldlで書き換え可能な状態となってしまっている。
(なんなら、foldrバージョンはreverseしているので読みにくいし、計算コスト的にも無駄が多い)。
-- foldlで書くとこうなる
result = foldl (\acc c -> (if null acc && c `Set.notMember` sSet then c : acc else acc)) [] ['a' .. 'z'] -- ['a'..]だとUnicode全域になってしまう
短絡するにはどうすればよかったか?
foldrの畳み込みに使用する関数を非正格にすればよい。
具体的にはaccの評価が強制されない形にする。
以下の例(\c acc -> if c `Set.notMember` sSet then [c] else acc)では、条件判定にaccを使わずcだけで分岐している点がポイントである。cがsSetに存在しない時はaccを無視して[c]を返すため、残りのfoldr(=acc)は評価されず短絡できる。
foldr (\c acc -> if c `Set.notMember` sSet then [c] else acc) "None" ['a' .. 'z']
-- `a`が`sSet`に存在しない場合
-> (\c acc -> if c `Set.notMember` sSet then [c] else acc) 'a' (foldr (\c acc -> if c `Set.notMember` sSet then [c] else acc) "None" ['b' .. 'z'])
-> ['a']
{-# LANGUAGE MonoLocalBinds #-}
{-# OPTIONS_GHC -Wno-x-partial #-}
{-# OPTIONS_GHC -Wunused-imports #-}
import Control.Arrow ((>>>))
import Data.Set qualified as Set
solve :: String -> String
solve s = if null result then "None" else result
where
result = foldr (\c acc -> if c `Set.notMember` sSet then [c] else acc) "None" ['a' .. 'z'] -- ['a'..]だとUnicode全域になってしまう
sSet = Set.fromList $ init s
main :: IO ()
main =
interact $
solve >>> (++ "\n")
AC結果も15ms -> 9msとお気持ち程度は速くなった。
おまけ
foldrで書いても良いが、同じことができるHaskellの便利な関数を紹介する。
findは1に記載のあるように短絡できる関数の一つなので、条件を満たす値を1つ見つけた段階でJust aを返して短絡する。
{-# OPTIONS_GHC -Wno-x-partial #-}
{-# OPTIONS_GHC -Wunused-imports #-}
import Control.Arrow ((>>>))
import Data.List (find)
import Data.Set qualified as Set
-- Sに含まれない最小の英小文字を返す。全て含む場合はNone
solve :: String -> String
solve s = case find (`Set.notMember` sSet) ['a' .. 'z'] of
Just c -> [c]
Nothing -> "None"
where
sSet = Set.fromList s
main :: IO ()
main =
interact $
lines >>> head >>> solve >>> (++ "\n") -- 入力値側で改行を削除
2026年7月追記
自分はfoldrやfindのようなメソッドを使うほうが好みではあるため、コメントいただいたような手で再帰を書かないように努力している。
だが、頑張っても畳み込みでは短絡できない問題もあるのでこういうのは諦めて手で再帰したほうが良さそう。
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MonoLocalBinds #-}
{-# OPTIONS_GHC -Wno-x-partial #-}
{-# OPTIONS_GHC -Wunused-imports #-}
import Data.List (sortOn)
solve :: Int -> [[Int]] -> Int
solve m abList = fst $ go (0, 0) abTupleList
where
abTupleList = sortOn fst $ map (\[a, b] -> (a, b)) abList
go :: (Int, Int) -> [(Int, Int)] -> (Int, Int)
go (!result, !cnt) _
| cnt == m = (result, cnt)
go (!result, !cnt) ((a, b) : rest) =
let n = min b (m - cnt)
in go (result + (n * a), cnt + n) rest
main :: IO ()
main = interact $ \inputs ->
let ls = lines inputs
[n, m] = map read . words $ head ls :: [Int]
abList = map (map read . words) $ drop 1 ls :: [[Int]]
in show (solve m abList) ++ "\n"