相关疑难解决方法(0)

在Wikibooks的Haskell中,有以下声明:

Data.List提供用于排序列表的排序功能.它不使用quicksort; 相反,它使用称为mergesort的算法的有效实现.

Haskell使用mergesort而不是quicksort的根本原因是什么？Quicksort通常具有更好的实际性能,但在这种情况下可能不是.我认为快速排序的现场好处很难(不可能？)与Haskell列表有关.

关于so​​ftwareengineering.SE有一个相关的问题,但实际上并不是为什么使用 mergesort.

我自己实现了两种类型的分析.Mergesort是优越的(大约是2 ^ 20个元素列表的两倍),但我不确定我的quicksort实现是否最佳.

编辑:这是我的mergesort和quicksort的实现:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) …

我目前正在通过在线学习你的Haskell书籍的方式,并且已经到了一个章节,作者正在解释一些列表连接可能效率低下:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下.作者提出的解决方案是使用定义为的"差异列表"

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么DiffList在某些情况下比简单串联更具计算效率.有人可以用简单的语言向我解释为什么上面的例子是如此低效,以及DiffList以什么方式解决了这个问题？

Haskell初学者在这里：二叉树的中序遍历很简单，例如：

data IntegerTree = Leaf Integer
                 | Node IntegerTree Integer IntegerTree

inorder :: IntegerTree -> [Integer]
inorder (Leaf n)     = [n]
inorder (Node l n r) = inorder l ++ [n] ++ inorder r

然而，在我看来，必须有一个更有效的实现。由于列表是单链表，串联inorder l和[n]似乎浪费，特别是因为这种工作是为一棵大树进行多次。我可以通过以不同的方式编写相同的函数来避免这个问题吗？

我最初是在尝试解决以类似方式构建移动列表的河内塔难题时考虑到这一点的，我希望可以使用类似的递归算法解决许多问题。