Haskell合并排序
问题描述：
这是Mergesort的实现，它使用更高阶的函数，保护，where和递归.
This is an implementation of Mergesort using higher order functions,guards,where and recursion.
但是从编译器 6:26收到错误:解析输入"="
mergeSort :: ([a] -> [a] -> [a]) -> [a] -> [a]
mergeSort merge xs
| length xs < 2 = xs
| otherwise = merge (mergeSort merge first) (mergeSort merge second)
where first = take half xs
second = drop half xs
half = (length xs) `div` 2
我看不到有什么问题吗?甚至我不了解编译器.
I can't see whats wrong? or rather I don't understand the compiler.
答
将列表减半不是O(1)操作，而是O(n)，因此与命令式合并排序相比，给定的解决方案会带来额外的成本.避免减半的一种方法是简单地通过制作单例直接开始合并，然后合并每两个连续的列表:
Halving a list is not an O(1) operation but O(n), so the given solutions introduce additional costs compared to the imperative version of merge sort. One way to avoid halving is to simply start merging directly by making singletons and then merging every two consecutive lists:
sort :: (Ord a) => [a] -> [a]
sort = mergeAll . map (:[])
where
mergeAll [] = []
mergeAll [t] = t
mergeAll xs = mergeAll (mergePairs xs)
mergePairs (x:y:xs) = merge x y:mergePairs xs
mergePairs xs = xs
其中 merge 已由其他人指定.