1

我正在尝试在 JavaScript 中实现基本的惰性序列。我只使用闭包和延续。这是我到目前为止得到的：

var cons = curry(function(x, y, list){
  return list(x, y);
});
var head = function(seq){
  return seq(function(x, y){
    return x;
  });
};
var tail = function(seq){
  return seq(function(x, y){
    return y();
  });
};
var iterate = function(f){
  var next = f();
  if (next != null) {
    return cons(next, function(){
      return iterate(f);
    });
  }
};
var take = curry(function(n, seq){
  if (n && seq != null) {
    return cons(head(seq), function(){
      return take(n - 1, tail(seq));
    });
  }
});
var doSeq = curry(function(n, f, seq){
  while (n-- && seq != null) {
    f(head(seq));
    seq = tail(seq);
  }
});

var rand = iterate(Math.random);
var log = function(x){ console.log(x) };

doSeq(10, log, rand); //=> logs 10 random numbers

我没有发布咖喱功能，因为它与问题没有直接关系。

现在交易破坏者是filter. 规范的实现是尾递归的：

var filter = curry(function(f, seq){
  if (seq == null) {
    return;
  }
  if (!f(head(seq))) {
    return filter(f, tail(seq)); // recursion
  }
  return cons(head(seq), function(){
    return filter(f, tail(seq));
  });
});

当我在一个序列上多次运行它时，堆栈最终会爆炸：

伊姆古尔

我知道一个常见的解决方法是使用trampoline，这在一个热切的世界中相对容易，但对于一个惰性序列来说实现它似乎令人生畏。我在 Scheme 中找到了一个复杂的解决方案，但我放弃了尝试在 JavaScript 中按原样实现它。

这是否像看起来那么复杂？有没有另一种方法来解决这个问题，也许是迭代？关于以理智的方式将 Scheme 代码移植到 JavaScript 的任何提示？

4

1 回答 1

2

我认为这应该在仍然懒惰的同时做到这一点1：

var filter = curry(function(f, seq){
  while (seq != null && !f(head(seq)))
      seq = tail(seq);
  if (seq == null)
    return;
  return cons(head(seq), function() {
    return filter(f, tail(seq))
  });
});

也许更容易阅读：

var filter = curry(function(f, seq){
  for (; seq != null; seq = tail(seq))
    if ( f(head(seq)) )
      return cons(head(seq), function() {
        return filter(f, tail(seq))
      });
});

1）：您对惰性序列的表示似乎没有办法表达一个可能为空（但未确定）的列表

于 2014-03-05T16:53:41.383 回答