jjzjj

javascript - 如何在严格评估的语言中实现 protected 递归？

coder 2025-01-15 原文

我在 Javascript 中实现了一个 Scott 编码的 List 类型以及一个模仿 Semigroup 类型类的重载 append 函数。

append 工作得很好，但对于大型列表，它会破坏堆栈。这是我实现的决定性部分:

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));

通常我使用蹦床来避免不断增长的堆栈，但这以尾递归为前提，因此在这种情况下不起作用。

由于这个实现是基于 Haskell 的，我猜惰性求值和保护递归/尾递归模 cons 会有所不同:

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

假设我理解正确，由于惰性求值(几乎)，当我将一个列表附加到另一个列表时，Haskell 中什么也不会发生，直到我真正对这个新列表做一些事情。在下面的示例中，我将其折叠。

我不明白的是 protected 递归如何防止递归增加调用堆栈，以及这种行为是否可以在严格评估的语言(如 Javascript)中显式实现。

希望这个问题不要太宽泛。

为了更好地理解，这里是完整的实现/示例:

// type constructor

const Type = name => {
  const Type = tag => Dcons => {
    const t = new Tcons();

    Object.defineProperty(
      t,
      `run${name}`,
      {value: Dcons});

    t[TAG] = tag;
    return t;
  };

  const Tcons =
    Function(`return function ${name}() {}`) ();

  Tcons.prototype[Symbol.toStringTag] = name;
  return Type;
};


const TAG = Symbol("TAG");
const List = Type("List");


// data constructors

const Cons = x => tx => List("Cons") (cases => cases.Cons(x) (tx));
const Nil = List("Nil") (cases => cases.Nil);


// overload binary functions

const overload2 = (name, dispatch) => {
  const pairs = new Map();

  return {
    [`${name}Add`]: (k, v) => pairs.set(k, v),

    [`${name}Lookup`]: k => pairs.get(k),

    [name]: x => y => {
      if (typeof x === "function" && (VALUE in x))
        x = x(y);

      else if (typeof y === "function" && (VALUE in y))
        y = y(x);

      const r = pairs.get(dispatch(x, y));

      if (r === undefined)
        throw new TypeError("...");

      else if (typeof r === "function")
        return r(x) (y);

      else return r;
    }
  }
};


const dispatcher = (...args) => args.map(arg => {
  const tag = Object.prototype.toString.call(arg);
  return tag.slice(tag.lastIndexOf(" ") + 1, -1);
}).join("/");


// Semigroup "typeclass"

const {appendAdd, appendLookup, append} =
  overload2("append", dispatcher);


// List instance for Semigroup

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));


// fold

const foldr = f => acc => {
  const aux = tx =>
    tx.runList({
      Nil: acc,
      Cons: x => tx_ => f(x) (aux(tx_))})

  return aux;
};


// data

const tx = Cons(1) (Cons(2) (Nil));
const ty = Cons(3) (Cons(4) (Nil));
const tz = append(tx) (ty);


// run

console.log(
  foldr(x => acc => `${x}${acc}`) (0) (tz) // "12340"
);

最佳答案

这不是真正的答案，而是我在进一步研究后得出的结论:

  1. 尾递归模 Cons - TRMC(和其他操作的“模”)仅指严格评估的上下文，而 protected 递归指的是惰性评估的上下文
  2. TRMC 是一种昂贵的编译器技术，(可能)在用户空间中实现它没有意义
  3. TRMC 要求操作是结合的(至少形成一个半群)，以便括号可以重新排列

此问答也很有帮助:a tail-recursion version list appending function .

关于javascript - 如何在严格评估的语言中实现 protected 递归？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50288939/

言中何在constsection34javascripthaskellrecursionlazy-evaluationtail-recursion

有关javascript - 如何在严格评估的语言中实现 protected 递归？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  3. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  4. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  5. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  6. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  7. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  8. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  9. ruby-on-rails - 如何在 ruby​​ 交互式 shell 中有多行？ - 2

    这可能是个愚蠢的问题。但是，我是一个新手......你怎么能在交互式ruby​​shell中有多行代码？好像你只能有一条长线。按回车键运行代码。无论如何我可以在不运行代码的情况下跳到下一行吗？再次抱歉，如果这是一个愚蠢的问题。谢谢。 最佳答案 这是一个例子:2.1.2:053>a=1=>12.1.2:054>b=2=>22.1.2:055>a+b=>32.1.2:056>ifa>b#Thecode‘if..."startsthedefinitionoftheconditionalstatement.2.1.2:057?>puts"f

  10. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

随机推荐