Haskell合并排序

本文介绍了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 已由其他人指定.