單遞函數中的尾遞歸

我想在尾遞歸函數中將以下函數轉換爲genEdges函數。單遞函數中的尾遞歸

genEdges :: Int -> Node -> IO [Edge] 
genEdges n origin | n == 0 = return [] 
        | otherwise = do 
         edge <- genRandEdge origin 
         edges <- genEdges (n-1) (snd edge) 
         return $ edge : edges

我的意思是，最後一行應該是這樣的

return $ edge : genEdges (n-1) (snd edge)

雖然我知道類型的edge和genEdges (n-1) (snd edge)是不同的，因此這個例子行不正確。

這可能嗎？如果是這樣，功能應該如何？如果不是，爲什麼？

來源

2013-09-27 Guiraldelli

無論如何，尾遞歸是Haskell中的一個紅鯡魚，因爲它的評估模型與傳統語言差別很大。 –

這是不可能的。您的尾巴電話確實是

(genRange origin) >>= (\edge -> .....)

因此它不是遞歸的。

-----------編輯更新的問題-----------------

一般來說，如果你有類似

do 
    a <- foo 
    bar

你不能做出一些尾遞歸的東西。這是因爲它被取消爲

foo >>= (\a -> bar)

因此（>> =）（或（>>））是尾部調用。

來源

2013-09-27 13:14:03 Ingo

所以問題變爲：是否可以做一個尾遞歸'邊緣：genEdges（n-1）（snd edge）'而不使用'return'？由於我使用隨機數字（'System），因爲我想要一個'[Edge]'，而不是'IO [Edge]'，但是我的'Edge's被「困在」IO單元內。隨機'功能，如'getStdRandom'和'randomR'）。 – Guiraldelli

你不應該被困在IO單子中，有更好的方法。 – nponeccop

一個小問題;這不是不可能的。「解決方案」通常不被建議，並且確實有更好的方法，但它確實存在。 –

編輯

縱觀英戈的回答，他是對的，你可能有發電機傳遞到功能，那麼你可以使用純函數來獲取下一個隨機數並通過根，它產生下一個遞歸函數調用。

編輯完

你可以有一個累加器所以像這樣的輔助函數。我沒有編譯器，所以我不能保證它是完全正確的。

genEdges :: Int -> Node -> IO [Edge] 
genEdges n o = genEdgesTR n o [] 
    where genEdgesRec n origin acc 
      | n == 0 = return acc 
      | otherwise = do 
      edge <- get RandEdge orgin 
      genEdgesRec (n-1) (snd edge) (edge : acc)

這也許可以用foldM或東西，但最多也就是你找出寫的。

來源

2013-09-27 14:31:01 DiegoNolan

您還需要在最後反轉結果列表。 –

如果你最終使用IO或其他單子/單子轉換，如RandT（其他選項傳遞發電機和/或周圍預先生成無限列表），這裏是一個使用狀態單子轉換，以幫助的origin線程的例子：

import Control.Monad.State 

data Node = Node 
type Edge = ((), Node) 

genRandEdge :: Node -> IO Edge 
genRandEdge = undefined 

genEdges :: Int -> Node -> IO [Edge] 
genEdges n = evalStateT $ replicateM n $ do 
     origin <- get 
     edge <- liftIO $ genRandEdge origin 
     put $ snd edge 
     return edge

爲了幫助您更好的genRandEdge避免IO我們需要更多的上下文，以便隨時問你的生成方法如何才能改善另一個問題。

來源

2013-09-27 17:14:08 nponeccop

單遞函數中的尾遞歸

回答

相關問題