In the comments to the previous exercise, reader Kevin gave a beautiful solution in Haskell; it sorts the input items, groups them into sub-lists of like items, transposes the rows and columns of the sub-lists, and concatenates the sub-lists back into a single list:

import Data.List
sortwodup :: (Ord a) => [a] -> [a]
sortwodup = concat . transpose . group . sort

Here’s the pipeline of functions applied to the sample input (2 9 1 5 1 4 9 7 2 1 4):

Sort converts the input list to (1 1 1 2 2 4 4 5 7 9 9).

Group converts the output of sort to a list of sub-lists: ((1 1 1) (2 2) (4 4) (5) (7) (9 9)).

Transpose swaps rows and columns, ignoring missing items, like this:

    1 1 1        1 2 4 5 7 9
    2 2          1 2 4 9
    4 4          1
    5
    7
    9 9

Thus, the output from transpose is ((1 2 4 5 7 9) (1 2 4 9) (1)). Finally, concatenate removes the sub-list structure, producing (1 2 4 5 7 9 1 2 4 9 1).

Your task is to write a Haskell-style program to solve the problem of sorting a list, moving duplicates to the end. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2