「Real World Haskell」第三章练习中的代码形式批判

Question

我正在学习《Real World Haskell》，目前在做第三章末尾的练习。

我采取了一种不同寻常的方法：即使我知道他们尚未涵盖的某些语言特性可以帮助我，我仍然尝试使用只有他们明确介绍过的东西来完成这些练习。为什么？只是为了好玩。感觉这迫使我多练习递归。

所以我刚刚完成了以下练习：“创建一个函数，根据每个子列表的长度对列表的列表进行排序。(您可能需要查看Data.List模块中的sortBy函数。)” 现在，他们提供了关于Data.List模块的提示。但他们没有提及参考文档在哪里，如何导入内容等。因此，我决定自己编写排序，只是为了看看自己能否做到。我使用了冒泡排序算法，因为它是最简单的算法。

结果如下。我希望你们擅长Haskell的人能够批评一下...但是请记住以下警告：如果您建议改进，请基于《Real World Haskell》第3章涵盖的语言特性（或者您猜测这些特性而不必费心去查找）。我知道有很多很棒的语言特性等着我，可以让我使代码更好，但现在具体的挑战是使用到目前为止“原始”的特性来完成它。 我相信有些情况下我可能在做无用功，使用显式控制流时递归和模式匹配可能对我更有利等等。我相信代码可以变得更短更易读。我敢打赌我不知道可以与我限制自己使用的原始语言特性一起使用的好习惯。这些是我想收到的提示。

这可能是我以任何语言为荣的最丑陋的代码（至少我能记得的）。我在函数式语言中的第一次尝试，超越了“Hello, world”类型的东西。现在你要把它搞砸 :) 。请温柔点，但我期待一些有见地的洞察力。谢谢。

areListsEqual :: (Eq a) => [a] -> [a] -> Bool

areListsEqual [] [] = True
areListsEqual [] _  = False
areListsEqual _ []  = False

areListsEqual xs ys = (head xs == head ys)  && (areListsEqual (tail xs) (tail ys))

charlieSort :: (Eq a) => [[a]] -> [[a]]

charlieSort [] = []
charlieSort (x:xs) | null xs = [x]
charlieSort xs | (length xs) >= 2 = if(not (areListsEqual xs wip))
                    then charlieSort wip 
                    else wip
                    where
                      first = head xs
                      second = head (tail xs)
                      theRest = drop 2 xs
                      swapPairIfNeeded a b = if(length a >= length b) 
                          then [second, first]
                          else [first, second]
                      modifiedPair = swapPairIfNeeded first second
                      wip = (take 1 modifiedPair) ++ charlieSort ( (drop 1 modifiedPair) ++ theRest)

- Charlie Flowers

---

有人说这不是一个问题。我会尊重并开放地接受这个观点。但我必须问一下，按照什么定义它不是一个问题？你所遵循的标准是否有我不知道的一些标准？我正在寻求改进一些代码的建议。这将帮助我在学习语言方面取得进展。难道这不是一个有效的StackOverflow问题的原因吗？ - Charlie Flowers

我认为这个问题唯一无效的部分是要求人们根据一本随机书籍的随机章节限制他们的改进。否则，我认为这个问题没有任何问题。 - Unknown

谢谢，很高兴你认为这是有效的。至于限制，我只是指人们涉及到TypeClasses和列表推导式或其他什么都是没有意义的。我会继续阅读这本书并最终涉及到所有这些内容，所以我试图将此讨论限制在基础知识上。当然，没有人需要查找这本书（我在问题中已经说过了）...只需限制在基本语言特性上即可。 - Charlie Flowers

@apphacker，既然您继续编辑并应用“不是问题”标签，那么您能否解释一下您的立场呢？这似乎是我合理的要求，您觉得呢？ - Charlie Flowers

关于“文档在哪里”的问题：最简单的方法是使用Hoogle，例如http://haskell.org/hoogle/?q=sortBy - nominolo

想不到啊——你正在做我正在做的那一套问题集。 :) - rtperson

Answer 1

我首先会开始使用模式匹配。

