しゃくとり法

code:haskell

shakutori :: (a -> b -> Bool) -- 区間条件

-> (b -> a -> b) -- 伸長操作

-> (b -> a -> b) -- 短縮操作

-> b -- 初期値

shakutori p op inv e as = phi as as 0 e

where

phi lls rrs len res = case lls of

[] -> []

l:ls -> case rrs of

[] -> len : phi ls [] (pred len) (inv res l)

r:rs | p r res -> phi lls rs (succ len) (op res r)

| len == 0 -> 0 : phi ls rs 0 e

| otherwise -> len : phi ls rrs (pred len) (inv res l)