Haskell中如何遍历对比波浪型List？能否泛化适配其他模式？

Hey there! Since you're new to Haskell but comfortable with other languages, let's break this down using functional programming principles—no manual index tracking needed, we'll lean into Haskell's list-handling strengths.

1. 实现波浪型列表判断 #

首先明确需求：我们要验证一个列表是否符合**首元素<次元素>第三元素<第四元素>...**的严格交替大小关系（相等元素直接不符合）。

在Haskell里，我们可以通过以下步骤实现：

• 把列表转换成相邻元素的配对（比如[1,3,2,4]变成[(1,3),(3,2),(2,4)]）
• 对每一对元素做比较，得到Ordering类型的序列（LT表示小于，GT表示大于，EQ表示相等）
• 检查这个序列是否严格遵循LT → GT → LT → GT...的交替规律，且没有EQ

直接上代码：

isWavy :: Ord a => [a] -> Bool
isWavy xs
  -- 空列表或单元素列表默认符合条件（没有违反规则的可能）
  | length xs <= 1 = True
  | otherwise = let
      -- 生成相邻元素对的比较结果序列
      cmpSequence = map (uncurry compare) (zip xs (tail xs))
      -- 检查序列是否从LT开始，交替GT/LT
      checkAlternating _ [] = True
      checkAlternating expected (o:os)
        | o == expected = checkAlternating (flipOrder expected) os
        | otherwise = False
      flipOrder LT = GT
      flipOrder GT = LT
      flipOrder EQ = EQ  -- 不会走到这里，因为下面会过滤EQ
    in all (/= EQ) cmpSequence && checkAlternating LT cmpSequence

举几个测试例子：

• isWavy [1,3,2,4] → True
• isWavy [5,3,4,2] → False（不符合首元素小于次元素的要求）
• isWavy [1,2,3] → False（连续两个LT，违反交替规则）
• isWavy [2,2,1] → False（存在相等元素，不符合严格大小要求）

2. 泛化到其他模式 #

当然可以！函数式编程的核心优势之一就是抽象和复用，我们可以把“要遵循的模式”抽离成参数，让函数适配任意重复的大小关系模式。

比如，我们可以写一个通用函数，接受一个Ordering的模式列表（比如[LT, GT]或者[GT, LT, GT]），然后检查列表是否循环遵循这个模式：

isPatternCycling :: Ord a => [Ordering] -> [a] -> Bool
isPatternCycling pattern xs
  | length xs <= 1 = True
  | null pattern = True  -- 空模式默认视为符合（可根据需求调整）
  | otherwise = let
      cmpSequence = map (uncurry compare) (zip xs (tail xs))
      -- 循环匹配模式
      matchCycle _ [] = True
      matchCycle pat (c:cs) = case pat of
        (p:ps) -> if c == p then matchCycle ps cs else False
        [] -> matchCycle pattern (c:cs)  -- 模式用完后从头循环
    in all (/= EQ) cmpSequence && matchCycle pattern cmpSequence

现在，原来的isWavy就可以用这个通用函数简化实现：

isWavy :: Ord a => [a] -> Bool
isWavy = isPatternCycling [LT, GT]

如果我们需要另一种波浪模式（比如首元素>次元素<第三元素>...），只需要调用：

isReverseWavy :: Ord a => [a] -> Bool
isReverseWavy = isPatternCycling [GT, LT]

甚至可以适配更复杂的自定义模式，比如[LT, LT, GT]循环：

isCustomPattern :: Ord a => [a] -> Bool
isCustomPattern = isPatternCycling [LT, LT, GT]

这个方案的灵活性很高，只要你能把模式用Ordering序列表示，就能轻松验证列表是否符合。

内容的提问来源于stack exchange，提问作者Atir