Haskell合并排序 [英] Haskell Merge Sort

问题描述

这是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 已由其他人指定.

这篇关于Haskell合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！