时间戳

首页 > 解决方案 > 在 Haskell 的列表中查找最短的列表

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

问题描述

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

这是我正在使用的代码：

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

如果有人能给我任何关于我哪里出错的指示，那将不胜感激！

标签： haskellrecursionminimumtype-mismatch

解决方案

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，您可以将参数写入mapas (length &&& id)。

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

Daniel Wagner 指出了一个更好的 using 解决方案minimum，即将每个元素包装在一个Arg值中，让两个列表仅根据它们的长度进行比较，而不考虑列表的内容。

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

Arg基本上是一种 2 元素产品类型，它只使用第一个元素作为其Ord实例，而不是(,)同时使用两者。

推荐阅读