0

我想将以下函数转换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)，因此此示例行不正确。

那可能吗？如果是这样，该功能应该如何？如果不是，为什么？

4

3 回答 3

2

不可能。你的尾声真的

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

因此它不是递归的。

------------ 编辑更新的问题 -----

一般来说，如果你有类似的东西

do
  a <- foo
  bar

你不能用它做一些尾递归。这是因为这被脱糖了

foo >>= (\a -> bar)

所以 (>>=) (或 (>>)) 是尾调用。

于 2013-09-27T13:14:03.840 回答
1

编辑

看看 Ingo 的答案，他是对的，您可能必须将生成器传递给函数，然后您可以使用纯函数来获取下一个随机数并将生成的 gen 传递给下一个递归函数调用。

结束编辑

您可以制作一个具有累加器的辅助函数，就像这样。我没有编译器，所以我不能保证它是完全正确的。

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-27T14:31:01.423 回答
1

如果您最终使用IO或其他 monad/monad 转换器，例如RandT（其他选项是传递生成器和/或预先生成的无限列表），这里是一个使用状态 monad 转换器来帮助线程化的示例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-27T17:14:08.763 回答