多通話功能

這裏哈斯克爾尾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

回答

相關問題