-5

我需要帮助。我有那种形式的功能

myFunction = case myFunction of
    (Nothing) -> (Just)
    (Just) -> (Just)

我想让它尾递归。一个人会怎么做？我知道根据递归调用的返回我们有不同的语句这一事实使它变得困难（我需要帮助的原因^^）。我可以提供原始功能，但我宁愿寻找更通用的解决方案。提前致谢

编辑：实际代码：

myFunction :: MyTree x -> (x, Maybe(MyTree x))
myFunction = (x, Nothing)
myFunction (MyNode left right) = case myFunction left of
                                      (x, Nothing)    -> (x, Just right)
                                      (x, Just left2) -> (x, Just (Node left2 right))
4

2 回答 2

1

我假设你定义了

data MyTree x = MyLeaf x | MyNode (MyTree x) (MyTree x)

并且意味着

myFunction :: MyTree x -> (x, Maybe(MyTree x))
myFunction (MyLeaf x) = (x, Nothing)
myFunction (MyNode left right) = case myFunction left of
                                      (x, Nothing)    -> (x, Just right)
                                      (x, Just left2) -> (x, Just (MyNode left2 right))

这是一个拉出最左边的叶子并将相应的右分支缝合到它所在位置的函数。

你问如何使这个尾递归。这是为什么？在某些（严格的）语言中，尾递归代码效率更高，但 Haskell 使用惰性求值，这意味着递归调用发生的时间有多晚并不重要，而是它们产生输出的时间有多早。在这种情况下，头部递归case myFunction left of会沿着树向下缩放，直到找到最左边的叶子，您无法更快地找到它。然而，在返回的路上，它确实x绕过了一点而不是立即返回，但它还在适当的地方缝合了所有正确的分支，没有任何簿记，这是在递归数据结构上使用递归的乐趣.

请参阅这个问题，了解为什么尾递归对于 Haskell 中的效率而言不是最重要的事情。

对节点处有数据的二叉树要做的三件事是： 1. 前序遍历（先访问当前节点，然后访问左子树，然后访问右子树）- 双尾递归 2. 中序遍历（访问左子树，然后是当前节点，然后是右） - 头尾递归 3. 后序遍历（访问当前节点之前的左右子树） - 双头递归。

对于不习惯懒惰评估的人来说，发布顺序听起来令人担忧，但它是一种对树中的值求和的有效方法，例如，特别是如果您确保编译器知道它是严格的。

与往常一样，最好的算法给出最快的结果，如果你想打开优化，你应该用 -O2 编译。

于 2012-11-22T02:42:32.003 回答
0

这些必须匹配。

myFunction = ...
myFunction (MyNode left right) = ...

他们不匹配。你不能一起使用它们。为什么？其中一个接受零参数，另一个接受一个参数。它们必须采用相同数量的参数。如果您需要忽略参数，请使用_. 请注意，使用_的版本必须在不使用的版本之后_。

myFunction :: MyTree x -> Maybe (MyTree x)
myFunction (MyNode left right) =
  case myFunction left of
    Nothing -> Just right
    Just left2 -> Just (MyNode left2 right)
myFunction _ = Nothing

我不知道x你的函数体应该是什么。它不受任何东西的约束。

这不是尾递归。并不是所有的函数都可以做成尾递归函数。

暗示

也许如果您描述了该功能应该做什么，我们可以帮助您做到这一点。

于 2012-11-21T23:28:28.297 回答