areListsEqual :: Eq a => [a] -> [a] -> Bool
areListsEqual [    ] [    ] = True
areListsEqual [    ] _      = False
areListsEqual _      [    ] = False
areListsEqual (x:xs) (y:ys) = x == y && areListsEqual xs ys

请注意，避免使用 head 和 tail 时，此内容的可读性更高。

charlieSort :: Eq a => [[a]] -> [[a]]
charlieSort    [                    ] = []
charlieSort    [x                   ] = [x]
charlieSort xs@(first:second:theRest)
  | areListsEqual xs wip              = wip
  | otherwise                         = charlieSort wip
  where
  swapPairIfNeeded a b
    | length a >= length b = [second,first]
    | otherwise            = [first,second]
  modifiedPair = swapPairIfNeeded first second
  wip = take 1 modifiedPair ++ charlieSort (drop 1 modifiedPair ++ theRest)

我将if-then-else改为了一种更易读的保护格式，但具体效果因人而异。我们使用模式匹配来代替使用length来检查列表是否至少有两个元素，这样还可以直接命名first、second和theRest。 name @ pattern 模式既可以将输入与pattern匹配，又可以将整个输入命名为name。

现在，我希望避免使用take和drop来提取modifiedPair的两个元素，所以最后两行代码被改为：

  [shorter,longer] = swapPairIfNeeded first second
  wip = [shorter] ++ charlieSort ([longer] ++ theRest)

最后一行可以写成

  wip = shorter : charlieSort (longer : theRest)

如果您喜欢，可以这样做。但是为什么应该在 swapPairIfNeeded 中返回 first 和 second 列表中的 shorter 和 longer 呢？为什么不使用类似于一对的方式呢？

  swapPairIfNeeded a b
    | length a >= length b = (second,first)
    | otherwise            = (first,second)
  (shorter,longer) = swapPairIfNeeded first second

在大多数情况下，固定数量的值（可能是不同类型的）应该使用元组，而变量数量的值（必须是相同类型的）应该使用列表。但是，swapPairIfNeeded比较其参数a和b，然后无论如何返回first和second似乎有些奇怪。在这种情况下，我将完全删除swapPairIfNeeded，而不是让它返回一对a和b：

  (shorter,longer)
    | length first >= length second = (second,first)
    | otherwise                     = (first,second)

将swapPairIfNeeded的主体展开到(shorter,longer)的定义中。

现在，charlieSort的代码如下：

charlieSort :: Eq a => [[a]] -> [[a]]
charlieSort    [                    ] = []
charlieSort    [x                   ] = [x]
charlieSort xs@(first:second:theRest)
  | areListsEqual xs wip              = wip
  | otherwise                         = charlieSort wip
  where
  (shorter,longer)
    | length first >= length second = (second,first)
    | otherwise                     = (first,second)
  wip = shorter : charlieSort (longer : theRest)

最后，我应该指出，charlieSort并没有真正实现冒泡排序，因为对charlieSort的递归调用不仅会沿着列表进行一次“冒泡”遍历，还会完全对longer : theRest列表进行排序，因此在这个递归调用之后（在返回一个“级别”之前），可能需要将shorter移动到其正确的位置。

- ski

---

出色的观点，谢谢。是的，在 swapPairIfNeeded 中存在一些“糟糕的耦合”：它没有理由“知道”a和b，以及first和second。此外，它不需要返回一个列表。这两个都是从早期构建“wip”的尝试中遗留下来的，当时我认为可以将“修改后的对”放在wip的前面。您能帮我看看为什么“charlieSort [x] = [x]”模式无论列表包含多少元素都不匹配吗？ - Charlie Flowers

Answer 2

Charlie: 我只要提出一点批评：如果可以使用模式匹配，永远不要使用head、tail或length：

areListsEqual [] [] = True
areListsEqual (x:xs) (y:ys) = x == y && areListsEqual xs ys
areListsEqual _ _   = False

我无法理解你的排序算法（而且如果您重新格式化问题以消除水平滚动条，那将是礼貌的），但我会将前三行重写为：

charlieSort []  = []
charlieSort [x] = x
charlieSort (x1:x2:xs) = if ...

