haskell - 在递归调用中向后传播信息

Question

如何在递归调用链中向后传播信息？

例如:

f :: [Int] -> [Int]
f (x:xs)
  | x `mod` 17 = ...
  | otherwise = (x + 1) : f xs
f [] = []

我想在...停止评估，并且我还想将该信息传播回调用者(它停止的事实)。我尝试使用像 Maybe 这样的返回类型，但随后我必须对递归调用进行模式匹配，从而失去尾部调用优化，因为我必须在调用返回后对其进行评估(注意:可以轻松地将上面的代码转换为TR 形式，但我这样保留是为了更容易理解)。

您能否提出一个仍能从 TCO 中受益的更好解决方案？

Answer 1

您始终可以使用额外的参数，并返回一个包含累积结果的元组。这样您仍然可以从 TCO 中受益，并获得所需的信息。

一个例子:

f :: [Int] -> Bool -> [Int] -> (Bool, [Int])
f (x:xs) l accum
  | x `mod` 17 == 0 = (False, accum)
  | otherwise       = f xs l ((x+1) : accum)
f [] l accum = (True, accum)

或者以更优雅的方式:

data CheckedValue a = Valid a | Invalid a
  deriving Show

f :: [Int] -> [Int] -> CheckedValue [Int]
f (x:xs) accum
  | x `mod` 17 == 0 = Invalid accum
  | otherwise       = f xs ((x+1) : accum)
f [] accum = Valid accum

注意:这些函数也会反转列表，但不必注意这一点。