按字符串长度对字符串列表排序

Question

我想String根据字符串的长度对第一个列表进行排序,如果长度相同则应该按词法排序.我以为我可以使用该Data.List库并编写我自己的比较函数来做到这一点.所以compare函数应该将一个列表String作为参数并比较所有元素(即Strings).Strings 的比较函数看起来像这样

comp a b
    | length a > length b   = GT
    | length a < length b   = LT

我怎么能用这样的函数解决所有列表元素？

Answer 1

首先,您的cmp函数不处理长度相等的情况:您需要添加它.否则,您将收到运行时模式匹配错误:

comp a b
    | length a > length b   = GT
    | length a < length b   = LT
    | otherwise             = undefined  -- TODO

此外,请注意,此实现有时会计算两次长度,但很可能GHC会自行优化这一长度,并且我们将在以后基本上更好地解决这个问题.

然后,一旦你修复了你comp,你需要做的就是将它Data.List.sortBy与你想要排序的字符串列表一起传递.下面提供了类似的ipmplementation(<$>运算符别名与列表fmap相同map).

但是,有一个更好的解决方案,首先计算列表中所有元素的长度,方法是将每个元素映射到一对,其中第一个成员是原始字符串,第二个成员是其长度.然后使用一个修改过的comp函数,该函数需要2对而不是2个字符串,但其他行为与原始函数相同comp.但是,您需要将中间列表映射回只包含字符串(这就是fst <$>它的用途,相当于map fst但是,再次使用,IMO更好看,操作<$>符).

所以有点天真的解决方案是:

sortByLenOrLex :: [String] -> [String]
sortByLenOrLex as = sortBy cmp as where
  cmp a b | n > m     = GT
          | n < m     = LT
          | otherwise = compare a b
    where n = length a
          m = length b

和更高效的之一,因为leftaroundabout指出,将是:

sortByLenOrLex' :: [String] -> [String]
sortByLenOrLex' as = fst <$> sortBy cmp (addLen <$> as) where
  cmp (a,n) (b,m) | n > m     = GT
                  | n < m     = LT
                  | otherwise = compare a b
  addLen x = (x, length x)

首先使用每个元素的长度修改列表,以避免重复,昂贵的length调用.

编辑:请参阅chi的答案,以便更好地实现此算法!

此外:

您可以通过使它们在以下列表列表上Ord运行来使您的函数具有通用性:

sortByLenOrLex'' :: Ord a => [[a]] -> [[a]]
sortByLenOrLex'' as = fst <$> sortBy cmp (addLen <$> as) where
  cmp (a,n) (b,m) | n > m     = GT
                  | n < m     = LT
                  | otherwise = compare a b
  addLen x = (x, length x)

这给你:

*Main> sortByLenOrLex'' [[1,2], [1,3], [1,2,3]]
[[1,2],[1,3],[1,2,3]]

...如果你想使它尽可能通用,您可以排序的名单Foldable中Ord:

sortByLenOrLex''' :: (Foldable f, Ord a) => [f a] -> [f a]
sortByLenOrLex''' as = unamend <$> sortBy cmp (amend <$> as) where
  cmp (a,n,a') (b,m,b') | n > m     = GT
                        | n < m     = LT
                        | otherwise = compare a' b'
  amend    x      = (x, length x, toList x)
  unamend (x,_,_) =  x

这给你:

*Main> sortByLenOrLex''' [Just 3, Just 4, Just 3, Nothing]
[Nothing,Just 3,Just 3,Just 4]

*Main> sortByLenOrLex''' [(4,1),(1,1),(1,2),(1,1),(3,1)]
[(4,1),(1,1),(1,1),(3,1),(1,2)]

*Main> sortByLenOrLex''' [Left "bla", Right "foo", Right "foo", Right "baz"]
[Left "bla",Right "baz",Right "foo",Right "foo"]

*Main> sortByLenOrLex''' [(3,"hello"),(2,"goodbye"),(1,"hello")]
[(2,"goodbye"),(3,"hello"),(1,"hello")]