haskell - 你能得到列表理解中的匹配计数吗(尝试在阈值后对 qsort 进行插入排序)

Question

我有 C++ 背景，所以我不确定我是否正确地处理了这个问题。但我想做的是编写快速排序，但如果列表的长度小于某个阈值，则回退到插入排序。到目前为止，我有这段代码:

insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

quickSort :: (Ord a) => [a] -> [a]
quickSort x = qsHelper x (length x)

qsHelper :: (Ord a) => [a] -> Int -> [a]
qsHelper [] _ = []
qsHelper (x:xs) n 
    | n <= 10 = insertionSort xs
    | otherwise =  qsHelper before (length before) ++ [x] ++ qsHelper after (length after)
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

现在我关心的是每次计算每个列表的长度。我不完全理解 Haskell 如何优化事物或惰性评估对上述代码的完整影响。但似乎为列表理解之前和之后的每个计算列表的长度不是一件好事？有没有一种方法可以让您在执行列表推导时提取列表推导中发生的匹配项的数量？

即如果我们有 [x | x <- [1,2,3,4,5], x > 3] (结果为 [4,5])我可以在不调用 length 的情况下获得 [4,5] 的计数吗？

感谢您的帮助/解释!

Answer 1

简短的回答:没有。

不太简短的回答:是的，你可以伪造它。 导入 Data.Monoid，然后

    | otherwise =  qsHelper before lenBefore ++ [x] ++ qsHelper after lenAfter
        where
            (before, Sum lenBefore) = mconcat [([a], Sum 1) | a <- xs, a < x]
            (after, Sum lenAfter) = mconcat [([a], Sum 1) | a <- xs, a >= x]

---

更好的答案:你不想。

避免 length 的常见原因包括:

• 它的运行时间是 O(N)
  • 但无论如何构建列表都需要 O(N)
• 它强制列表脊柱严格
  • 但我们正在对列表进行排序:我们必须(至少部分地)评估每个元素，以便知道哪个是最小的；列表脊柱已经强制严格
• 如果您不关心列表的长度，只关心它是否比另一个列表或阈值短/长，length 是浪费:它会一直走到列表的末尾无论如何列出
  • 宾果

isLongerThan :: Int -> [a] -> Bool
isLongerThan _ []     = False
isLongerThan 0 _      = True
isLongerThan n (_:xs) = isLongerThan (n-1) xs

quickSort :: (Ord a) => [a] -> [a]
quickSort []     = []
quickSort (x:xs) 
    | not (isLongerThan 10 (x:xs)) = insertionSort xs
    | otherwise =  quickSort before ++ [x] ++ quickSort after
        where
            before = [a | a <- xs, a < x]
            after = [a | a <- xs, a >= x]

这里真正的低效是在 before 和 after 中。它们都遍历整个列表，将每个元素与 x 进行比较。因此，我们两次遍历 xs，并将每个元素与 x 进行两次比较。我们只需要做一次。

            (before, after) = partition (< x) xs

partition在 Data.List 中。