[Haskell-cafe] A small puzzle: inTwain as function of foldr

[Malcolm Wallace]

Martijn van Steenbergen <martijn at van.steenbergen.nl> wrote:

> 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