Feature #6758

Object#sequence

Added by kyo endo over 1 year ago. Updated over 1 year ago.

[ruby-core:46562]
Status:Open
Priority:Normal
Assignee:-
Category:core
Target version:next minor

Description

=begin

== Object#sequence

Let me propose a new method ((Object#sequence)).

次のような実装の((Object#sequence))を提案します。

class Object
  def sequence(init=true, &blk)
    x = self
    Enumerator.new do |y|
      y << x if init
      loop { y << (x = yield x) }
    end
  end
end

((sequence)) generate a sequence by applying a block recursively to the receiver object. The result is wrapped with a Enumerator object, thus it is set under lazy evaluation.

((sequence))は、そのレシーバオブジェクトを初期値として、渡されたブロック(漸化式)を繰り返し適用してシーケンスを生成します。適用の結果はEnumeratorオブジェクトでラップされているので、遅延評価されます。

== Usage;

使い方を示します。

1.sequence { |x| x + 2 }.take(10) # => [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

3.sequence { |x| x * 2 }.take(10) # => [3, 6, 12, 24, 48, 96, 192, 384, 768, 1536]

[0, 1].sequence { |a, b| [b, a + b] }.take(10).map(&:first) # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

[0, 1, 1].sequence { |a, b, c| [b, c, a + b + c] }.take(10).map(&:first) # => [0, 1, 1, 2, 4, 7, 13, 24, 44, 81]

# square root 5
a = 5
eps = 0.0001
1.0.sequence { |x| (x + a/x) / 2.0 }
   .each_cons(2)
   .detect { |a, b| (a - b).abs < eps }[1] # => 2.236067977499978

# Excel label
'A'.sequence { |x| x.succ }.take(30) # => ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "AA", "AB", "AC", "AD"]

# random boolean(avoid true-true sequence)
true.sequence { |prev| prev ? false : [true, false].sample }.take(20) # => [true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false, false, false, true, false]

== Some background

== 提案の経緯

Let me explain some background of this request.

本件に関しては、ここに至る若干の経緯がありますので、併せて説明します。

  1. I introduced this method as ((Object#repeat)) on my Japanese blog.

  2. 私のブログにおいて、本メソッドを((Object#repeat))として紹介する記事を公開。

((URL:http://melborne.github.com/2012/07/12/object-repeat-take-care-of-sequence/))

  1. Matz tweeted to the article.

    "um.. the feature is attractive, but the name is.."

  2. 記事に対してMatzがつぶやく。

    「うーん、昨日としては魅力的だけど、名前がなあ。」

((URL:https://twitter.com/yukihiro_matz/status/223790181113806848))

  1. I updated the article to propose ((Object#repeat_apply)) or ((Object#repeat_call)).

  2. Object#repeatapply, Object#repeatcallを提案するべく記事を更新。

  3. Matz tweeted to the article.

    @merborne more clear. but combining two verbs is wrong. I understand naming is difficult.

  4. 記事に対してMatzがつぶやく。

    @merborne なるほど「repeatapply」か「repeatcall」ですか。repeat単体よりは誤解を受けにくいとは思いますが、repeatって動詞とapply/callって動詞の組み合わせは感心しませんね。名前って難しい。

((URL:https://twitter.com/yukihiro_matz/status/224105896110866432))

  1. Matz tweeted to the article.

    @merborne I suggest some clue lies around a word "series"..

  2. 記事に対してMatzがつぶやく。

    @merborne 「級数/series」あたりに名前のヒントがありそうな。

((URL:https://twitter.com/yukihiro_matz/status/224106160591081472))

  1. I tweeted to Matz.

  2. 私もつぶやく

    @yukihiro_matz you are right.. repeated_apply repeated_call?..

    @yukihiromatz たしかに.. repeatedapply repeated_callかな..

((URL:https://twitter.com/merborne/status/224108387653259264))

> @yukihiro_matz clue! `series_by` ? 


> @yukihiro_matz ヒント! series_by ? 

((URL:https://twitter.com/merborne/status/224108809948377088))

> @yukihiro_matz `repeated` is adjective..^^; but I don't like `repeatedly_apply`. I thought once `series_by` is good, but it would be better a method is named based on its behavior, not on its function, I think. How about `repeat_by`?


> @yukihiro_matz repeatedは形容詞でしたね^^; するとrepeatedly_applyですが、今ひとつです。series_byもいいと思ったんですが、できれば機能ではなく動作を言いたい思いがあります。そこでrepeat_byというのはどうでしょうか。

((URL:https://twitter.com/merborne/status/224324670764220416))

the conversation closed..

会話終了..

  1. Ideas from other Rubyists

Some Japanese Rubyists tweeted or commented me on the name. Candidates are..

  1. 他のRubyistの意見

名前に関し何人かのRubyistからアイディアをもらっています。リストアップします。

iterate
recur
recurrence
recur_with
unfold
sequence
seq

Haskell and Scala have the same functionality with a name of ((iterate)).

なお、HaskellとScalaには同種の機能が、((iterate))という名前で実装されているそうです。

Also, @makotokuwata-san tweeted that ((Kernel#seq))(function style) or ((Enumerator.seq()))(a Class method) is better.

また、@makotokuwata氏よりKernel#seqのような関数形式か、Enumerator.seq()のようなクラスメソッドのほうがいいとの意見も頂いています。

> @yukihiro_matz @merborne 初期値と漸化式から順列を作る機能なので、"sequence"か"seq"に1票。あとKernel#seq(initial,&blk)のほうが好きです。RT 「級数/series」あたりに名前のヒントがありそうな。 

((URL:https://twitter.com/makotokuwata/status/225806204390227968))

Thank you for your consideration.

以上、ご検討のほどよろしくお願い致します。

=end

History

#1 Updated by Thomas Sawyer over 1 year ago

Nice, but why Object method and not Kernel method?

#2 Updated by kyo endo over 1 year ago

trans (Thomas Sawyer) wrote:

Nice, but why Object method and not Kernel method?

Thank you.

If you mean Kernel public method, no difference.

If you mean Kernel private method that is, function style, I prefer having a receiver. Two reason. Passing block argument from a receiver object is more natural for me than from argument of the method. Also I prefer placing this method into method chain.

#3 Updated by Kenta Murata over 1 year ago

I prefer Enumerable.seq and Kernel#seq.

#4 Updated by Naohisa Goto over 1 year ago

In biology, the term "sequence" has special meanings for DNA and protein, and I'm already using the method name "sequence" and its abbreviation "seq" in my libraries and tools (e.g. bioruby). So, I have objection to the name Object#sequence and #seq.

According to WikiPedia, "sequence" has several field-specific meanings other than biology.
http://en.wikipedia.org/wiki/Sequence_%28disambiguation%29

I prefer "iterate" or "recurrence".

#5 Updated by Alexey Muranov over 1 year ago

ngoto (Naohisa Goto) wrote:

In biology, the term "sequence" has special meanings for DNA and protein, and I'm already using the method name "sequence" and its abbreviation "seq" in my libraries and tools (e.g. bioruby). So, I have objection to the name Object#sequence and #seq.

According to WikiPedia, "sequence" has several field-specific meanings other than biology.
http://en.wikipedia.org/wiki/Sequence_%28disambiguation%29

I prefer "iterate" or "recurrence".

I think that the use of "sequence" in biology and all other sciences are special cases of the mathematical meaning (the one at the top of the wikipedia page). So i object to this particular objection. "Recurrence" is a more special term than a sequence. In particular, if the generated sequence is random, it is hard to call it a "recurrence". See also http://en.wikipedia.org/wiki/Recurrence_relation .

#6 Updated by Thomas Sawyer over 1 year ago

@ngoto You can still use #sequence for your specialized classes, and if you need to use Object#sequence simply alias it.

class DNA
alias :iterate, :sequence

def sequence
  # your code
end

end

However, mathematically speaking, I think the technical name for this is series. So maybe that would be a better choice?

#7 Updated by Alexey Muranov over 1 year ago

trans (Thomas Sawyer) wrote:

However, mathematically speaking, I think the technical name for this is series. So maybe that would be a better choice?

I believe that in mathematical English "series" means an infinite sum, like 1 + 2 + 3 + 4 + ...
For example: Fourier series.

#8 Updated by Thomas Sawyer over 1 year ago

I believe that in mathematical English "series" means an infinite sum, like 1 + 2 + 3 + 4 + ...
For example: Fourier series.

Oh, yeah. That's right.

#9 Updated by Alexey Muranov over 1 year ago

=begin
ngoto (Naohisa Goto) wrote:

I prefer "iterate" or "recurrence".

Excuse me, Naohisa Goto, after some thought i agree that (({#iterate})) or (({#recurrence})) are good ideas, as the sequence generated in this way is more or less a recurrent sequence ( http://en.wikipedia.org/wiki/Recurrence_relation ).

I would propose a different behavior however, with an arbitrary number of initializing values:

class Object
def recurrence(args)
Enumerator.new do |y|
v = [self] + args
v.each { |x| y << x }
loop { y << (x = yield(
v)); v.shift; v << x }
end
end
end

fibonacci = 0.recurrence(1) { |a, b| a + b }

fibonacci.take(10) # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

What do you think? The result looks nice to me, but my implementation looks weird.
=end

#10 Updated by kyo endo over 1 year ago

alexeymuranov (Alexey Muranov) wrote:

fibonacci = 0.recurrence(1) { |a, b| a + b }

I disagree this. because I can't image fibonacci sequence from this code. and two block variables, which are both used as init data comes from different sources(one from a receiver, one from an argument). It's not natural for me.

with the original, you can easily get a sequence, of which a sequence of diffrences becomes a sequence of numbers with common difference as follows;

[1, 1].sequence { |a, b| [a+2, a+b] }.take(20).map(&:last) # => [1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 325, 362]

# a sequence of diffrences of above sequence becomes [1, 3, 5, 7, 9 ..]

#11 Updated by Thomas Sawyer over 1 year ago

Please don't name the method #recurrence. #sequence was long enough, and thankfully nice obvious shorthand, if we want to use it, with #seq. While #iterate is ok too, but if we are going to talk about it as a "sequence", which everyone seems to be doing, it might as well be named that.

#12 Updated by Alexey Muranov over 1 year ago

merborne (kyo endo) wrote:

alexeymuranov (Alexey Muranov) wrote:

fibonacci = 0.recurrence(1) { |a, b| a + b }

I disagree this. because I can't image fibonacci sequence from this code. and two block variables, which are both used as init data comes from different sources(one from a receiver, one from an argument). It's not natural for me.

with the original, you can easily get a sequence, of which a sequence of diffrences becomes a sequence of numbers with common difference as follows;

[1, 1].sequence { |a, b| [a+2, a+b] }.take(20).map(&:last) # => [1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 325, 362]

# a sequence of diffrences of above sequence becomes [1, 3, 5, 7, 9 ..]

Ok, i agree, my proposed behavior was not intuitive and not completely general.

However, the original proposal looks to me rather restrictive and not very efficient. Between

[0, 1].sequence { |a, b| [b, a + b] }.take(10).map(&:first)

and

Enumerator.new { |y| a, b = 0, 1; loop { y << a; a, b = b, a + b } }.take(10)

i think i would choose the second, even though it is longer.

#13 Updated by kyo endo over 1 year ago

alexeymuranov (Alexey Muranov) wrote:

However, the original proposal looks to me rather restrictive and not very efficient. Between

[0, 1].sequence { |a, b| [b, a + b] }.take(10).map(&:first)

and

Enumerator.new { |y| a, b = 0, 1; loop { y << a; a, b = b, a + b } }.take(10)

i think i would choose the second, even though it is longer.

how about this?

b = 1
0.sequence { |a| a, b = b, a + b; a}.take(10)

#14 Updated by Alexey Muranov over 1 year ago

merborne (kyo endo) wrote:

how about this?

b = 1
0.sequence { |a| a, b = b, a + b; a}.take(10)

Well, in my opinion this is not too different from

a, b, s = 0, 1, []
10.times { s << a; a, b = b, a + b }
s

because it requires an external local variable.

#15 Updated by kyo endo over 1 year ago

alexeymuranov (Alexey Muranov) wrote:

merborne (kyo endo) wrote:

how about this?

b = 1
0.sequence { |a| a, b = b, a + b; a}.take(10)

Well, in my opinion this is not too different from

a, b, s = 0, 1, []
10.times { s << a; a, b = b, a + b }
s

because it requires an external local variable.

#sequence returns an enumerator object. It means it can be evaluated later.

class Enumerator
  def lazy(&blk)
    Enumerator.new do |y|
      each { |e| yield(y, e) }
    end
  end
end

# even fibonacci sequence
b = 1
0.sequence { |a| a, b = b, a + b; a }
 .lazy { |y, fib| y << fib if fib.even? }.take(10) # => [0, 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418]

Enumerator#lazy will be introduced in Ruby 2.0.

When #sequence is called from an array object, it is natural for me to get an arrays, each of which is same size of receivers, as its returning sequence.

[0, 1].sequence { |a, b| [b, a + b] }.take(10) # => [[0, 1], [1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 13], [13, 21], [21, 34], [34, 55]]

# create two different sequences at once.
[1, 1].sequence { |a, b| [a+2, b*2] }.take(10) # => [[1, 1], [3, 2], [5, 4], [7, 8], [9, 16], [11, 32], [13, 64], [15, 128], [17, 256], [19, 512]]

so, the first fib example is acceptable for me :)

#16 Updated by Yutaka HARA over 1 year ago

  • Category set to core
  • Target version set to next minor

#17 Updated by Boris Stitnicky over 1 year ago

The method seems useful, but adding it to Object or Kernel would be feature creep. I still remember how I was memorizing basic Ruby classes. The number of features in them is already such, that adding new features raises the bar for novices more than linearly.

I suggest to make this a public class method of Enumerator, which it constructs. As for the name, I do not think that "sequence" is optimal. Better name would be "produce", similar sounding but not same as "reduce". Like this:

Enumerator.produce( 1 ) { |a| a + 2 }

I would definitely leave it up to the user alone to add the shortcut method to Object class, if ze wants.

Also available in: Atom PDF