Class: Immutable::Stream

Inherits:
Promise show all
Includes:
Consable
Defined in:
lib/immutable/stream.rb

Overview

Immutable::Stream represents a stream, also known as a lazy list. A stream is similar to a list. However the evaluation of a stream element is delayed until its value is needed

Examples:

Natural numbers

def from(n)
  Stream.cons ->{n}, ->{from(n + 1)}
end

nats = from(0)
p from(0).take(10).to_list #=> List[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Prime numbers

primes = Stream.from(2).filter { |n|
  (2 ... n / 2 + 1).all? { |x|
    n % x != 0
  }
}
p primes.take_while { |n| n < 10 }.to_list #=> List[2, 3, 5, 7]

Defined Under Namespace

Classes: Pair

Constant Summary collapse

NULL = 
Object.new

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Consable

#flat_map, included, #prepend, #rev_map, #subsequences, #transpose, #unshift

Methods included from Headable

#==, #[], #each, #each_index, #eql?, #fetch, #find, #first, #foldl, #foldl1, #foldr, #foldr1, #hash, #index, #null?, #rindex, #shift, #to_list

Methods included from Foldable

#foldl, #length, #product, #sum

Methods inherited from Promise

delay, eager, #eager?, #force, #initialize, lazy, #lazy?

Constructor Details

This class inherits a constructor from Immutable::Promise

Class Method Details

.[](*elements) ⇒ Stream

Creates a new stream. Note that the arguments are evaluated eagerly.

Parameters:

  • elements (Array<Object>) —

    the elements of the stream.

Returns:

  • (Stream) —

    the new stream.



96
97
98
 
# File 'lib/immutable/stream.rb', line 96

def self.[](*elements)
  from_enum(elements)
end

.cons(head, tail) ⇒ Stream

Creates a new stream.

Examples:

A Stream which has 123 as the only element.

s = Stream.cons(->{123}, ->{Stream.empty})
p s.to_list #=> List[123]

A Stream which has two elements: “abc” and “def”.

s = Stream.cons(->{"abc"},
      ->{Stream.cons(->{"def"}, ->{Stream.empty})})
p s.to_list #=> List["abc", "def"]

Parameters:

  • head (Proc) —

    a Proc whose value is the head of self.

  • tail (Proc) —

    a Proc whose value is the tail of self.

Returns:

  • (Stream) —

    the new stream.



69
70
71
 
# File 'lib/immutable/stream.rb', line 69

def self.cons(head, tail)
  Stream.eager(Pair.new(Stream.delay(&head), Stream.lazy(&tail)))
end

.empty ⇒ Stream

Returns an empty stream.

Returns:

  • (Stream) —

    an empty stream.



52
53
54
 
# File 'lib/immutable/stream.rb', line 52

def self.empty
  delay { NULL }
end

.from(first, step = 1) ⇒ Stream

Creates an infinite stream which starts from first and increments each succeeding element by step.

