Haskell中对比变量列表与无限列表找首个未出现值及报错解决

编译错误原因 #

你看到的报错完全来自代码里的一行语法错误：

ourFilter p (x:xs) | matches x = x ourFilter xs

这里你漏掉了列表的Cons运算符:，也没有给递归调用的ourFilter传递第一个参数p。Haskell会把空格解析为函数调用，所以编译器会误以为你要把字符串类型的x作为函数，传入ourFilter和xs两个参数执行，自然会报「字符串类型不能作为函数调用」的类型 mismatch 错误。

逻辑问题 #

除了语法错误之外，你的实现逻辑也存在偏差：

• 你要找的是不在输入列表中的变量，你写的matches函数反而在判断元素是否存在于无限候选列表variables里，判断条件完全写反
• 你定义的ourFilter第一个参数p（应该是传入的已使用变量列表）全程没有被用到，matches函数硬编码了全局的variables，函数复用性为0

如果你要自己实现过滤逻辑，改完的正确版本如下：

ourFilter :: [Var] -> [Var] -> [Var]
ourFilter _ [] = []
ourFilter used (x:xs)
  | x `notElem` used = x : ourFilter used xs -- 补上:操作符，传递used参数，修改判断条件
  | otherwise = ourFilter used xs

调用时执行head $ ourFilter input variables即可得到预期结果。

你的思路方向是对的：过滤无限列表，取第一个符合条件的元素即可。因为Haskell是惰性求值，过滤操作不会遍历整个无限列表，拿到第一个匹配结果就会终止，完全符合需求。不需要自己手写过滤逻辑，直接用标准库的filter即可：

type Var = String

-- 第一个参数：已使用的变量列表；第二个参数：无限候选变量列表；返回值：第一个可用变量
firstAvailable :: [Var] -> [Var] -> Var
firstAvailable used candidates = head $ filter (`notElem` used) candidates

测试示例：

input = ["a", "b", "x"]
variables = ["a", "b", "c", "d", "a1", "b1"] <> cycle [] -- 模拟无限列表
main = print $ firstAvailable input variables -- 输出结果为 "c"

性能优化版本（适用于已使用变量较多的场景） #

如果已使用的变量列表很大，elem的线性查找效率很低，可以转成Set做O(1)查找：

import qualified Data.Set as Set

firstAvailableFast :: [Var] -> [Var] -> Var
firstAvailableFast used candidates = head $ filter (`Set.notMember` usedSet) candidates
  where usedSet = Set.fromList used

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