1

我想利用归并排序算法。mergeSort是等待合并函数作为第一个参数的主要函数。有谁知道，我的问题出在哪里？非常感谢您提前。 

mergeSort xs = merge xs
mergeDesc xs = reverse (mergeAsc xs)
mergeAsc [] = []
mergeAsc [x] = [x]
mergeAsc xs = merge (mergeAsc top) (mergeAsc bottom) where (top, bottom) = splitAt (length xs `div` 2) xs
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) | x <= y    = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys
4

1 回答 1

5

将类型签名添加到您的函数中，那么问题就变得很明显了：

mergeAsc, mergeDesc :: Ord a => [a] -> [a]

mergeDesc xs = reverse (mergeAsc xs)
mergeAsc [] = []
mergeAsc [x] = [x]
mergeAsc xs = merge (mergeAsc top) (mergeAsc bottom) where (top, bottom) = splitAt (length xs `div` 2) xs

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) | x <= y    = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys

因此，如果您定义mergeSort为merge，它是一个仅合并两个有序列表的函数，而您实际上希望它对单个列表进行排序。你可以用

mergeSort xs = mergeAsc xs

或者简单而可取地，

mergeSort = margeAsc

请注意这mergeDesc不是很好：您首先以错误的顺序对列表进行排序，然后将其反转？在 Haskell 中，你希望你的算法足够灵活，可以自己处理不同的排序。所以你会定义

mergeSortBy :: (a->a->Ordering) -> [a] -> [a]
mergeSortBy cmp = mSort
 where 
       mSort [] = []
       mSort [x] = [x]
       mSort xs = merge (mSort top) (mSort bottom)
        where (top, bottom) = splitAt (length xs `quot` 2) xs

       merge [] ys = ys
       merge xs [] = xs
       merge (x:xs) (y:ys) = case x`cmp`y of
          LT  -> x : merge xs (y:ys)
          _   -> y : merge (x:xs) ys

然后您可以简单地定义mergeSort = mergeSortBy compare和mergeSortDesc = mergeSortBy (flip compare)。

还要观察创建merge本地函数如何防止您在实现中遇到的错误。

它说它应该声明为：mergeSort :: ([a]->[a]->[a]) -> [a] -> [a] 作为接受合并函数作为第一个参数的函数。 ..

这很奇怪，它不应该被称为mergeSort但是sortWithMerge或什么的。无论如何，这样做很简单：只需抛出cmp（仅在merge子函数中使用！）并将其替换为 merge 作为参数，而不是在本地定义它。

sortWithMerge :: ([a]->[a]->[a]) -> [a] -> [a]
sortWithMerge merger = mSort
 where 
       mSort [] = []
       mSort [x] = [x]
       mSort xs = merger (mSort top) (mSort bottom)
        where (top, bottom) = splitAt (length xs `quot` 2) xs
于 2013-04-06T11:27:31.157 回答