Parameters:

  • first (#+) —

    the first element.

  • step (#+) (defaults to: 1) —

    the step for succeeding elements.

Returns:

  • (Stream) —

    the new stream.



131
132
133
 
# File 'lib/immutable/stream.rb', line 131

def self.from(first, step = 1)
  cons ->{ first }, ->{ from(first + step, step) }
end

.from_enum(e) ⇒ Stream

Creates a new stream from an Enumerable object.

Parameters:

  • e (Enumerable) —

    an Enumerable object.

Returns:

  • (Stream) —

    the new stream.



104
105
106
 
# File 'lib/immutable/stream.rb', line 104

def self.from_enum(e)
  from_enumerator(e.each)
end

.from_enumerator(e) ⇒ Stream

Creates a new stream from an Enumerator object. Note that from_enumerator has side effects because it calls Enumerator#next.

Parameters:

  • e (Enumerator) —

    an Enumerator object.

Returns:

  • (Stream) —

    the new stream.



114
115
116
117
118
119
120
121
122
123
 
# File 'lib/immutable/stream.rb', line 114

def self.from_enumerator(e)
  lazy {
    begin
      x = e.next
      cons ->{ x }, ->{ from_enumerator(e) }
    rescue StopIteration
      empty
    end
  }
end

.unfoldr(e, &block) ⇒ Stream

Builds a stream from the seed value e and the given block. The block takes a seed value and returns nil if the seed should unfold to the empty stream, or returns [a, b], where a is the head of the stream and b is the next seed from which to unfold the tail. For example:

xs = List.unfoldr(3) { |x| x == 0 ? nil : [x, x - 1] }
p xs #=> List[3, 2, 1]

unfoldr is the dual of foldr.

Parameters:

  • e (Object) —

    the seed value.

Returns:

  • (Stream) —

    the stream built from the seed value and the block.



404
405
406
407
408
409
410
411
412
413
414
 
# File 'lib/immutable/stream.rb', line 404

def self.unfoldr(e, &block)
  Stream.lazy {
    x = yield(e)
    if x.nil?
      Stream.empty
    else
      y, z = x
      Stream.cons ->{ y }, ->{ unfoldr(z, &block) }
    end
  }
end

Instance Method Details

#+(s) ⇒ Stream

Appends two streams self and s.

Parameters:

  • s (Stream) —

    the stream to append.

Returns:

  • (Stream) —

    the new stream.



224
225
226
227
228
229
230
231
232
 
# File 'lib/immutable/stream.rb', line 224

def +(s)
  Stream.lazy {
    if empty?
      s
    else
      Stream.cons ->{head}, ->{tail + s}
    end
  }
end

#cons(x = nil, &block) ⇒ Stream

Creates a new stream whose head is the value of x or block and whose tail is self.

Examples:

A Stream which has 123 as the only element.

s = Stream.empty.cons(123)
p s.to_list #=> List[123]

A Stream which has two elements: “abc” and “def”.

s = Stream.empty.cons {"def"}.cons {"abc"}
p s.to_list #=> List["abc", "def"]

Returns:

  • (Stream) —

    the new stream.



84
85
86
87
88
89
90
 
# File 'lib/immutable/stream.rb', line 84

def cons(x = nil, &block)
  if block
    Stream.eager(Pair.new(Stream.delay(&block), self))
  else
    Stream.eager(Pair.new(Stream.eager(x), self))
  end
end

#drop(n) ⇒ Stream

Returns the suffix of self after the first n elements, or Stream[] if n > self.length.

Parameters:

  • n (Integer) —

    the number of elements to drop.

Returns:

  • (Stream) —

    the suffix of self after the first n elements.



335
336
337
338
339
340
341
342
343
 
# File 'lib/immutable/stream.rb', line 335

def drop(n)
  Stream.lazy {
    if n <= 0 || empty?
      self
    else
      tail.drop(n - 1)
    end
  }
end

#drop_while(&block) ⇒ Stream

Returns the suffix remaining after self.take_while(&block).

Returns:

  • (Stream) —

    the suffix of the elements of self.



363
364
365
366
367
368
369
370
371
 
# File 'lib/immutable/stream.rb', line 363

def drop_while(&block)
  Stream.lazy {
    if empty? || !yield(head)
      self
    else
      tail.drop_while(&block)
    end
  }
end

#empty? ⇒ true, false

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



138
139
140
 
# File 'lib/immutable/stream.rb', line 138

def empty?
  force == NULL
end

#filter(&block) ⇒ Stream

Returns the elements in self for which the given block evaluates to true.

Returns:

  • (Stream) —

    the elements that satisfies the condition.



377
378
379
380
381
382
383
384
385
386
387
388
389
 
# File 'lib/immutable/stream.rb', line 377

def filter(&block)
  Stream.lazy {
    if empty?
      Stream.empty
    else
      if yield(head)
        Stream.cons ->{ head }, ->{ tail.filter(&block) }
      else
        tail.filter(&block)
      end
    end
  }
end

#flatten ⇒ Stream Also known as: concat

Concatenates a stream of streams.

Returns:

  • (Stream) —

    the concatenated stream.



297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
 
# File 'lib/immutable/stream.rb', line 297

def flatten
  Stream.lazy {
    if empty?
      self
    else
      if head.empty?
        tail.flatten
      else
        Stream.cons ->{head.head}, ->{
          Stream.cons(->{head.tail}, ->{tail}).flatten
        }
      end
    end
  }
end

#head ⇒ Object

Returns the first element of self. If self is empty, Immutable::EmptyError is raised.

Returns:

  • (Object) —

    the first element of self.



146
147
148
 
# File 'lib/immutable/stream.rb', line 146

def head
  force.head.force
end

#init ⇒ Stream

Returns all the elements of self except the last one. If self is empty, Immutable::EmptyError is raised.

Returns:

  • (Stream) —

    the elements of self except the last one.



175
176
177
178
179
180
181
182
183
184
185
186
187
 
# File 'lib/immutable/stream.rb', line 175

def init
  Stream.lazy {
    if empty?
      raise EmptyError
    else
      if tail.empty?
        Stream.empty
      else
        Stream.cons(->{head}, ->{tail.init})
      end
    end
  }
end

#inspect ⇒ String Also known as: to_s

Creates a string representation of self.

Returns:

  • (String) —

    a stream representation of self.



192
193
194
 
# File 'lib/immutable/stream.rb', line 192

def inspect
  "Stream[" + inspect_i + "]"
end

#intercalate(xs) ⇒ Stream

Returns a new stream obtained by inserting xs in between the streams in self and concatenates the result. xss.intercalate(xs) is equivalent to xss.intersperse(xs).flatten.

Parameters:

  • xs (Stream) —

    the stream to insert between streams.

Returns:

  • (Stream) —

    the new stream.



290
291
292
 
# File 'lib/immutable/stream.rb', line 290

def intercalate(xs)
  intersperse(xs).flatten
end

#intersperse(sep) ⇒ Stream

Returns a new stream obtained by inserting sep in between the elements of self.

Parameters:

  • sep (Object) —

    the object to insert between elements.

Returns:

  • (Stream) —

    the new stream.



260
261
262
263
264
265
266
267
268
 
# File 'lib/immutable/stream.rb', line 260

def intersperse(sep)
  Stream.lazy {
    if empty?
      self
    else
      Stream.cons(->{head}, ->{tail.prepend_to_all(sep)})
    end
  }
end

#last ⇒ Object

Returns the last element of self. If self is empty, Immutable::EmptyError is raised.

Returns:

  • (Object) —

    the last element of self.



154
155
156
157
158
159
160
 
# File 'lib/immutable/stream.rb', line 154

def last
  if tail.empty?
    head
  else
    tail.last
  end
end

#map(&block) ⇒ Stream

Returns the stream obtained by applying the given block to each element in self.

Returns:

  • (Stream) —

    the obtained stream.



238
239
240
241
242
243
244
245
246
 
# File 'lib/immutable/stream.rb', line 238

def map(&block)
  Stream.lazy {
    if empty?
      Stream.empty
    else
      Stream.cons ->{ yield(head) }, ->{ tail.map(&block) }
    end
  }
end

#reverse ⇒ Stream

Returns the elements of self in reverse order.

Returns:

  • (Stream) —

    the reversed stream.



251
252
253
 
# File 'lib/immutable/stream.rb', line 251

def reverse
  foldl(Stream.empty) { |x, y| Stream.cons(->{y}, ->{x}) }
end

#tail ⇒ Stream

Returns the stream stored in the tail of self. If self is empty, Immutable::EmptyError is raised.

Returns:

  • (Stream) —

    the stream stored in the tail of self.



166
167
168
 
# File 'lib/immutable/stream.rb', line 166

def tail
  force.tail
end

#take(n) ⇒ Stream

Returns the first n elements of self, or self itself if n > self.length.

Parameters:

  • n (Integer) —

    the number of elements to take.

Returns:

  • (Stream) —

    the first n elements of self.



320
321
322
323
324
325
326
327
328
 
# File 'lib/immutable/stream.rb', line 320

def take(n)
  Stream.lazy {
    if n <= 0 || empty?
      Stream.empty
    else
      Stream.cons ->{ head }, ->{ tail.take(n - 1) }
    end
  }
end

#take_while(&block) ⇒ Stream

Returns the longest prefix of the elements of self for which block evaluates to true.

Returns:

  • (Stream) —

    the prefix of the elements of self.



349
350
351
352
353
354
355
356
357
 
# File 'lib/immutable/stream.rb', line 349

def take_while(&block)
  Stream.lazy {
    if empty? || !yield(head)
      Stream.empty
    else
      Stream.cons ->{ head }, ->{ tail.take_while(&block) }
    end
  }
end

#zip(*xss) ⇒ Stream

Takes zero or more streams and returns a new stream in which each element is an array of the corresponding elements of self and the input streams.

Parameters:

  • xss (Array<Stream>) —

    the input streams.

Returns:

  • (Stream) —

    the new stream.



422
423
424
425
426
427
428
429
430
431
432
 
# File 'lib/immutable/stream.rb', line 422

def zip(*xss)
  Stream.lazy {
    if empty?
      self
    else
      heads = xss.map { |xs| xs.empty? ? nil : xs.head }
      tails = xss.map { |xs| xs.empty? ? Stream.empty : xs.tail }
      Stream.cons ->{ [head, *heads] }, ->{ tail.zip(*tails) }
    end
  }
end

#zip_with(*xss, &block) ⇒ Stream

Takes zero or more streams and returns the stream obtained by applying the given block to an array of the corresponding elements of self and the input streams. xs.zip_with(*yss, &block) is equivalent to xs.zip(*yss).map(&block).

Parameters:

  • xss (Array<Stream>) —

    the input streams.

Returns:

  • (Stream) —

    the new stream.



442
443
444
445
446
447
448
449
450
451
452
453
 
# File 'lib/immutable/stream.rb', line 442

def zip_with(*xss, &block)
  Stream.lazy {
    if empty?
      self
    else
      heads = xss.map { |xs| xs.empty? ? nil : xs.head }
      tails = xss.map { |xs| xs.empty? ? Stream.empty : xs.tail }
      h = yield(head, *heads)
      Stream.cons ->{ h }, ->{ tail.zip_with(*tails, &block) }
    end
  }
end