CODEWITHSUNDEEP
haskell
Tedd Parsile
Tedd Parsile

Reputation: 65

haskell beginner - my simple sort

I have this code for sorting list of even number of items:

sort [] = []
sort l = sortN l (length l)

sortN l 0 = l
sortN l n = sortN (swap l) (n - 1)

swap [] = []
swap (a:b:t) | a <= b = a : b : (swap t)
swap (a:b:t) | b <  a = b : a : (swap t)

and I am stuck. For some reason, which I don't understand it returns results as if only one swap was always called.

Also, please do not post here better and more efficient ways how to sort. I am aware of them. I want to know why this is wrong, not other solutions.

Thank you.

Upvotes: 0

Views: 157

Answers (2)

Random Dev
Random Dev

Reputation: 52280

Let me offer you a working version (there was the one-element case missing from swap so as far as I see you will run into trouble else:

swap []  = []
swap [a] = [a]
swap (a:b:t)
  | a <= b    = a : swap (b:t)
  | otherwise = b : swap (a:t)

I will not be tempted into giving you a different algorithm but still you don't need to run swap xs length xs times - you just have to run it till the output is not changing anymore:

sort :: Ord a => [a] -> [a]
sort = fix swap

swap :: Ord a => [a] -> [a]
swap []  = []
swap [a] = [a]
swap (a:b:t)
  | a <= b    = a : swap (b:t)
  | otherwise = b : swap (a:t)

fix :: Eq a => (a -> a) -> a -> a
fix f x = let x' = f x
          in if x' /= x then fix f x' else x

fix here will do exactly that - it applies f to x till the result is not changing anymore.

for example:

  • sort [3,6,1,3,2] will call swap only 4 times
  • sort [1..10] it will be called only once

testing your implementations

maybe you are interested in how you can easily check your implementations - here is a QuickCheck test (I used to verify my solution too) that does this:

import Test.QuickCheck

isSorted :: Ord a => [a] -> Bool
isSorted []  = True
isSorted [_] = True
isSorted (a:b:t) = a<=b && isSorted (b:t)

checkSortAlg :: ([Int] -> [Int]) -> IO ()
checkSortAlg sortAlg = quickCheck test
  where
    test xs = isSorted $ sortAlg xs

you just have to run it like this (for example in ghci):

checkSortAlg sort

it should print +++ OK, passed 100 tests.

here is what it does for for the version with the missing swap [a] = [a] case:

(after 3 tests and 1 shrink): 
Exception:
  SimpleSort.hs:(9,1)-(12,30): Non-exhaustive patterns in function swap
[0]

this tells you that after 3 tests it used some list that after shrinking to [0] still threw the Non-exhaustive patterns exception - so it basically tells you to look for the single element case here ;) - of course the compiler should have too

Upvotes: 1

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

The problem is you are only considering the same pairs of element on each pass. Consider:

swap (a:b:t) | a <= b = a : b : (swap t)
swap (a:b:t) | b <  a = b : a : (swap t)

What if we have a list [4,1,1,1]?

swap [4,1,1,1] = 1 : 4 : swap [1,1] = 1:4:1:1:[]

Ok, now lets look at the next iteration of sortN and its call to swap:

swap [1,4,1,1] = 1 : 4 : swap [1,1]

So you see, swap implicitly assumes every pair of elements is ordered within the list. Instead consider the implementation a: swap (b:t) and b : swap (a : t).

Upvotes: 6

Related Questions