多调用函数的Haskell尾部递归

Question

这里是非尾部递归函数

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负载循环结束。。。

Answer 1

你在Haskell中研究过Fibonacci吗？它是一个类似类型的函数。BTW尾部递归在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。

Answer 2

根据您的问题，还不完全清楚使函数尾部递归的目的是什么。如果你想减少cpu/内存的使用，那么你应该使用内存化（Guvante的回答中提到）。

同时，有一种方法可以使几乎任何函数尾部递归，称为延续传递样式。您在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

请注意，与天真的非尾部递归实现相比，这并没有降低算法复杂性或内存使用量。

Answer 3

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

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提高到适当的幂，就可以得到它们的乘积。

（我还没有真正测试过，但它似乎是正确的。即使不是，我也很确定它背后的想法是合理的）

附言：正如@Guvante所说，Int在这里不是一个好选择，因为它会很快溢出。一般来说，我默认使用Integer，只有在有充分理由的情况下才会切换。

Answer 4

这里有一个可能的解决方案。

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])