标签: mutual-recursion

是否可以将相互递归类型([<Struct>])分布在不同的文件中？这些类型直接位于命名空间下.

我的解决方案是将它们放在一个大文件中并使用type ... and ... and ... etc构造.这是唯一的方法吗？

在OCaml中使用相互递归的模块定义时,即使在.ml文件中也必须提供签名.这是一个烦恼,我也希望从中公开给定的接口.mli,因为我最终重复签名两次.:(!

module rec Client : sig
  type ('serv,'cli) t

  (* functions ... *)
end = struct
  type ('serv,'cli) t =
    { server: ('serv,'cli) Server.t
    ; (* other members ... *)
    }
end
and Server : sig
  type ('serv,'cli) t

  (* functions ... *)
end = struct
  type ('serv,'cli) t =
    { mutable clients: ('serv,'cli) Client.t list
    ; mutable state: 'serv
    }

  (* functions again ... *)
end

这是我正在做的粗略近似(Client类型对象知道Server实例化它们Server.s知道它们的Clients). …

转到使用C/Java背景的python,我最近不得不实现相互递归,但python中的某些东西困扰着我:

因为python程序是逐行解释的,如果我在同一个python文件中一个接一个地有两个函数:

def A(n):
    B(n-1)
# if I add A(1) here, it gives me an error
def B(n):
    if n <= 0:
        return
    else:
        A(n-1)

当解释器正在读取时A,B尚未定义,但是此代码不会给我一个错误

TL; DR 我的理解是,当def被解释,蟒蛇增加了一些本地的名称空间中的条目locals()有{"function name": function address},但作为函数体,它只能做语法检查:

def A():
    blabla # this will give an error

def B():
    print x # even though x is not defined, this does not give an error
    A()     # same as above, NameError is only detected during runtime

这些语言不支持"原生"的相互递归函数优化,所以我猜它必须是蹦床或者......嘿......重写为循环)我想念一些东西吗？

更新:似乎我对FSharp撒了谎,但我只是没有看到谷歌搜索时相互尾调用的例子

如何在C++中实现相互递归的类？就像是:

/*
 * Recursion.h
 *
 */

#ifndef RECURSION_H_
#define RECURSION_H_

class Class1
{
  Class2* Class2_ptr;
public:
  void Class1_method()
  {
      //...
      (*Class2_ptr).Class2_method();
      //...
  }
};

class Class2
{
    Class1* Class1_ptr;
public:
    void Class2_method()
    {
        //...
        (*Class1_ptr).Class1_method();
        //...
    };
};


#endif /* RECURSION_H_ */

我正在试验Haskell中的外部函数接口.我想实现一个简单的测试,看看我是否可以进行相互递归.所以,我创建了以下Haskell代码:

module MutualRecursion where
import Data.Int

foreign import ccall countdownC::Int32->IO ()
foreign export ccall countdownHaskell::Int32->IO()

countdownHaskell::Int32->IO()
countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return ()

请注意,递归情况是对countdownC的调用,因此这应该是尾递归的.

在我的C代码中,我有

#include <stdio.h>

#include "MutualRecursionHaskell_stub.h"

void countdownC(int count)
{
    printf("%d\n", count);
    if(count > 0)
        return countdownHaskell(count-1);
}

int main(int argc, char* argv[])
{
    hs_init(&argc, &argv);

    countdownHaskell(10000);

    hs_exit();
    return 0;
}

这同样是尾递归.那我就做了

MutualRecursion: MutualRecursionHaskell_stub
    ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion
MutualRecursionHaskell_stub:
    ghc -O2 -c MutualRecursionHaskell.hs

并编译 …

我有一个程序,它产生一系列功能f,g如下所示:

step (f,g) = (newF f g, newG f g)

newF f g x = r (f x) (g x)
newG f g x = s (f x) (g x)

foo = iterate step (f0,g0)

其中R和S是一些无趣的功能f x和g x.我天真地希望,有foo是一个列表将意味着当我打电话的第n个f它不会重新计算(N-1)个f,如果它已经计算出它(如将如果发生f和g没有功能).有没有办法记住这一点而不会将整个程序拆开(例如评估f0和g0所有相关论点,然后向上工作)？

在某些编程语言中,尤其是在C语言中,存在具有函数声明的头文件.这些函数"标题"位于代码之前,并且在具有相互递归的情况下是必需的.当函数头放在头文件中时,它们还有助于链接多个C文件一起编译的情况.

我对C文件中函数头的理解是它们有助于编译,因为它们定义函数的类型,如果它在定义之前被调用.如果这是错误的,我会很高兴能够得到纠正和更好的信息,但这是我对它的理解.

所以我不明白,为什么其他语言 - 在这种情况下我单挑OCaml - 没有功能标题.在OCaml中,存在具有签名的模块,但是签名不允许您的函数实例化是相互递归的,即使给出了类型.为了在OCaml中进行相互递归,你需要使用"和"关键字,或者在另一个函数中本地定义一个函数(据我所知).

(* version 1 *)
let rec firstfun = function
  | 0 -> 1
  | x -> secondfun (x - 1)
and secondfun = function
  | 0 -> 1
  | x -> firstfun x

(* version 2 *)
let rec firstfun = function
  | 0 -> 1
  | x -> 
       let rec secondfun = function
         |0 -> 1
         | x -> firstfun x in
       secondfun (x - 1)

那么为什么会这样呢？它与多态性有关吗？有没有我不考虑的编译瓶颈？

如果我编写以下代码，JSLint 会抱怨在定义之前使用了'isOdd'。有没有办法编写相互递归的代码并且仍然取悦JSLint？

var isEven = function(n) {
    if (n === 0) {
        return true;
    }
    return isOdd(n - 1);
};

var isOdd = function(n) {
    if (n === 0) {
        return false;
    }
    return isEven(n - 1);
};

我遇到了一个相互递归的问题。我采用的基本结构是，我有一个定义类型类的模块和几个定义该类型类实例的模块。但是，根据所有其他实例来定义每个实例。

如果说的描述太抽象了，那么这里有一些代码的结构类似于我的代码。（我已对其进行了相当大的削减，以使必要的部分变得明显，并在与整体结构无关的部分上添加了一些椭圆形）。

我的课程如下所示：

data Result = ...

class Foo a where
  openFoo  :: Result      -> IO (a, Result)
  runFoo   :: (a, Result) -> IO (a, Result)
  closeFoo :: (a, Result) -> IO Result

然后我有实例

data XData = ...

instance Foo XData where
   openFoo result = ...
   runFoo (data, result) = do
     currentEvent <- getEvent
     case currentEvent of
       EventA -> return (data, result)
       EventB ->
         (openFoo result :: IO YData)
           >>= runFoo
             >>= closeFoo
               >>= curry return data
   closeFoo (data, result) …