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

Question

我在使用Haskell编写的程序中遇到了一些困难。其背后的思想是递归地在一个列表中找到最短的列表并返回该列表。我已经设法把程序写得很好，但我似乎不知道我在其中做错了什么。这些是我尝试编译时得到的错误：

• 无法将类型“a”与“[[a]]”匹配，“a”是一个严格的类型变量，由类型签名绑定的类型为：seltest：：forall a。短时间内。HS:1:13。预期类型:[[[a]]]，实际类型:[a]
• 在“最短”的第一个论元中，即“y”。在'(:)'的第一个参数中，即最短的y。在表达式：最短y:[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 (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))

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