= Solution
Join either two halves or successive pairs:
``
unhalve :: ([a],[a]) -> [a]
unhalve (xs,ys) = xs ++ ys
unpairs :: [(a,a)] -> [a]
unpairs = foldr (\(x,y) zs -> x:y:zs) []
``
By the defining property of `splitAt`, concatenating the two halves restores the original <list>. For `unpairs`, <structural induction> on the even input proves that its first pair restores its first two elements and the recursive result restores the rest. Thus both requested <function compositions> are the identity. Fully consuming either result takes at most <linear time>; <list concatenation> only copies the left half once.
Back to article page
