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
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. Mike 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
I'm not sure. We start with one list and also, perhaps I should have mentioned that I have a merge function which takes two sorted lists with similar, now, what do they call it, similar orientation? and merges them into one sorted list. e.g. merge [1, 4,] [2, 3] [1,2,3,4] Cheers, Paul At 04:02 14/09/2007, you wrote:
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.
Mike
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
OK, you have the split function, and you have the merge function, and now you have to define the msort function. First write down the base cases (there are two, as you mention), which should be obvious. Then consider the remaining case. Let's say you split the list into two parts. Then what would you do? Mike PR Stanley wrote:
I'm not sure. We start with one list and also, perhaps I should have mentioned that I have a merge function which takes two sorted lists with similar, now, what do they call it, similar orientation? and merges them into one sorted list. e.g. merge [1, 4,] [2, 3] [1,2,3,4] Cheers, Paul At 04:02 14/09/2007, you wrote:
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.
Mike
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
------------------------------------------------------------------------
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Fri, Sep 14, 2007 at 03:45:02AM +0100, PR Stanley wrote:
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.
Split the input list using halve, sort both halves (as merge requires lists to be sorted) and merge them into output list... Regards, -- Krzysztof Kościuszkiewicz Skype: dr.vee, Gadu: 111851, Jabber: kokr@jabberpl.org Mobile IRL: +353851383329, Mobile PL: +48783303040 "Simplicity is the ultimate sophistication" -- Leonardo da Vinci
You may also find this function helpful. I'll let you work out why/how:
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f p = f (fst p) (snd p)
On 9/13/07, Krzysztof Kościuszkiewicz
On Fri, Sep 14, 2007 at 03:45:02AM +0100, PR Stanley wrote:
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.
Split the input list using halve, sort both halves (as merge requires lists to be sorted) and merge them into output list...
Regards, -- Krzysztof Kościuszkiewicz Skype: dr.vee, Gadu: 111851, Jabber: kokr@jabberpl.org Mobile IRL: +353851383329, Mobile PL: +48783303040 "Simplicity is the ultimate sophistication" -- Leonardo da Vinci _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Andrew Wagner -
Krzysztof Kościuszkiewicz -
Michael Vanier -
PR Stanley