修复Haskell生成器的andAlso函数：测试结果不一致问题

问题背景 #

实现Haskell生成器时，andAlso函数用于为生成器添加额外谓词过滤，但部分测试用例无法返回所有预期值，仅能得到第一个满足条件的元素或部分结果。

生成器与相关函数定义 #

生成器类型定义 #

-- Type definition for a generator: a function producing a sequence of values
-- 1. The first function generates the next value.
-- 2. The second function checks if generation should continue.
-- 3. The third value is the initial value, or seed. It does not count as being generated by the generator.
type Generator a = (a -> a, a -> Bool, a)

当前andAlso实现 #

-- Adds an additional predicate to a generator.
andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p (f, g, s) = (f, \x -> g x && p x, s)

测试辅助函数takeGen #

takeGen :: Int -> ((a -> a), (a -> Bool), a) -> [a]
takeGen 0 _ = []
takeGen n (next, pred, seed)
  | not (pred seed) = []
  | otherwise = seed : takeGen (n-1) (next, pred, next seed)

测试用例及异常结果 #

部分测试用例不符合预期：

-- Test 1: Filter for odd numbers
takeGen 10 (andAlso (\x -> x `mod` 2 == 1) ((+1), (<10), 0))
-- Expected: [1,3,5,7,9], but getting: [1]

-- Test 2: Filter for numbers divisible by 3
takeGen 10 (andAlso (\x -> x `mod` 3 == 0) ((+1), (<10), 0))
-- Expected: [0,3,6,9], but getting: [0]

其余测试用例（如过滤大于5的数、组合谓词、步长为2的生成器）均正常工作。

问题分析 #

核心问题出在**takeGen的逻辑设计**：
当前takeGen在遇到不满足谓词的seed时直接返回空列表，终止生成流程，而非跳过该seed继续寻找下一个满足条件的元素。

以测试1为例：
生成到元素2时，2不满足奇数的谓词，takeGen直接停止生成，不会继续查找3、5等后续满足条件的元素，最终仅返回第一个有效元素1。

当前andAlso的实现逻辑是将新谓词与原生成器的终止谓词做逻辑与，本身并无错误，但takeGen未处理“跳过不满足条件的元素”的场景，导致过滤逻辑失效。

修复方案 #

修改takeGen函数，使其在遇到不满足谓词的seed时，递归调用自身并传入下一个seed，而非直接终止：

takeGen :: Int -> Generator a -> [a]
takeGen 0 _ = []
takeGen n gen@(next, pred, seed)
  | not (pred seed) = takeGen n (next, pred, next seed)  -- 跳过不满足条件的seed，继续查找
  | otherwise = seed : takeGen (n-1) (next, pred, next seed)

修复逻辑说明 #

• 当seed不满足谓词时，不终止生成，而是使用next seed作为新的seed继续尝试生成
• 只有当n减至0，或seed不满足原生成器的终止谓词（即g x为False）时，才会停止生成

验证测试 #

修复后的takeGen运行测试用例：

• 测试1返回[1,3,5,7,9]，符合预期
• 测试2返回[0,3,6,9]，符合预期
• 其余原有正常测试用例仍保持正确输出

补充方案（修改andAlso实现） #

若希望在andAlso层面实现过滤逻辑（无需修改takeGen），可调整andAlso的实现，让生成器自动跳过不满足条件的元素：

andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p gen@(next, g, s) = (findValidNext, g, initialValidSeed)
  where
    -- 找到第一个同时满足原生成器条件和新谓词的元素
    findValidSeed x
      | g x && p x = x
      | not (g x) = x  -- 原生成器终止，返回当前值（后续takeGen会处理终止）
      | otherwise = findValidSeed (next x)
    -- 初始seed调整为第一个满足条件的元素
    initialValidSeed = findValidSeed s
    -- 生成下一个有效元素
    findValidNext x = findValidSeed (next x)

这种方式将过滤逻辑内置于生成器中，但实现相对复杂。

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