[Haskell-cafe] Clarification Please

Michael Vanier mvanier at cs.caltech.edu
Thu Sep 13 23:02:45 EDT 2007

Define a merge function that merges two sorted lists into a sorted list containing all the elements 
of the two lists.  Then define the msort function, which will be recursive.


PR Stanley wrote:
> Hi
> 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,
> Paul
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list