sorting - 代码形式的批判 Real World Haskell，第 3 章练习

Question

关闭。这个问题是opinion-based .它目前不接受答案。












想改进这个问题？更新问题，以便 editing this post 可以用事实和引用来回答它.


上个月关门。







Improve this question




我正在处理 Real World Haskell ，目前正在做第 3 章末尾的练习。

我采取了一种不同寻常的方法:尽管我知道他们还没有涵盖一些对我有帮助的语言功能，但我仍在尝试仅使用他们明确涵盖的内容来进行这些练习。 为什么？真的只是为了好玩。感觉就像它迫使我给我的大脑一些额外的递归练习。

所以我刚刚完成了如下的练习: “创建一个函数，根据每个子列表的长度对列表列表进行排序。(您可能需要查看 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)

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给守卫稍微提高可读性
(YMMV)。而不是检查列表是否至少有两个元素
调用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返回 shorter和longer的first和 second列表中的列表？为什么不使用
对像

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

?在大多数情况下，最好将元组用于固定数量的
值(可能是不同的类型)并使用列表来表示可变数量的
值(必须是相同类型)。但这似乎很奇怪swapPairIfNeeded比较它的参数 a和 b , 但随后返回first和 second反正。在这种情况下，不要让它返回 a和 b在一对中，我将删除 swapPairIfNeeded完全相反:

  (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对其
正当的地方。