主页 / coding / 问题 / 79553310
Accepted
Simon Abadi
Asked: 2025-04-03 23:03:24 +0800 CST

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

  • 772

我正在使用 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]

-- Test 3: Filter for numbers greater than 5
takeGen 10 (andAlso (>5) ((+1), (<10), 0))
-- Works correctly: [6,7,8,9]

-- Test 4: Combine two additional predicates
takeGen 10 (andAlso (>3) (andAlso (<8) ((+1), (<10), 0)))
-- Works correctly: [4,5,6,7]

-- Test 5: Test with a different generator function
takeGen 10 (andAlso (<15) ((+2), (<20), 1))
-- Works correctly: [1,3,5,7,9,11,13]

takeGen 10 (andAlso (<10) ((+1), (<10), 0))
-- Works correctly: [0,1,2,3,4,5,6,7,8,9]

我尝试过的方法

我尝试过的各种实现andAlso，包括：

  1. 当前实现如上所示
  2. 调整谓词在序列中的应用方式
  3. 尝试找到满足两个谓词的第一个有效值

一些测试用例运行正常，但其他测试用例（特别是测试 1 和 2）并未返回所有预期值。

我的问题

我的实现有什么问题andAlso？我应该如何修复它才能使所有测试用例按预期工作？问题在于生成器的定义方式、takeGen工作原理，还是andAlso附加谓词的应用方式？

其他背景信息

我已经实现的其他与生成器相关的功能：

nthGen :: Integer -> Generator a -> a
nextGen :: Generator a -> Generator a
lengthGen :: Generator a -> Integer
hasLengthOfAtLeast :: Integer -> Generator a -> Bool
constGen :: a -> Generator a
foreverGen :: (a -> a) -> a -> Generator a
emptyGen :: Generator a

感谢您帮助我了解我的实施出了什么问题。

haskell

1 个回答

  1. Best Answer

    请注意，我无法将您的测试结果与您提供的版本进行匹配andAlso。（例如，我得到的错误答案比您多。）

    但是，看起来您已经实现了andAlso将提供的谓词添加到生成器的延续规则中，但测试用例表明它应该被视为生成器的过滤器。

    例如，对于“测试 1”，您的实现仅在谓词为真且谓词为真andAlso时才继续生成值。但是，由于第二个谓词的第一个种子失败，因此此测试生成一个空列表（这是我使用您的代码得到的）。相反，您希望只要成功就继续生成值，但只“传递”满足的值子集。(<10)\x -> x `mod` 20[](<10)\x -> x `mod` 2

    直接实现起来有点费脑力andAlso，所以您可能需要遵循@user2407038 的建议并尝试实现fromList和toList。

    但是，如果你想要一个直接的解决方案，这里有几个提示。考虑模板定义：

    andAlso p (f, g, s) = (f', g', s')

    让我们假设这个生成器永远不会停止（因此g和g'无关紧要）。f'和应该是什么s'样子？好吧，你希望s'成为满足的Generator序列中的第一个值。所以写：[s, f s, f (f s), ...]p

    where s' = find p (f, g, s)

    并实施：

    find :: (a -> Bool) -> Generator a -> a
find p (f, g, a) = ...

    这里find应该通过如下测试：

    λ> find even ((+1), (<100), 0)
0
λ> find odd ((+1), (<100), 0)
1
λ> find (>10) ((+3), (<100), 0)
12

    g先不要担心停止规则find...我们马上就会解决这个问题。

    那么 呢f'？好吧，f'需要将当前种子（无论它是什么）快进到满足 的t序列中的下一个种子。所以，它只是：[f t, f (f t), ...]p

    where f' t = find p (f, g, f t)

    （请注意使用f t代替t以确保我们不会在 处停止t。）

    那么，如何停止呢？好吧，这里我们要小心，在第一个不满足谓词的生成值处停止g，不管它是否满足我们的过滤谓词p。

    我们可以通过修改来确保这一点，find这样当g满足时它就会停止，即使生成的种子失败了p。这将确保s'设置为停止值，因此生成器的进一步处理将停止，因为g s'将为假。

    因此，请find根据需要进行修改，以便它能够通过上述测试并且能够与以下环境兼容：

    λ> find (>10) ((+1), (<5), 0)
5

    也就是说，它应该“找到”第一个不符合延续谓词的元素(<5)，即使该元素不满足过滤谓词(>10)。

    使用该版本find，您应该能够编写：

    andAlso :: (a -> Bool) -> Generator a -> Generator a
andAlso p (f, g, s) = (f', g, s')
  where s' = find p (f, g, s)
        f' t = find p (f, g, f t)

    并让它通过所有测试。

    • 0

相关问题