My sorting algorithm doesn't work

Question

As homework, we were supposed to implement a few functions and then come up with a sorting algorithm potentially implementing those functions. first of all, these are the two needed functions:

remove :: (Ord a) => a -> [a] -> [a] 
remove a (x:[]) = x:[]
remove a (x:xs) =
  if a == x
    then xs
    else x:(remove a xs)

and:

smallest :: (Ord a) => [a] -> a
smallest (x:y:[]) =
  if x < y
    then x
    else y
smallest (x:y:xs) =
  if x < y
    then smallest (x:xs)
    else smallest (y:xs)

My sorting Algorithm is just supposed to take the smallest element and put it at the beginning of the list:

sort :: (Integral a) => [a] -> [a]
sort [] = []
sort x = smallest x : sort (rest x)
      where
        rest = remove (smallest x) x

The Error I get is

Couldn't match expected type ‘[a] -> [a]’ with actual type ‘[a]’
The function ‘rest’ is applied to one argument, but its type ‘[a]’ has none In the first argument of ‘sort’, namely ‘(rest x)’ In the second argument of ‘(:)’, namely ‘sort (rest x)’

I'm surely missing something obvious, but I can't figure out what it is. help me pls.

Notice, after it's fixed, the algorithm appears to sort and deduplicate the list. sort [1,1,1,1] == [1]. This is because remove removes all matching elements instead of just one. — Thomas M. DuBuisson
– Thomas M. DuBuisson, Commented Jun 7, 2017 at 16:21
But you call rest x, but rest is defined without any arguments. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jun 7, 2017 at 16:28

willeM_ Van Onsem · Accepted Answer · 2017-06-07 16:37:48Z

First of all, your remove function will error on the empty list, and never remove an element from a list with one element. You probably want to write:

remove :: Eq a => a -> [a] -> [a] 
remove a [] = []
remove a (x:xs) | a == x = xs
                | otherwise = x : remove a xs

Next your smallest behaves weird as well since it will not select the smallest from a list with one element (in that case the smallest element is that case). We can rewrite it like:

smallest :: Ord a => [a] -> a
smallest [x] = x
smallest (x:y:xs) | x < y = smallest (x:xs)
                  | otherwise = smallest (y:xs)

Now that we have fixed these, we can focus on the real sorting function. I do not really see why you want to use a helper function here to remove the element, you can use a variable small to store the smallest element in the list, and then simply use recursion, like:

sort :: Ord a => [a] -> [a]
sort [] = []
sort x  = small : sort (remove small x)
    where small = smallest x

Now with this sorting algorithm, we obtain:

*Main> sort [1,4,2,5]
[1,2,4,5]
*Main> sort [1,4,2,5,1,3,0,2]
[0,1,1,2,2,3,4,5]

Centril · Accepted Answer · 2017-09-18 17:55:05Z

2

Compile Error

If we look at the entire error message from ghci, which is:

    * Couldn't match expected type `[a] -> [a]' with actual type `[a]'
    * The function `rest' is applied to one argument,
      but its type `[a]' has none
      In the first argument of `sort', namely `(rest x)'
      In the second argument of `(:)', namely `sort (rest x)'
    * Relevant bindings include
        rest :: [a]
          (bound at ...)
        x :: [a]
          (bound at ...)
        sort :: [a] -> [a]
          (bound at ...)
Failed, modules loaded: none.

We see that rest :: [a]. But you are attempting to apply something to rest here:

sort x = smallest x : sort (rest x)

But you had already applied x here:

rest = remove (smallest x) x

So, simply change the former to:

sort x = smallest x : sort rest

And it will compile. That said, I haven't checked the logic of the algorithm itself.

Fixing the logic:

I rewrote the code with the LambdaCase extension which looks neater. I also renamed your sorting function to sort' so that it doesn't clash with Data.List (sort).

You had 2 problems in sort'. First, you didn't handle the case of a singleton list, which resulted in a non-exhaustive pattern match. I added the clause [x] -> [x] for this. Second, you should use a let binding to evaluate smallest xs only once, I fixed that too. Third, you had the problem that Thomas M. DuBuisson described, which I fixed. And below is the code, with quickCheck and all.

remove :: Eq a => a -> [a] -> [a] 
remove a = \case
  []     -> []
  (x:xs) -> if a == x then xs else x : remove a xs

smallest :: Ord a => [a] -> a
smallest = \case
  (x:y:[]) -> if x < y then x else y
  (x:y:xs) -> if x < y then smallest (x:xs) else smallest (y:xs)

sort' :: Ord a => [a] -> [a]
sort' = \case
  [ ] -> [ ]
  [x] -> [x]
  xs  -> let s = smallest xs in s : sort' (remove s xs)

prop_sort :: Ord a => [a] -> Bool
prop_sort xs = sort xs == sort' xs

Running QuickCheck:

> quickCheck prop_sort
+++ OK, passed 100 tests.

With the alternate changes proposed by Willem Van Onsem, smallest, sort instead looks as:

smallest :: Ord a => [a] -> a
smallest = \case
  [x]      -> x
  (x:y:xs) -> if x < y then smallest (x:xs) else smallest (y:xs)

sort' :: Ord a => [a] -> [a]
sort' = \case
  [] -> []
  xs -> let s = smallest xs in s : sort' (remove s xs)

smallest can also be written as a fold:

import Data.List (foldl1)

smallest :: Ord a => [a] -> a
smallest = foldl1 $ \x y -> if x < y then x else y

and even shorter with by also using min :: Ord a => a -> a -> a:

import Data.List (foldl1)

smallest :: Ord a => [a] -> a
smallest = foldl1 min

wherefore our solution can be written, in total as:

sort' :: Ord a => [a] -> [a]
sort' = \case [] -> [] ; xs -> let s = foldl1 min xs in s : sort' (remove s xs)

edited Sep 18, 2017 at 17:55

answered Jun 7, 2017 at 16:07

Centril

2,6761 gold badge25 silver badges34 bronze badges

5 Comments

John Doe Over a year ago

Ok cool, progress. Now it compiles, but it prints an array with infinite "1"s

Centril Over a year ago

With what input?

John Doe Over a year ago

sort [100,99..1], it just takes the last element and repeats it

Thomas M. DuBuisson Over a year ago

JohnDoe, that's because you don't both removing the smallest element when its at the end: remove a (x:[]) = x:[].

Centril Over a year ago

@JohnDoe updated my answer with a fix to the logic. Bear in mind that this algorithm is slow with complexity O(n^2). A better solution is quicksort or mergesort. smthngsmwhr.wordpress.com/2012/11/09/…

Collectives™ on Stack Overflow

My sorting algorithm doesn't work

2 Answers 2

Comments

Compile Error

Fixing the logic:

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Compile Error

Fixing the logic:

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related