多通话功能

这里哈斯克尔尾recusion是非尾递归函数多通话功能

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

来源

2015-02-11 Aistis Taraskevicius

我什至不知道有一种方法，使这项严格尾递归。 – 2015-02-11 22:52:13

@LouisWasserman在我看来，应该可以获得可以用循环尾部递归生成的任何序列的元素。 – genisage 2015-02-11 22:56:19

没错。你必须完全改变算法，但是，这不仅仅是一个简单的转换。 – 2015-02-11 22:57:09

从你的问题来看，它不完全清楚你的功能尾回复驱动的目的是什么。如果你想减少CPU /内存的使用，那么你应该使用memoization（在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

注意，这不会降低算法复杂度或内存使用情况与天真的非尾递归实现相比。

来源

2015-02-11 23:11:18 deniss

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

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 [email protected](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，只有在有充分理由的情况下才能切换。

来源

2015-02-11 22:52:39 genisage

“浮动”不是'**'指数？ – Guvante 2015-02-11 23:01:53

是的，好的。 – genisage 2015-02-11 23:03:03

是的，注意到整数限制溢出非常快，但这是一个任务，因此我不能改变声明，并且必须使用Int，即使我们被告知运行alg（20）和50并比较，当它在12时死亡并且在返回零时数字越高，速度越慢。 – 2015-02-11 23:09:22

你看看哈斯克尔的斐波那契吗？它是一种类似的功能。 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这里，这是不开放结束，第十一届会议将在Int中循环。

编辑：其实Int比我想象的还要差。一旦你在结果中输入32 2，你将开始返回0，因为每个回答都是0 mod 2^32。

来源

2015-02-11 22:58:09 Guvante

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

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

来源

2015-02-11 23:22:11 rafalio

如何使用此解决方案，我正在艰难地围绕它进行包装 – 2015-02-12 22:00:15

回答

相关问题