Haskell:高阶函数

Question

问题：

实现高阶插入排序算法hoMergeSort，它类似于合并排序，但元素x放在元素y之前，如果乐趣x<趣味y :：a -> b是由高阶合并排序作为输入的函数。换句话说，评估hoMergeSort趣味xs的结果应该是一个列表y1、y2、.

我的非工作尝试：

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)

在过去的一个半小时里，我一直在努力解决这个问题，但没有取得任何进展。我编写代码的方式对我来说是有意义的，但编译器却没有。

不要为我寻找完全解决问题的人，只要让我走上正确的思路就行了。

谢谢。

Answer 1

您希望在列表中插入x，而不是fun x。下面是一个应该起作用的函数：

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

注意，我使用了守卫，因为它们使代码更加清晰，而不是“如果-然后-否则”。此外，这只合并了两个已经排序的列表。