module Algo.Rootfix where import Data.Vector.Unboxed as V rootfix :: (V.Vector Int, V.Vector Int) -> V.Vector Int {-# NOINLINE rootfix #-} rootfix (ls, rs) = rootfix (V.replicate (V.length ls) 1) ls rs where rootfix xs ls rs = let zs = V.replicate (V.length ls * 2) 0 vs = V.update_ (V.update_ zs ls xs) rs (V.map negate xs) sums = V.prescanl' (+) 0 vs in V.backpermute sums ls