Class: Immutable::List

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Foldable
Defined in:
lib/immutable/list.rb

Overview

Immutable::List represents an immutable list.

Immutable::List is an abstract class and List.[] should be used instead of new. For example:

include Immutable
p List[]      #=> List[]
p List[1, 2]  #=> List[1, 2]

Immutable::Nil represents an empty list, and Immutable::Cons represents a cons cell, which is a node in a list. For example:

p Nil                    #=> List[]
p Cons[1, Cons[2, Nil]]  #=> List[1, 2]

Direct Known Subclasses

Cons

Defined Under Namespace

Classes: EmptyError

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Foldable

#length, #product, #sum

Class Method Details

.[](*elements) ⇒ List

Creates a new list populated with the given objects.

Parameters:

  • elements (Array<Object>) —

    the elements of the list.

Returns:

  • (List) —

    the new list.



34
35
36
 
# File 'lib/immutable/list.rb', line 34

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

.from_array(ary) ⇒ List

Converts the given array to a list.

Parameters:

  • ary (Array, #reverse_each) —

    the array to convert.

Returns:

  • (List) —

    the list converted from ary.



42
43
44
45
46
 
# File 'lib/immutable/list.rb', line 42

def self.from_array(ary)
  ary.reverse_each.inject(Nil) { |x, y|
    Cons.new(y, x)
  }
end

.from_enum(enum) ⇒ List

Converts the given Enumerable object to a list.

Parameters:

  • enum (#inject) —

    the Enumerable object to convert.

Returns:

  • (List) —

    the list converted from enum.



52
53
54
55
56
 
# File 'lib/immutable/list.rb', line 52

def self.from_enum(enum)
  enum.inject(Nil) { |x, y|
    Cons.new(y, x)
  }.reverse
end

.unfoldr(e, &block) ⇒ List

Builds a list 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 list, or returns [a, b], where a is the head of the list 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:

  • (List) —

    the list built from the seed value and the block.



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

def self.unfoldr(e, &block)
  x = yield(e)
  if x.nil?
    Nil
  else
    y, z = x
    Cons[y, unfoldr(z, &block)]
  end
end

Instance Method Details

#+(xs) ⇒ List

Appends two lists self and xs.

Parameters:

  • xs (List) —

    the list to append.

Returns:

  • (List) —

    the new list.



66
67
68
 
# File 'lib/immutable/list.rb', line 66

def +(xs)
  foldr(xs) { |y, ys| Cons[y, ys] }
end

#==(xs) ⇒ true, false

Returns whether self equals to xs.

false.

Parameters:

  • xs (List) —

    the list to compare.

Returns:

  • (true, false) —

    true if self equals to xs; otherwise,



75
76
77
 
# File 'lib/immutable/list.rb', line 75

def ==(xs)
  # this method should be overriden
end

#[](n) ⇒ Object

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

Returns:

  • (Object) —

    the nth element.



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

def [](n)
  # this method should be overriden
end

#drop(n) ⇒ List

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

Parameters:

  • n (Integer) —

    the number of elements to drop.

Returns:

  • (List) —

    the suffix of self after the first n elements.



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

def drop(n)
  # this method should be overriden
end

#drop_while(&block) ⇒ List

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

Returns:

  • (List) —

    the suffix of the elements of self.



306
307
308
 
# File 'lib/immutable/list.rb', line 306

def drop_while(&block)
  # this method should be overriden
end

#each(&block) ⇒ Object

Calls block once for each element in self.



59
60
 
# File 'lib/immutable/list.rb', line 59

def each(&block)
end

#empty? ⇒ true, false

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



123
124
125
 
# File 'lib/immutable/list.rb', line 123

def empty?
  # this method should be overriden
end

#filter ⇒ List

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

Returns:

  • (List) —

    the elements that satisfies the condition.



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

def filter
  foldr(Nil) { |x, xs|
    if yield(x)
      Cons[x, xs]
    else
      xs
    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.



322
323
324
 
# File 'lib/immutable/list.rb', line 322

def find(&block)
  # this method should be overriden
end

#first ⇒ Object

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

Returns:

  • (Object) —

    the first element of self.



91
92
93
 
# File 'lib/immutable/list.rb', line 91

def first
  head
end

#flat_map ⇒ List Also known as: concat_map, bind

Returns the list obtained by concatenating the results of the given block for each element in self.

Returns:

  • (List) —

    the obtained list.



237
238
239
 
# File 'lib/immutable/list.rb', line 237

def flat_map
  foldr(Nil) { |x, xs| yield(x) + xs }
end

#flatten ⇒ List Also known as: concat

Concatenates a list of lists.

Returns:

  • (List) —

    the concatenated list.



227
228
229
 
# File 'lib/immutable/list.rb', line 227

def flatten
  foldr(Nil) { |x, xs| x + xs }
end

#foldl(e, &block) ⇒ Object

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

List[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.



212
213
214
 
# File 'lib/immutable/list.rb', line 212

def foldl(e, &block)
  # this method should be overriden
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.



220
221
222
 
# File 'lib/immutable/list.rb', line 220

def foldl1(&block)
  # this method should be overriden
end

#foldr(e, &block) ⇒ Object

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

List[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.



193
194
195
 
# File 'lib/immutable/list.rb', line 193

def foldr(e, &block)
  # this method should be overriden
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.



201
202
203
 
# File 'lib/immutable/list.rb', line 201

def foldr1(&block)
  # this method should be overriden
end

#head ⇒ Object

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

Returns:

  • (Object) —

    the first element of self.



83
84
85
 
# File 'lib/immutable/list.rb', line 83

def head
  # this method should be overriden
end

#init ⇒ List

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

Returns:

  • (List) —

    the elements of self except the last one.



116
117
118
 
# File 'lib/immutable/list.rb', line 116

def init
  # this method should be overriden
end

#intercalate(xs) ⇒ List

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

Parameters:

  • xs (List) —

    the list to insert between lists.

Returns:

  • (List) —

    the new list.



165
166
167
 
# File 'lib/immutable/list.rb', line 165

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

#intersperse(sep) ⇒ List

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

Parameters:

  • sep (Object) —

    the object to insert between elements.

Returns:

  • (List) —

    the new list.



154
155
156
 
# File 'lib/immutable/list.rb', line 154

def intersperse(sep)
  # this method should be overriden
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.



99
100
101
 
# File 'lib/immutable/list.rb', line 99

def last
  # this method should be overriden
end

#map ⇒ List

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

Returns:

  • (List) —

    the obtained list.



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

def map
  foldr(Nil) { |x, xs| Cons[yield(x), xs] }
end

#null? ⇒ true, false

Returns whether self is empty.

Returns:

  • (true, false) —

    true if self is empty; otherwise, false.



130
131
132
 
# File 'lib/immutable/list.rb', line 130

def null?
  empty?
end

#reverse ⇒ List

Returns the elements of self in reverse order.

Returns:

  • (List) —

    the reversed list.



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

def reverse
  foldl(Nil) { |x, y| Cons[y, x] }
end

#subsequences ⇒ List<List>

Returns the list of all subsequences of self.

Returns:

  • (List<List>) —

    the list of subsequences.



182
183
184
 
# File 'lib/immutable/list.rb', line 182

def subsequences
  Cons[List[], nonempty_subsequences]
end

#tail ⇒ List

Returns the elements after the head of self. If self is empty, Immutable::List::EmptyError is raised.

Returns:

  • (List) —

    the elements after the head of self.



107
108
109
 
# File 'lib/immutable/list.rb', line 107

def tail
  # this method should be overriden
end

#take(n) ⇒ List

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

Parameters:

  • n (Integer) —

    the number of elements to take.

Returns:

  • (List) —

    the first n elements of self.



281
282
283
 
# File 'lib/immutable/list.rb', line 281

def take(n)
  # this method should be overriden
end

#take_while(&block) ⇒ List

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

Returns:

  • (List) —

    the prefix of the elements of self.



298
299
300
 
# File 'lib/immutable/list.rb', line 298

def take_while(&block)
  # this method should be overriden
end

#to_list ⇒ List

Returns self.

Returns:



313
314
315
 
# File 'lib/immutable/list.rb', line 313

def to_list
  self
end

#transpose ⇒ List

Transposes the rows and columns of self. For example:

p List[List[1, 2, 3], List[4, 5, 6]].transpose
#=> List[List[1, 4], List[2, 5], List[3, 6]]

Returns:

  • (List) —

    the transposed list.



175
176
177
 
# File 'lib/immutable/list.rb', line 175

def transpose
  # this method should be overriden
end

#zip(*xss) ⇒ List

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

Parameters:

  • xss (Array<List>) —

    the input lists.

Returns:

  • (List) —

    the new list.



346
347
348
 
# File 'lib/immutable/list.rb', line 346

def zip(*xss)
  # this method should be overriden
end

#zip_with(*xss, &block) ⇒ List

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

Parameters:

  • xss (Array<List>) —

    the input lists.

Returns:

  • (List) —

    the new list.



358
359
360
 
# File 'lib/immutable/list.rb', line 358

def zip_with(*xss, &block)
  # this method should be overriden
end