Class: Immutable::List

Inherits:
Object
  • Object
show all
Defined in:
lib/immutable/list.rb

Overview

Immutable::List represents an immutable list.

Immutable::List is an abstract class and Immutable::List.[] should be used instead of Immutable::List.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

Class Method Details

.[](*args) ⇒ Object

Returns a new list populated with the given objects.



28
29
30
 
# File 'lib/immutable/list.rb', line 28

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

.from_array(ary) ⇒ Object

Converts the given array ary to a list.



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

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

.from_enum(enum) ⇒ Object

Converts enum to a list. enum should respond to each.



40
41
42
43
44
 
# File 'lib/immutable/list.rb', line 40

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

.unfoldr(e, &block) ⇒ Object

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.



199
200
201
202
203
204
205
206
207
 
# File 'lib/immutable/list.rb', line 199

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) ⇒ Object

Appends two lists self and xs.



47
48
49
 
# File 'lib/immutable/list.rb', line 47

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

#drop(n) ⇒ Object

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

Raises:

  • (ScriptError) 


218
219
220
 
# File 'lib/immutable/list.rb', line 218

def drop(n)
  raise ScriptError, "this method should be overriden"
end

#drop_while(&block) ⇒ Object

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

Raises:

  • (ScriptError) 


230
231
232
 
# File 'lib/immutable/list.rb', line 230

def drop_while(&block)
  raise ScriptError, "this method should be overriden"
end

#empty? ⇒ Boolean

Returns true if self is empty.

Returns:

  • (Boolean)

Raises:

  • (ScriptError) 


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

def empty?
  raise ScriptError, "this method should be overriden"
end

#filter ⇒ Object

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



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

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.

Raises:

  • (ScriptError) 


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

def find(&block)
  raise ScriptError, "this method should be overriden"
end

#first ⇒ Object

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



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

def first
  head
end

#flat_map ⇒ Object Also known as: concat_map, bind

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



169
170
171
 
# File 'lib/immutable/list.rb', line 169

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

#flatten ⇒ Object Also known as: concat

Concatenates a list of lists.



160
161
162
 
# File 'lib/immutable/list.rb', line 160

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

Raises:

  • (ScriptError) 


149
150
151
 
# File 'lib/immutable/list.rb', line 149

def foldl(e, &block)
  raise ScriptError, "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.

Raises:

  • (ScriptError) 


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

def foldl1(&block)
  raise ScriptError, "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

Raises:

  • (ScriptError) 


135
136
137
 
# File 'lib/immutable/list.rb', line 135

def foldr(e, &block)
  raise ScriptError, "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.

Raises:

  • (ScriptError) 


141
142
143
 
# File 'lib/immutable/list.rb', line 141

def foldr1(&block)
  raise ScriptError, "this method should be overriden"
end

#head ⇒ Object

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

Raises:

  • (ScriptError) 


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

def head
  raise ScriptError, "this method should be overriden"
end

#init ⇒ Object

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

Raises:

  • (ScriptError) 


78
79
80
 
# File 'lib/immutable/list.rb', line 78

def init
  raise ScriptError, "this method should be overriden"
end

#intercalate(xs) ⇒ Object

Inserts xs in between the lists in self and concatenates the result. xss.intercalate(xs) is equivalent to xss.intersperse(xs).flatten.



119
120
121
 
# File 'lib/immutable/list.rb', line 119

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

#intersperse(xs) ⇒ Object

Inserts xs in between the lists in self.

Raises:

  • (ScriptError) 


111
112
113
 
# File 'lib/immutable/list.rb', line 111

def intersperse(xs)
  raise ScriptError, "this method should be overriden"
end

#last ⇒ Object

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

Raises:

  • (ScriptError) 


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

def last
  raise ScriptError, "this method should be overriden"
end

#length ⇒ Object Also known as: size

Returns the number of elements in self. May be zero.



93
94
95
 
# File 'lib/immutable/list.rb', line 93

def length
  foldl(0) { |x, y| x + 1 }
end

#map ⇒ Object

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



101
102
103
 
# File 'lib/immutable/list.rb', line 101

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

#null? ⇒ Boolean

Returns true if self is empty.

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/immutable/list.rb', line 88

def null?
  empty?
end

#product ⇒ Object

Computes the product of the numbers in self.



185
186
187
 
# File 'lib/immutable/list.rb', line 185

def product
  foldl(1, &:*)
end

#reverse ⇒ Object

Returns the elements of self in reverse order.



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

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

#sum ⇒ Object

Computes the sum of the numbers in self.



180
181
182
 
# File 'lib/immutable/list.rb', line 180

def sum
  foldl(0, &:+)
end

#tail ⇒ Object

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

Raises:

  • (ScriptError) 


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

def tail
  raise ScriptError, "this method should be overriden"
end

#take(n) ⇒ Object

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

Raises:

  • (ScriptError) 


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

def take(n)
  raise ScriptError, "this method should be overriden"
end

#take_while(&block) ⇒ Object

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

Raises:

  • (ScriptError) 


224
225
226
 
# File 'lib/immutable/list.rb', line 224

def take_while(&block)
  raise ScriptError, "this method should be overriden"
end

#transpose ⇒ Object

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]]

Raises:

  • (ScriptError) 


127
128
129
 
# File 'lib/immutable/list.rb', line 127

def transpose
  raise ScriptError, "this method should be overriden"
end