[Haskell-cafe] A small puzzle: inTwain as function of foldr
Malcolm.Wallace at cs.york.ac.uk
Fri Jun 5 09:35:02 EDT 2009
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
> 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
More information about the Haskell-Cafe