CODEWITHSUNDEEP
algorithmsortinghaskell
John Doe
John Doe

Reputation: 3

My sorting algorithm doesn't work

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

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

Upvotes: 0

Views: 148

Answers (2)

Centril
Centril

Reputation: 2658

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)

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477607

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]

Upvotes: 2

Related Questions