CODEWITHSUNDEEP
listsortinghaskell
Arnthor
Arnthor

Reputation: 33

haskell list and functional

This is homework that has been driving crazy for the last couple of days.

I got a list that I am applying a function to - pushing each element to the right if the element next to it is smaller then the previous one.

My function to pass over the list once and sort the head of the list:

sortEm lis@(x:y:xs) = if x > y then y: sortEm (x:xs) else lis
sortEm [x] = [x]
sortEm [] = []

myList (x:y:xs) = if x > y then sortEm lis else x:myList(y:xs)
myList [] = []
myList [x] = [x]

But my problem is that once that sortem has finished it returns either an empty list or a list containing one element, how would i design this the functional way?

I was thinking about foldl and some haskell magic to go along with that but currently I am stuck.

Thanks in advance

Upvotes: 3

Views: 513

Answers (3)

Will Ness
Will Ness

Reputation: 71065

First of, your sortEm function name is misleading, it doesn't sort its argument list but inserts its head element into its tail. As it happens, there is an insert function already in Data.List module that inserts its first argument into the 2nd, so there's an equivalency

sortEm (x:xs) === Data.List.insert x xs

Now, inserting an item will only get you a sorted list back if you're inserting it into a list that is already sorted. Since empty list is sorted, that's what myList function does that you got in dave4420's answer. That is an "insertion" sort, progressively inserting elements of list into an auxiliary list, initially empty. And that's what the 2nd function does that you got in dave4420 answer:

insertionSort xs = foldr Data.List.insert [] xs

This does "apply sortem" i.e. inserts, "each element" only once. For a list [a,b,c,...,z] it's equivalent to 

insert a (insert b (insert c (... (insert z []) ...)))

What you probably meant in your comment, i.e. comparing (and possibly swapping) two neighboring elements "only once", is known as bubble sort. Of course making only one pass through the list won't get it sorted, in a general case:

bubbleOnce xs = foldr g [] xs  where
  g x [] = [x]
  g x xs@(y:ys) | x>y       = y:x:ys  -- swap x and y in the output
                | otherwise = x:xs    -- keep x before y in the output

Now, bubbleOnce [4,2,6,1,8] ==> [1,4,2,6,8]. The value that you expected, [2,4,1,6,8], would result from applying the folding function g in an opposite direction, from the left to the right. But that's much less natural to do here with Haskell lists:

bubbleOnce' [] = []
bubbleOnce' (x:xs) = let (z,h)=foldl g (x,id) xs in (h [z])  where
  g (x,f) y | x>y       = (x, f.(y:))   -- swap x and y in the output
            | otherwise = (y, f.(x:))   -- keep x before y in the output

(edit:) see jimmyt's answer for the equivalent, but simple and nice version using straightforward recursion. It is also lazier (less strict) than both the fodlr and foldl versions here.

Upvotes: 4

jimmyt
jimmyt

Reputation: 501

-- if..then..else version
sortEM      ::  Ord a => [a] -> [a]

sortEM (x:y:xs)     =   if x < y
                        then x : sortEM (y:xs)
                        else y : sortEM (x:xs)
sortEM b            =   b   


-- guard version
sortEM_G    ::  Ord a => [a] -> [a]

sortEM_G (x:y:xs)
     | x < y        =   x : sortEM_G (y:xs)
     | otherwise    =   y : sortEM_G (x:xs)
sortEM_G b          =   b

Upvotes: 2

dave4420
dave4420

Reputation: 47042

myList []       = []
myList (x : xs) = sortEm (x : myList xs)

(untested)

Or in terms of a fold:

myList = foldr cons []
  where cons x xs = sortEm (x : xs)

(also untested)

Upvotes: 2

Related Questions