单递函数中的尾递归

我想在尾递归函数中将以下函数转换为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

单递函数中的尾递归

回答

相关问题