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));
  });
});

シーケンスで何度も実行すると、スタックは最終的に爆発します:

イムグル

一般的な回避策はトランポリンを使用することであり、熱心な世界では比較的簡単ですが、怠惰なシーケンスに実装するのは困難なようです。Schemeで複雑な解決策を見つけましたが、そのまま JavaScript で実装することをあきらめました。

これは見た目ほど複雑ですか？おそらく反復で、この問題を解決する別の方法はありますか？健全な方法でスキーム コードを 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 に答える