求解Advent of Code 2022 Day4：Haskell元组列表过滤报错问题

我正在解决Advent of Code 2022第4题，需求是过滤一个由元组列表构成的列表，找出所有其中两个元组存在包含关系的元素。

示例数据 #

sample = [[(2,4),(6,8)],[(2,3),(4,5)],[(5,7),(7,9)],[(2,8),(3,7)],[(6,6),(4,6)],[(2,6),(4,8)]]

该数据通过Data.Text.splitOn和元组转换函数(\[x,y] -> (x,y))生成。

辅助函数 #

我编写了判断包含关系的辅助函数：

contains :: (Int,Int) -> (Int,Int) -> Bool
contains a b = (fst a) <= (fst b) && (snd a) <= (snd b)

错误尝试与报错 #

我想要用filter过滤示例数据，但多次尝试都失败了。我的main函数如下：

main :: IO ()
main = do
  print $ length $ map solution sample

尝试1 #

solution :: [(Int,Int)] -> [Bool]
solution = filter (\x y -> x `contains` y || y `contains` x)

报错：

Couldn't match type ‘(Int, Int)’ with ‘Bool’
      Expected: [(Int, Int)] -> [Bool]
        Actual: [(Int, Int)] -> [(Int, Int)]
    • In the expression:
        filter (\ x y -> x `contains` y || y `contains` x)

尝试2 #

solution :: [(Int,Int)] -> [(Int,Int)]
solution = filter (\x y -> x `contains` y || y `contains` x)

报错：

Couldn't match type ‘(Int, Int)’ with ‘Bool’
      Expected: [(Int, Int)] -> [Bool]
        Actual: [(Int, Int)] -> [(Int, Int)]
    • In the expression:
        filter (\ x y -> x `contains` y || y `contains` x)

尝试3 #

solution :: [(Int,Int)] -> [(Int,Int)]
solution = filter (\[x,y] -> x `contains` y || y `contains` x)

报错：

• Couldn't match expected type: (Int, Int)
                  with actual type: [(Int, Int)]
    • In the pattern: [x, y]
      In the first argument of ‘filter’, namely
        ‘(\ [x, y] -> x `contains` y || y `contains` x)’
      In the expression:
        filter (\ [x, y] -> x `contains` y || y `contains` x)

我尝试了各种写法都没解决，请问问题出在哪？

错误分析与解决方法 #

1. filter用法误解 #

filter的作用是筛选列表中满足条件的元素，它的参数是单参数的布尔判断函数（a -> Bool）和目标列表（[a]），返回符合条件的元素组成的列表。

你的sample中每个元素是[(Int,Int)]（长度为2的元组列表），所以你需要的是一个判断[(Int,Int)]是否满足“两个元组有包含关系”的函数，然后用filter直接处理sample，而不是用map。

2. Lambda参数与函数类型错误 #

• 你写的\x y -> ...是双参数函数，但filter需要的是接收单个元素（即[(Int,Int)]）的单参数函数，类型不匹配。
• 你给solution定义的返回类型错误：判断函数应该返回Bool，而不是[Bool]或[(Int,Int)]。
• \[x,y] -> ...是对[(Int,Int)]进行模式匹配，但你把solution的返回类型写成了列表，导致类型不匹配。

3. contains函数逻辑错误 #

原contains函数判断的是“a的区间完全在b的左侧”（a的起始和结束都≤b的），这不是包含关系。正确的包含关系应该是：a的起始≤b的起始，且a的结束≥b的结束（即a完全包含b）。

正确写法 #

修正contains函数

contains :: (Int, Int) -> (Int, Int) -> Bool
contains (aStart, aEnd) (bStart, bEnd) = aStart <= bStart && aEnd >= bEnd

编写判断包含关系的函数

hasContainment :: [(Int, Int)] -> Bool
hasContainment [x, y] = contains x y || contains y x
hasContainment _ = False  -- 容错处理非二元组列表的情况

修正main函数

main :: IO ()
main = do
  let sample = [[(2,4),(6,8)],[(2,3),(4,5)],[(5,7),(7,9)],[(2,8),(3,7)],[(6,6),(4,6)],[(2,6),(4,8)]]
  print $ length $ filter hasContainment sample

运行后会输出3，对应示例中符合条件的3组元组：[(2,8),(3,7)]、[(6,6),(4,6)]、[(2,6),(4,8)]。

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