CODEWITHSUNDEEP
haskell
henahzurfdsa
henahzurfdsa

Reputation: 23

Haskell: Higher order functions

The Problem:

Implement the higher order insertion sort algorithm hoMergeSort which is similar to merge sort except that an element x is placed before an element y if fun x < fun y where fun :: a -> b is a function taken as input by higher order merge sort. In other words, the result of evaluating hoMergeSort fun xs should be a list [y1,y2,..., yn] such that fun y1 < fun y2 < ... < fun yn.

My non-working attempt:

homerge :: Ord b => (a -> b) -> [a] -> [a] -> [a]
homerge _ xs [] = xs
homerge _ [] ys = ys
homerge fun (x:xs) (y:ys) = if (fun x)<(fun y) then fun x : (homerge fun xs (y:ys)) 
                            else y : (homerge fun (x:xs) ys)

I've been trying to get my head around this problem for the past hour and a half and have been making no progress. The way I've written my code makes sense to me but the compiler is not having any of it.

Not looking for someone to completely solve the question for me, just set me on the right track of thinking.

Thanks.

Upvotes: 0

Views: 293

Answers (1)

Lorenzo
Lorenzo

Reputation: 2210

You want to insert x into the list, not fun x. Here is a function that should work:

homerge :: Ord b => (a -> b) -> [a] -> [a] -> [a]
homerge _ xs [] = xs
homerge _ [] ys = ys
homerge f (x:xs) (y:ys) | f x < f y = x : homerge f xs (y:ys)
                        | otherwise = y : homerge f (x:xs) ys

Note I used guards because they make the code much more clear then if-then-else. Also this only merges two already-sorted lists.

Upvotes: 3

Related Questions