[Haskell-cafe] Clarification Please

PR Stanley prstanley at ntlworld.com
Thu Sep 13 22:45:02 EDT 2007

Taken from chapter 6, section 8 of the Hutton book on programming in Haskell:
5. Using merge, define a recursive function
msort :: (Ord a) => [a] -> [a]
that implements merge sort, in which the empty 
list and singleton lists are already sorted, and 
any other list is sorted by merging together the 
two lists that result from sorting the two halves of the list separately. :
Hint: first define a function
¬halve :: [a] -> [([a], [a])]
¬that splits a list into two halves whose length differs by at most one.

	Create a halve function - okay, that's fairly 
straightforward. The rest, I'm afraid, is a 
little obscure. I'm not looking for the solution; 
I'd like to work that out for meself. However, 
I'd  really appreciate some clues as to the general structure of the algorithm.
Much obliged,

More information about the Haskell-Cafe mailing list