riemann.hs

import Data.Ratio
import Data.List (partition)

-- Riemann's rearrangement theorem.  @rearrange target rs@ takes a sequence @rs@ whose sum converges but
-- does not converge absolutely, and rearranges its terms so that its sum converges to @target@.

rearrange :: (Ord a, Fractional a) => a -> [Rational] -> [Rational]
rearrange target rs = uncurry go (partition (> 0) rs) 0
    where
    go pos neg accum | fromRational accum < target = let (p:ps) = pos in p : go ps neg (accum+p)
                     | otherwise                   = let (n:ns) = neg in n : go pos ns (accum+n)


-- Rearrange the sequence [ (-1)^n / n | n <- [1..] ] to converge to the golden ratio.

check = mapM_ (print . fromRational) . scanl (+) 0 . rearrange phi $ [ (-1)^n / fromIntegral n | n <- [1..] ]
    where
    phi = (1 + sqrt 5) / 2