在 Haskell 中的列表列表中查找最短列表

Question

我在使用 Haskell 编写的程序时遇到了一些困难。它背后的想法是递归地找到列表列表中的最短列表 return 。我已经成功地编写了程序，但我似乎无法弄清楚我在其中做错了什么。这些是我在尝试编译时遇到的错误：

无法将类型“a”与“[[a]]”匹配，“a”是受类型签名绑定的严格类型变量：最短 :: forall a。 [[a]] -> [a] 在 shortest.hs:1:13。预期类型：[[[a]]]，实际类型：[a]
在'最短'的第一个参数中，即'y'。在‘(:)’的第一个参数中，即‘shortest y’。在表达式中：最短 y : [list]
相关绑定包括list :: [[a]]（绑定在shortest.hs:4:15），y :: [a]（绑定在shortest.hs:4:13）， x :: [a]（绑定在 shortest.hs:4:11），最短的 :: [[a]] -> [a]（绑定在 shortest.hs:2:1）。

这是我使用的代码：

shortest :: [[a]] -> [a]
shortest [] = []
shortest [y] = y
shortest (x:y:list)
   | length x > length y = shortest y:[list]
   | otherwise = shortest x:[list]

如果有人能指出我哪里出错了，将不胜感激！

Answer 1

我认为您只需要括号：shortest (y:list) 和 x 情况相同。

: 的优先级使其读起来像 (shortest y) : list

Answer 2

list已经是你输入的尾巴了；您不需要（也不应该）将其包装在另一个列表中。

shortest (x:y:list) = shortest $ (if length x > length y then y else x) : list

在每一步中，问题只是从递归调用的输入中删除哪个元素 x 或 y。

另一种不需要两个基本情况的方法是只比较列表的头部和尾部递归的结果。

shortest [] = []
shortest (x:xs) = let s = shortest xs
                  in if length s < length x then s else x

最后，元组按字典顺序进行比较，因此您还可以通过使用长度标记每个列表、找到最小的标记值，然后提取原始列表来免除显式递归。

shortest = snd . minimum . map (\x -> (length x, x))

使用 Control.Arrow，您可以将 map 的参数写为 (length &&& id)。

注意最后一种方法：由于列表也按字典顺序进行比较，如果您有多个长度最短的列表，最终结果将取决于列表值本身的比较方式。相比之下，前两个例子是稳定的；返回第一个这样的最短列表。

Daniel Wagner 指出了使用 minimum 的更好解决方案，即将每个元素包装在一个 Arg 值中，这样可以 单独比较两个列表 的长度，而不考虑列表的内容。

import Data.Semigroup
shortest xs = x where Arg _ x = minimum [Arg (length x) x | x <- xs]

Arg 基本上是一个 2 元素产品类型，仅使用第一个元素作为其 Ord 实例，不像 (,)两者都用。

Answer 3

  shortest []=[]
  shortest [y] = y
  shortest (x:y:list)
   |length x > length y = shortest (y:list)            
   |otherwise = shortest (x:list)

这行得通 :)，另外值得一提的是，如果列表中有 2 个或多个元素 "shortest"，第一个元素将始终弹出。

即

   Prelude>shortest[[1],[2],[3]]
   [1]

Answer 4

import Data.List
import Data.Ord
shortest list = minimumBy (comparing length) list

免分：

shortest = minimumBy (comparing length)

这些库包含在 GHC 中。他们的名字说明了他们做得很好。也许为空列表添加一个单独的案例。

在 Haskell 中的列表列表中查找最短列表

Finding the shortest list in a list of lists in Haskell

recursion

haskell

minimum

type-mismatch