Class: Immutable::Stream

Inherits:
Promise show all
Includes:
Enumerable, Foldable
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 Foldable

#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.



94
95
96
 
# File 'lib/immutable/stream.rb', line 94

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.null})
p s.to_list #=> List[123]

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

s = Stream.cons(->{"abc"},
      ->{Stream.cons(->{"def"}, ->{Stream.null})})
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.



71
72
73
 
# File 'lib/immutable/stream.rb', line 71

def self.cons(head, tail)
  Stream.eager(Pair.new(Stream.delay(&head), Stream.lazy(&tail)))
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.



129
130
131
 
# File 'lib/immutable/stream.rb', line 129

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.



102
103
104
 
# File 'lib/immutable/stream.rb', line 102

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.



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

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

.null ⇒ Stream

Returns an empty stream.

Returns:

  • (Stream) —

    an empty stream.



54
55
56
 
# File 'lib/immutable/stream.rb', line 54

def self.null
  delay { NULL }
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.



513
514
515
516
517
518
519
520
521
522
523
 
# File 'lib/immutable/stream.rb', line 513

def self.unfoldr(e, &block)
  Stream.lazy {
    x = yield(e)
    if x.nil?
      Stream.null
    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.



297
298
299
300
301
302
303
304
305
 
# File 'lib/immutable/stream.rb', line 297

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

#==(s) ⇒ true, false

Returns whether self equals to s.

false.

Parameters:

  • s (Stream) —

    the stream to compare.

Returns:

  • (true, false) —

    true if self equals to s; otherwise,



281
282
283
284
285
286
287
288
289
290
291
 
# File 'lib/immutable/stream.rb', line 281

def ==(s)
  if !s.is_a?(Stream)
    false
  else
    if null?
      s.null?
    else
      !s.null? && head == s.head && tail == s.tail
    end
  end
end

#[](n) ⇒ Object

Returns the nth element of self. If n is out of range, nil is returned.

Returns:

  • (Object) —

    the nth element.



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

def [](n)
  if n < 0 || null?
    nil
  elsif n == 0
    head
  else
    tail[n - 1]
  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.



455
456
457
458
459
460
461
462
463
 
# File 'lib/immutable/stream.rb', line 455

def drop(n)
  Stream.lazy {
    if n <= 0 || null?
      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.



483
484
485
486
487
488
489
490
491
 
# File 'lib/immutable/stream.rb', line 483

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

#each(&block) ⇒ Object

Calls block once for each element in self.



219
220
221
222
223
224
 
# File 'lib/immutable/stream.rb', line 219

def each(&block)
  unless null?
    yield(head)
    tail.each(&block)
  end
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.



407
408
409
410
411
412
413
414
415
416
417
418
419
 
# File 'lib/immutable/stream.rb', line 407

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

#find(&block) ⇒ Object

Returns the first element in self for which the given block evaluates to true. If such an element is not found, it returns nil.

Returns:

  • (Object) —

    the found element.



391
392
393
394
395
396
397
398
399
400
401
 
# File 'lib/immutable/stream.rb', line 391

def find(&block)
  if null?
    nil
  else
    if yield(head)
      head
    else
      tail.find(&block)
    end
  end
end

#flatten ⇒ Stream

Concatenates a stream of streams.

Returns:

  • (Stream) —

    the concatenated stream.



310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
 
# File 'lib/immutable/stream.rb', line 310

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

#foldl(e, &block) ⇒ Object

Reduces self using block from left to right. e is used as the starting value. For example:

Stream[1, 2, 3].foldl(9) { |x, y| x + y } #=> ((9 - 1) - 2) - 3 = 3

Parameters:

  • e (Object) —

    the start value.

Returns:

  • (Object) —

    the reduced value.



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

def foldl(e, &block)
  if null?
    e
  else
    tail.foldl(yield(e, head), &block)
  end
end

#foldl1(&block) ⇒ Object

Reduces self using block from left to right. If self is empty, Immutable::List::EmptyError is raised.

Returns:

  • (Object) —

    the reduced value.



272
273
274
 
# File 'lib/immutable/stream.rb', line 272

def foldl1(&block)
  tail.foldl(head, &block)
end

#foldr(e, &block) ⇒ Object

Reduces self using block from right to left. e is used as the starting value. For example:

Stream[1, 2, 3].foldr(9) { |x, y| x + y } #=> 1 - (2 - (3 - 9)) = -7

Parameters:

  • e (Object) —

    the start value.

Returns:

  • (Object) —

    the reduced value.



233
234
235
236
237
238
239
 
# File 'lib/immutable/stream.rb', line 233

def foldr(e, &block)
  if null?
    e
  else
    yield(head, tail.foldr(e, &block))
  end
end

#foldr1(&block) ⇒ Object

Reduces self using block from right to left. If self is empty, Immutable::List::EmptyError is raised.

Returns:

  • (Object) —

    the reduced value.



245
246
247
248
249
250
251
 
# File 'lib/immutable/stream.rb', line 245

def foldr1(&block)
  if tail.null?
    head
  else
    yield(head, tail.foldr1(&block))
  end
end

#head ⇒ Object Also known as: first

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

Returns:

  • (Object) —

    the first element of self.



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

def head
  force.head.force
end

#init ⇒ Stream

Returns all the elements of self except the last one. If self is empty, Immutable::List::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 null?
      raise List::EmptyError
    else
      if tail.null?
        Stream.null
      else
        Stream.cons(->{head}, ->{tail.init})
      end
    end
  }
end

#inspect ⇒ String

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.



382
383
384
 
# File 'lib/immutable/stream.rb', line 382

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.



352
353
354
355
356
357
358
359
360
 
# File 'lib/immutable/stream.rb', line 352

def intersperse(sep)
  Stream.lazy {
    if null?
      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::List::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.null?
    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.



330
331
332
333
334
335
336
337
338
 
# File 'lib/immutable/stream.rb', line 330

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

#null? ⇒ true, false Also known as: empty?

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



136
137
138
 
# File 'lib/immutable/stream.rb', line 136

def null?
  force == NULL
end

#prepend(&block) ⇒ Stream

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

Examples:

A Stream which has 123 as the only element.

s = Stream.null.prepend {123}
p s.to_list #=> List[123]

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

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

Returns:

  • (Stream) —

    the new stream.



86
87
88
 
# File 'lib/immutable/stream.rb', line 86

def prepend(&block)
  Stream.eager(Pair.new(Stream.delay(&block), self))
end

#reverse ⇒ Stream

Returns the elements of self in reverse order.

Returns:

  • (Stream) —

    the reversed stream.



343
344
345
 
# File 'lib/immutable/stream.rb', line 343

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

#tail ⇒ Stream

Returns the stream stored in the tail of self. If self is empty, Immutable::List::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.



440
441
442
443
444
445
446
447
448
 
# File 'lib/immutable/stream.rb', line 440

def take(n)
  Stream.lazy {
    if n <= 0 || null?
      Stream.null
    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.



469
470
471
472
473
474
475
476
477
 
# File 'lib/immutable/stream.rb', line 469

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

#to_list ⇒ List

Converts self to a list.

Returns:

  • (List) —

    a list.



496
497
498
 
# File 'lib/immutable/stream.rb', line 496

def to_list
  foldr(List[]) { |x, xs| Cons[x, xs] }
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.



531
532
533
534
535
536
537
538
539
540
541
 
# File 'lib/immutable/stream.rb', line 531

def zip(*xss)
  Stream.lazy {
    if null?
      self
    else
      heads = xss.map { |xs| xs.null? ? nil : xs.head }
      tails = xss.map { |xs| xs.null? ? Stream.null : 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.



551
552
553
554
555
556
557
558
559
560
561
562
 
# File 'lib/immutable/stream.rb', line 551

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