在递归电话中向后传播信息

Question

我如何在递归呼叫链中向后传播信息？

例如：

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

我想停止在...的评估，我也想将这些信息传播回呼叫者（它停止的事实）。我尝试使用返回类型，但后来我必须对递归调用进行模式，从而丢失了尾巴的优化，因为我必须在返回呼叫后进行评估（注意：一个人可以轻松地将上述代码转换为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

注意：这些功能也扭转了列表，但不关注。