haskell：如何在起始列表中获取高于其邻居的数字列表

3 回答

• 2

  我会按照Thomas M. DuBuisson的说明解决这个问题 . 由于我们希望列表的末尾为"count"，因此我们将在创建三元组之前为每一端添加负无穷大 . monoid-extras包为此提供了合适的类型 .

  import Data.Monoid.Inf
  
  pad :: [a] -> [NegInf a]
  pad xs = [negInfty] ++ map negFinite xs ++ [negInfty]
  
  triples :: [a] -> [(a, a, a)]
  triples (x:rest@(y:z:_)) = (x,y,z) : triples rest
  triples _ = []
  
  isBig :: Ord a => (a,a,a) -> Bool
  isBig (x,y,z) = y > x && y > z
  
  scnd :: (a, b, c) -> b
  scnd (a, b, c) = b
  
  finites :: [Inf p a] -> [a]
  finites xs = [x | Finite x <- xs]
  
  largest :: Ord a => [a] -> [a]
  largest = id
      . finites
      . map scnd
      . filter isBig
      . triples
      . pad
  

  它看起来运作得恰到好处;在ghci：

  > largest [0,1,5,2,3,7,8,4]
  [5,8]
  > largest [10,1,10]
  [10,10]
  > largest [3]
  [3]
  > largest []
  []
  

  您也可以考虑在单个列表推导中合并 finites ， map scnd 和 filter isBig （然后消除 finites ， scnd 和 isBig 的定义）：

  largest :: Ord a => [a] -> [a]
  largest xs = [x | (a, b@(Finite x), c) <- triples (pad xs), a < b, c < b]
  

  但我更喜欢分解版本; finites ， scnd 和 isBig 函数可能会在您的开发中的其他位置变得有用，特别是如果您计划针对不同需求构建一些此类变体 .

  回复于 2024-04-29T20:43:01+08:00
• 0

  你可能尝试的一件事就是前瞻性 . （托马斯·M·杜布森提出了一个不同的方法，如果你正确处理最后一个或两个元素也会有效 . ）因为这听起来像是一个你想要自己解决的问题作为一个学习练习，我会写一个您可以根据需要将骨架作为起点：

  largest :: [Integer] -> [Integer]
  largest [] = _
  largest [x] = _ -- What should this return?
  largest [x1,x2] | x1 > x2   = _
                  | x1 < x2   = _
                  | otherwise = _
  largest [x1,x2,x3] | x2 > x1 && x2 > x3 = _
                     | x3 > x2 = _
                     | otherwise = _
  largest (x1:x2:x3:xs) | x2 > x1 && x2 > x3 = _
                        | otherwise          = _
  

  除了 (x1:x2:x3:[]) 之外，我们还需要 [x1,x2,x3] 的特殊情况，因为根据您的评论中的澄清， largest [3,3,2] 应该返回 [] . 但是 largest [3,2] 应该返回 [3] . 因此，最后三个元素需要特殊处理，不能简单地在最后两个元素上进行递归 .

  如果你还希望结果包含列表的头部，如果它大于第二个元素，你可以使它成为一个辅助函数，你的 largest 就像 largest (x1:x2:xs) = (if x1>x2 then [x1] else []) ++ largest' (x1:x2:xs) . 也就是说，您需要对原始列表的第一个元素进行一些特殊处理，当您递归时，您不希望将这些元素应用于所有子列表 .

  回复于 2024-04-29T20:43:01+08:00
• 3

  正如评论中所建议的，一种方法是首先使用Prelude zip3和tail将列表分组为长度为3的元组：

  *Main> let xs = [0,1,5,2,3,7,8,4]
  *Main> zip3 xs (tail xs) (tail (tail xs))
  [(0,1,5),(1,5,2),(5,2,3),(2,3,7),(3,7,8),(7,8,4)]
  

  其类型分别为： [a] -> [b] -> [c] -> [(a, b, c)] 和 [a] -> [a] .

  接下来，您需要找到一种方法来过滤掉中间元素大于第一个和最后一个元素的元组 . 一种方法是使用Prelude filter函数：

  *Main> let xs = [(0,1,5),(1,5,2),(5,2,3),(2,3,7),(3,7,8),(7,8,4)]
  *Main> filter (\(a, b, c) -> b > a && b > c) xs
  [(1,5,2),(7,8,4)]
  

  其中的类型： (a -> Bool) -> [a] -> [a] . 这将根据从传递的谓词返回的布尔值过滤掉列表的元素 .

  现在，对于最后一部分，您需要从上面过滤的元组中提取中间元素 . 您可以使用Prelude map功能轻松完成此操作：

  *Main> let xs = [(1,5,2),(7,8,4)]
  *Main> map (\(_, x, _) -> x) xs
  [5,8]
  

  其中的类型： (a -> b) -> [a] -> [b] . 此函数将元素从 a 类型的列表映射到 b .

  上面拼凑的代码看起来像这样：

  largest :: (Ord a) => [a] -> [a]
  largest xs = map (\(_, x, _) -> x) $ filter (\(a, b, c) -> b > a && b > c) $ zip3 xs (tail xs) (tail (tail xs))
  

  注意这里我使用了类型类 Ord ，因为上面的代码需要与 > 和 < 进行比较 . 尽管如此，将它保持为 Integer 也没关系 .

  回复于 2024-04-29T20:43:01+08:00