Haskell 多调用函数的尾递归

Haskell tail recusion for multi call function

这里是非尾递归函数

alg :: Int -> Int
alg n = if n<7 then n else alg(n-1) * alg(n-2) * alg(n-4) * alg(n-6)

我已经坚持了一段时间,我了解了尾递归的基本概念,以及如何为单次调用递归函数做,但不知道如何为多次调用递归做。

连这个可恶的东西都想出来了

algT :: Int -> Int
algT n = tail1 n 0 where tail1 i r = tail1(i-1) r *
         tail2 n 0 where tail2 i r = tail2(i-2) r *
         tail3 n 0 where tail3 i r = tail3(i-4) r *
         tail4 n 0 where tail4 i r = tail4(i-6) r

它不起作用,显然不是递归函数的样子,几乎没有其他尝试,但所有这些都以无限的 100% cpu 加载循环结束...

我想我有一个解决方案,但它不是很优雅或漂亮。

alg :: Int -> Int
alg n | n < 7     -> n
      | otherwise -> alg' n (repeat 0)

alg' :: Int -> [Int] -> Int
alg' n [] = error "something has gone horribly wrong"
alg' n l@(x:y)
  | n < 5     -> error "something else has gone horribly wrong"
  | n == 6    -> product $ zipWith (^) [6,5..1] l
  | otherwise -> alg' (n-1) $ zipWith (+) [x,x,0,x,0,x] (y ++ [0])

我们的想法是,您可以跟踪应该将每个事物相乘多少次,而无需实际进行任何计算,直到最后。在任何给定时间,您都知道您需要接下来的 6 个值中的任何一个的次数,一旦低于 7,您只需将 1-6 提高到适当的幂并取其乘积。

(我还没有实际测试过,但它似乎是正确的。即使不是,我也很确定它背后的想法是正确的)

P.S。正如@Guvante 所说, Int 在这里不是一个好的选择,因为它会很快溢出。作为一般规则,我默认使用 Integer,只有在有充分理由的情况下才会切换。

你研究过 Haskell 中的斐波那契数列吗?它是一种类似的功能。顺便说一句,尾递归在 Haskell 中不是很正确的术语,因为多重递归函数不能真正递归地完成,但是 Haskell 的惰性使类似但更强大的技巧成为可能。这是给出的标准:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

对你使用同样的技巧得到编辑:作为一个函数

alg :: Int -> Int
alg n = alg' !! (n - 1)
    where alg' = 1 : 2 : 3 : 4 : 5 : 6 : zipWith4 (\a b c d -> a * b * c * d) (drop 5 alg') (drop 4 alg') (drop 2 alg') alg'

请注意,您不应在此处使用 Int,它不是开放式的,第 11 项将在 Int.

中循环

编辑:实际上 Int 比我想象的还要糟糕。一旦你在结果中命中 32 个 2,你将开始返回 0,因为每个答案都是 0 mod 2^32.

从你的问题来看,并不完全清楚使你的函数尾递归的目的是什么。如果你想减少 cpu/memory 使用,那么你应该使用记忆(在 Guvante 的回答中提到)。

同时,有一种方法可以使几乎所有函数尾递归,称为 continuation-passing style。您在 CPS 中编写的示例如下所示:

alg_cps :: Integer -> (Integer->a) -> a
alg_cps n cont = 
    if n < 7 
    then cont n 
    else alg_cps (n - 1) 
        (\x1 -> alg_cps (n - 2) 
            (\x2 -> alg_cps (n - 4) 
                (\x3 -> alg_cps (n - 6)
                    (\x4 -> cont (x1*x2*x3*x4)))))

要直接获得结果,您可以使用 id 继续调用它:

alg_cps 20 id

请注意,与简单的非尾递归实现相比,这不会降低算法复杂性或内存使用量。

这是一个可能的解决方案。

let f = [1..6] ++ foldr1 (zipWith (*)) [f, drop 2 f, drop 4 f, drop 5 f]

甚至:

let f = [1..6] ++ foldr1 (zipWith (*)) (map (flip drop $ f) [0,2,4,5])