（附注：所有使用head和tail的地方都可以使用模式匹配进行重写，初学者应该这样做。并非所有使用length的情况都可以通过模式匹配来替换，但常见的新手代码，如length xs == 0或length xs >=2可以重写并应该这样做。）

（另外，即使是经验丰富的Haskell程序员很少使用'head'。格拉斯哥Haskell编译器中不到千分之二的源代码行提到了'head'，仔细观察这些提及，大约一半在字符串文字或注释中。也就是说，每1500行代码中大约有一个使用'head'的地方。）

- Norman Ramsey

---

非常好，谢谢你的建议。我一定会尝试用模式匹配来替换head/length。问题：你的第二个charlieSort模式是“charlieSort [x] = x”。我认为那应该是一个不可反驳的模式。但是有什么原因它不是吗？ - Charlie Flowers

@Charlie：不可否认的模式是始终匹配的模式。[x] 模式仅匹配单元素列表，因此它可以被空列表或两个或更多元素的列表所否定。 - Norman Ramsey

Answer 3

你不需要使用areListsEqual函数。你可以使用(==)函数比较列表。我建议使用快速排序而不是冒泡排序。以下是我认为只使用了你目前应该学到的知识的解决方案。

charlieSort :: (Eq a) => [[a]] -> [[a]]
charlieSort []     = []
charlieSort (x:xs) = charlieSort (filter (cmpLen (>) x) xs) ++ [x] ++
                     charlieSort (filter (cmpLen (<=) x) xs)
   where filter _ [] = []
         filter p (x:xs) = (if (p x) then (x:) else id) (filter p xs)
         cmpLen f x y = f (length x) (length y)

- Apocalisp

---

谢谢。我遇到了这个错误，但是我还没有完全理解你的解决方案，无法弄清楚如何修复：无法匹配预期类型“t1 -> t2 -> t”与推断类型“[a]” 在表达式中：（x :) 在表达式中：（如果p x，则（x :)否则id）过滤器p xs 在“filter”的定义中： filter p（x：xs）=（如果p x，则（x :)否则id）filter p xs - Charlie Flowers

已经修复了，抱歉。这是一个快速的任务。id函数是prelude的一部分。它的定义如下：id x = x - Apocalisp

非常有趣。我看到它能工作。我大概理解了一半。有几个问题：1）看起来cmpLen需要三个参数，但你只用两个调用它。我读对了吗？如果是这样，为什么要这样做？嘿！算了...我刚刚想通了！这是柯里化。非常酷。他们还没有涵盖它，但我以前见过它。你是通过柯里化比较charlieSort的x和filter的x，对吧？2）我无法理解在这种情况下id可能返回什么，以及它如何影响对filter的下一次调用。 - Charlie Flowers

是的，你也可以将 (cmpLen (>) x) 写成 \y -> compLen (>) x y。甚至可以写成 (\x y -> length x > length y)。if 子句返回一个函数。它要么是将 x 前置到列表中的函数，要么是 id 函数。你也可以这样写：if (p x) then x : filter p xs else filter p xs。 - Apocalisp

那么，在if子句返回id函数的情况下，id函数的“结果”是否被使用？还是仅仅作为“占位符”存在，因为if函数必须评估出某些东西？“id”评估的值是否对最终结果有任何影响？ - Charlie Flowers

id 函数的结果始终只是其参数。它是函数 (\x -> x)。从某种意义上说，它“什么也不做”，只是通过传递值。我不知道如何更清楚地表达这一点。在 ghci 中尝试一下吧。 - Apocalisp

Answer 4

我正在第8章，所以我不是老手，但我更喜欢

areListsEqual x:xs y:ys = (x == y) && (areListsEqual xs ys)
areListsEqual [] [] = True
areListsEqual _ _ = False

这似乎更符合 Haskell 风格。

同样地，

charlieSort [] = []
charlieSort (x:[]) = [x]
charlieSort (x1:x2:xs) = blah blah

swapPairIfNeed 已经正常工作，因为你只使用第一个和第二个参数（按顺序）调用它，但你可能是想要的。

swapPairIfNeed a b = if (length a >= length b)
    then [b, a]
    else [a, b]

