CODEWITHSUNDEEP
haskell
newbie
newbie

Reputation: 63

implementing bubble sort using foldr haskell

I am trying to implement bubble sort using foldr but I keep getting error messages saying types not matching and I'm not understanding why. Here's my code:

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

bubbleSorting :: (Ord a) => [a] -> [a]
bubbleSorting = foldr bubble []

Upvotes: 0

Views: 1609

Answers (2)

Redu
Redu

Reputation: 26191

I guess you may implement the bubbleSort function with foldr as follows;

bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = foldr bubble [] xs
                where
                bubble x []     = [x]
                bubble x (y:ys) | x < y     = x:y:ys
                                | otherwise = y:bubble x ys

Upvotes: 0

Cirdec
Cirdec

Reputation: 24166

Your bubble function approximately inserts x into the sorted list y:xs. If we change the first pattern match from [x] to the equivalent (x:[]) you can see that bubble always takes a value x and a remainder of the list (the list it's being inserted into), either [] or y:xs.

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

This can be converted into a function that takes two arguments by removing the : constructor between x and the list it's being inserted into.

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

This is nice; it makes bubble a total function. It's no longer undefined on [] and is compatible with foldr.

There's still a logic error in bubble. I suggest you try bubbleSorting [10,9..1]. You might be surprised by the result.

If you don't want to change the signature of bubble you can instead define bubble' x ys = bubble (x:ys) and use bubble' in foldr.

Upvotes: 2

Related Questions