= Solution
Interleave equal halves, or collect the first and second components of adjacent pairs:
``
riffle :: [a] -> [a]
riffle = unpairs . uncurry zip . halve
unriffle :: [a] -> [a]
unriffle = unhalve . unzip . pairs
``
For halves `as` and `bs` of equal length, `pairs (riffle xs) = zip as bs`, and `unzip (zip as bs) = (as,bs)`. Therefore `unriffle (riffle xs) = xs`. Conversely, starting from the adjacent pairs of any even <list>, separating the components, halving their concatenation and zipping them restores those same pairs. Hence `riffle (unriffle xs) = xs` too. Every stage takes <linear time>. This <perfect out-shuffle> leaves the first and last positions fixed.
Back to article page