实际上，我更喜欢charlieSort的第三种情况看起来像这样

charlieSort (x1:x2:xs) = if not (areListsEqual x1:x2:xs wip)
                         then charlieSort wip
                         else wip
    where swapPairIfNeeded a b = if (length a >= length b)
                                 then (b, a)
                                 else (a, b)
          wip = f (swapPairIfNeeded first second)
          f (a, b) = a : (charlieSort b:xs)

我认为这些都在第三章中讲解过了。

现在，让我们来看一下算法。即使我们只使用冒泡排序，也没有必要在排序后检查整个列表。相反，我们可以在需要时交换前两个元素，然后对列表的尾部进行排序。如果头部比已排序的尾部的头部短，那么我们就完成了。

charlieSort (x1:x2:xs) = if (length a <= length (head sortedTail))
                         then a : sortedTail
                         else charlieSort (a : sortedTail)
    where sortedTail = charlieSort (b:xs)
          (a, b) = if (length x1 >= length x2)
                   then (x2, x1)
                   else (x1, x2)

- ruds

---

谢谢。我真的很喜欢“charlieSort（x：[]）= [x]”，比我之前做的要干净得多。另外，有趣的是你似乎在使用“深度优先”方法：我认为你是在排序头部之前先排序尾部。这很有道理，而且是我从未想过的。这对我有帮助，因为现在我意识到整个问题可以简化为这样：找出如何排序前两个条目；然后，一遍又一遍地使用它，直到整个列表都被排序。很酷。 - Charlie Flowers

有趣的是，我刚刚重新阅读了这条评论（是我在一年前写的）。当时我不知道，但在Haskell中，经常会出现一个好的答案是“找出如何对列表中的前两个项目执行foo操作，然后找出如何重复使用它，直到整个列表都被‘foo-d’”。 - Charlie Flowers

Answer 5

你声称冒泡排序是最简单的排序算法，但实际情况并非如此。冒泡排序适用于数组，在其中线性索引。对于Haskell的链表，插入排序实际上更加美观。

让我们从insert函数开始：

winsert :: [a] -> [[a]] -> [[a]]
winsert x [] = [x]
winsert x (y:ys)
    | length x < length y = x : y : ys
    | otherwise = y : winsert x ys

• 如果列表为空，则将x放入其中
• 如果列表不为空：
  • 如果x < y，则x属于列表的前面
  • 否则，列表的头部是y，尾部由将x插入到ys中的某个位置组成。

接下来，我们有实际的排序函数：

wsort :: [[a]] -> [[a]]
wsort [] = []
wsort [x] = [x]
wsort (x:xs) = winsert x (wsort xs)

• 如果列表为空，则返回它
• 如果列表只有一个项目，则不需要排序
• 如果列表长度超过一个以上，先对xs进行排序，然后将x插入到已排序的xs中

有趣的是，通过修改winsert以接受函数作为参数（而不是length），wsort可以用于基于各种标准进行排序。尝试创建一个根据每个子列表的总和对列表进行排序的函数。

- Wesley

---

很好，我喜欢它。我同意它非常干净。你也和我问Norman的问题一样：我认为"wsort [x]"应该是一个无可辩驳的模式（或者至少，它应该与长度从0到无限的任何列表匹配）。显然它不是，因为你们两个都在使用它。那么为什么不呢？谢谢。 - Charlie Flowers

相反，它只匹配一个单一元素的列表。"wsort (x:xs)"将匹配至少有一个元素的任何列表。您可能会将模式匹配与类型签名混淆。 "type [x]"表示其元素为任意类型的列表，但是"pattern [x]"表示只有一个元素的列表。类型仅在"::"之后出现。 - ruds

[x] 匹配只有一个元素的任何列表。然而，x 可以是任何类型，甚至是一个列表本身。如果 x 是这样的子列表，那么该子列表可以是任意长度。[x] 不匹配 [] 或 [1, 2]。[x] 匹配 [1]（x 是 1）、[[]]（x 是 []）、[[1]]（x 是 [1]）和 [[1, 2]]（x 是 [1, 2]）。 - Wesley