高階しゃくとり法関数

Syaku.hs

module Syaku where

import Debug.Trace

-- | 参考文献: https://qiita.com/drken/items/ecd1a472d3a0e7db8dce

-- | 参考にした関数
-- mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
-- mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s

data Cond = Pre | Post

-- | 高階しゃくとり法関数
syaku :: Cond -- ^ 条件が成り立たなければならないタイミング
      -> (a -> b -> (a, c)) -- ^ 頭側のポインタが動くときの計算
      -> (a -> b -> (a, c)) -- ^ 尾側のポインタが動くときの計算
      -> (a -> Bool) -- ^ 頭側のポインタを動かす前か後ろで成立しなければならない条件
      -> a -- ^ 累積値の初期値
      -> [b] -- ^ 入力リスト
      -> (a, [c]) -- ^ 累積値の最終値と出力
syaku cond f g p e xs = syaku' e [] xs xs
  where
    p' Post fun acc x = p (fst $ fun acc x)
    p' Pre _ acc _ = p acc
    syaku' acc ys [] [] = (acc, reverse ys)
    syaku' acc ys (l:ls) [] =
      if p acc
      then syaku' acc' (y:ys) ls []
      else syaku' acc (y:ys) ls []
      where 
        (acc', y) = g acc l
    syaku' acc ys [] (r:rs) = error "invalid syaku: The tail overtakes the head."
    syaku' acc ys ls'@(l:ls) rs'@(r:rs) = 
      if p' cond f acc r
      then syaku' acc' (y:ys) ls' rs
      else syaku' acc'' (y':ys) ls rs'
      where
        (acc', y) = f acc r
        (acc'', y') = g acc l


-- | AOJ より、総和が　x 以下となる区間の数をカウント
--
-- >>> aoj1
-- 11

aoj1 :: Int
aoj1 = let
  x = 12
  a = [5, 3, 8, 6, 1, 4]
  -- アキュムレータには距離と部分和の組を記録
  f (dist, sum) v =
    -- trace ("f " ++ show ((dist, sum), v))
     ((dist + 1, sum + v), 0)
  g (dist, sum) v =
    -- trace ("g " ++ show ((dist, sum), v))
    ((dist - 1, sum - v), dist) -- しゃくとりが縮むときの距離をカウントする
  p (dist, sum) = sum <= x
  in
    -- syaku f g p (0, 0) a
    sum . snd $ syaku Post f g p (0, 0) a -- 出力リストの総和が回答

-- | POJ より、総和が x 以上となる区間のうち最短のものの長さ
--
-- >>> poj3061
-- 4

poj3061 :: Int
poj3061 = let
  x = 28
  a = [5, 1, 2, 5, 10, 7, 4, 9, 2, 8]
  maxDist = maxBound :: Int
  f (dist, sum, minDist) v =
    -- trace ("f " ++ show ((dist, sum, minDist), v)) 
    ((dist + 1, sum + v, maxDist), maxDist)
  g (dist, sum, minDist) v =
    -- trace ("g " ++ show ((dist, sum, minDist), v)) 
    ((dist - 1, sum - v, minDist'), minDist')
    where
      minDist' = min minDist dist
  p (dist, sum, minDist) = sum < x
  in
    -- syaku f g p (0, 0, maxDist) a
    minimum . snd $ syaku Pre f g p (0, 0, maxDist) a -- 出力リストの最小値が回答