Martijn van Steenbergen
But this uses length and init and last all of which are recursive functions. I consider that cheating: only foldr may do the recursion.
I think the key is to pick your intermediate data-structure wisely. A pair of queues would be my choice. You don't need to calculate any lengths, just keep a parity bit for how far you have already come. Code is below, including a very simple implementation of queues - I'm sure there are better ones out there.
import Data.List (foldl')
-- inTwain divides a list of even length into two sections of equal length, -- using a single recursive traversal (fold) of the input. -- Intermediate values are a pair of FIFO queues, keeping a parity state -- to ensure the queues are of nearly equal length. inTwain :: [a] -> ([a],[a]) inTwain = unTwo . foldl' redistrib emptyTwo where redistrib (Two Even begin end) v = Two Odd begin (enQ v end) redistrib (Two Odd begin end) v = Two Even (enQ e begin) (enQ v es) where (e,es) = deQ end
-- The intermediate data structures needed. data Parity = Odd | Even data Two a = Two Parity (Queue a) (Queue a) data Queue a = Q [a] [a]
emptyTwo = Two Even emptyQ emptyQ emptyQ = Q [] []
unTwo :: Two a -> ([a],[a]) unTwo (Two _ begin end) = (unQ begin, unQ end)
-- A very simple implementation of FIFO queues. enQ :: a -> Queue a -> Queue a deQ :: Queue a -> (a, Queue a) unQ :: Queue a -> [a] enQ v (Q begin end) = Q begin (v:end) deQ (Q (v:vs) end) = (v, Q vs end) deQ (Q [] []) = error ("deQ []") deQ (Q [] end) = deQ (Q (reverse end) []) unQ (Q begin end) = begin ++ reverse end
Regards, Malcolm