Module: Immutable::List

Includes:
Enumerable
Defined in:
lib/immutable/list.rb

Overview

A List can be constructed with List[], or Enumerable#to_list. It consists of a head (the first element) and a tail (which itself is also a List, containing all the remaining elements).

This is a singly linked list. Prepending to the list with #add runs in constant time. Traversing the list from front to back is efficient, however, indexed access runs in linear time because the list needs to be traversed to find the element.

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#<=>, #==, #compact, #each_index, #grep, #grep_v, #join, #product, #reject, #sum, #to_set

Dynamic Method Handling

This class handles dynamic methods through the method_missing method

#method_missing(name, *args, &block) ⇒ Object, List (private)

Perform compositions of car and cdr operations (traditional shorthand for head and tail respectively). Their names consist of a c, followed by at least one a or d, and finally an r. The series of as and ds in the method name identify the series of car and cdr operations performed, in inverse order.

Examples:

l = Immutable::List[nil, Immutable::List[1]]
l.car   # => nil
l.cdr   # => Immutable::List[Immutable::List[1]]
l.cadr  # => Immutable::List[1]
l.caadr # => 1

Returns:



1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
 
# File 'lib/immutable/list.rb', line 1249

def method_missing(name, *args, &block)
  if name.to_s.match(CADR)
    code = "def #{name}; self."
    code << Regexp.last_match[1].reverse.chars.map do |char|
      {'a' => 'head', 'd' => 'tail'}[char]
    end.join('.')
    code << '; end'
    List.class_eval(code)
    send(name, *args, &block)
  else
    super
  end
end

Class Method Details

.[](*items) ⇒ List

Create a new List populated with the given items.

Examples:

list = Immutable::List[:a, :b, :c]
# => Immutable::List[:a, :b, :c]

Returns:



132
133
134
 
# File 'lib/immutable/list.rb', line 132

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

.empty ⇒ List

Return an empty List.

Returns:



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

def self.empty
  EmptyList
end

Instance Method Details

#<<(item) ⇒ List

Create a new List with item added at the end. This is much less efficient than adding items at the front.

Examples:

Immutable::List[:a, :b] << :c
# => Immutable::List[:a, :b, :c]

Parameters:

  • item (Object) —

    The item to add

Returns:



203
204
205
 
# File 'lib/immutable/list.rb', line 203

def <<(item)
  append(List[item])
end

#add(item) ⇒ List Also known as: cons

Create a new List with item added at the front. This is a constant time operation.

Examples:

Immutable::List[:b, :c].add(:a)
# => Immutable::List[:a, :b, :c]

Parameters:

  • item (Object) —

    The item to add

Returns:



189
190
191
 
# File 'lib/immutable/list.rb', line 189

def add(item)
  Cons.new(item, self)
end

#append(other) ⇒ List Also known as: concat, +

Return a List with all items from this List, followed by all items from other.

Examples:

Immutable::List[1, 2, 3].append(Immutable::List[4, 5])
# => Immutable::List[1, 2, 3, 4, 5]

Parameters:

  • other (List) —

    The list to add onto the end of this one

Returns:



377
378
379
380
381
382
 
# File 'lib/immutable/list.rb', line 377

def append(other)
  LazyList.new do
    next other if empty?
    Cons.new(head, tail.append(other))
  end
end

#at(index) ⇒ Object

Retrieve the item at index. Negative indices count back from the end of the list (-1 is the last item). If index is invalid (either too high or too low), return nil.

Parameters:

  • index (Integer) —

    The index to retrieve

Returns:

  • (Object) 


787
788
789
790
791
792
793
794
795
796
 
# File 'lib/immutable/list.rb', line 787

def at(index)
  index += size if index < 0
  return nil if index < 0
  node = self
  while index > 0
    node = node.tail
    index -= 1
  end
  node.head
end

#break {|item| ... } ⇒ Array

Return two Lists, one up to (but not including) the first item for which the block returns true, and another of all the remaining items.

Examples:

Immutable::List[1, 3, 4, 2, 5].break { |x| x > 3 }
# => [Immutable::List[1, 3], Immutable::List[4, 2, 5]]

Yields:

  • (item)

Returns:

  • (Array) 


525
526
527
528
 
# File 'lib/immutable/list.rb', line 525

def break(&block)
  return span unless block_given?
  span { |item| !yield(item) }
end

#cached_size? ⇒ Integer

Return true if the size of this list can be obtained in constant time (without traversing the list).

Returns:

  • (Integer) 


1230
1231
1232
 
# File 'lib/immutable/list.rb', line 1230

def cached_size?
  false
end

#chunk(number) ⇒ List

Split the items in this list in groups of number. Return a list of lists.

Examples:

("a".."o").to_list.chunk(5)
# => Immutable::List[
#      Immutable::List["a", "b", "c", "d", "e"],
#      Immutable::List["f", "g", "h", "i", "j"],
#      Immutable::List["k", "l", "m", "n", "o"]]

Returns:



726
727
728
729
730
731
732
 
# File 'lib/immutable/list.rb', line 726

def chunk(number)
  LazyList.new do
    next self if empty?
    first, remainder = split_at(number)
    Cons.new(first, remainder.chunk(number))
  end
end

#clear ⇒ List

Return an empty List. If used on a subclass, returns an empty instance of that class.

Returns:



534
535
536
 
# File 'lib/immutable/list.rb', line 534

def clear
  EmptyList
end

#combination(n) ⇒ List

Return a List of all combinations of length n of items from this List.

Examples:

Immutable::List[1,2,3].combination(2)
# => Immutable::List[
#      Immutable::List[1, 2],
#      Immutable::List[1, 3],
#      Immutable::List[2, 3]]

Returns:



708
709
710
711
712
713
714
 
# File 'lib/immutable/list.rb', line 708

def combination(n)
  return Cons.new(EmptyList) if n == 0
  LazyList.new do
    next self if empty?
    tail.combination(n - 1).map { |list| list.cons(head) }.append(tail.combination(n))
  end
end

#cycle ⇒ List

Concatenate an infinite series of copies of this List together into a new List. Or, if empty, just return an empty list.

Examples:

Immutable::List[1, 2, 3].cycle.take(10)
# => Immutable::List[1, 2, 3, 1, 2, 3, 1, 2, 3, 1]

Returns:



458
459
460
461
462
463
 
# File 'lib/immutable/list.rb', line 458

def cycle
  LazyList.new do
    next self if empty?
    Cons.new(head, tail.append(cycle))
  end
end

#delete(obj) ⇒ List

Return a List with all elements equal to obj removed. #== is used for testing equality.

Examples:

Immutable::List[:a, :b, :a, :a, :c].delete(:a) # => Immutable::List[:b, :c]

Parameters:

  • obj (Object) —

    The object to remove.

Returns:



994
995
996
997
998
999
 
# File 'lib/immutable/list.rb', line 994

def delete(obj)
  list = self
  list = list.tail while list.head == obj && !list.empty?
  return EmptyList if list.empty?
  LazyList.new { Cons.new(list.head, list.tail.delete(obj)) }
end

#delete_at(index) ⇒ List

Return a List containing the same items, minus the one at index. If index is negative, it counts back from the end of the list.

Examples:

Immutable::List[1, 2, 3].delete_at(1)  # => Immutable::List[1, 3]
Immutable::List[1, 2, 3].delete_at(-1) # => Immutable::List[1, 2]

Parameters:

  • index (Integer) —

    The index of the item to remove

Returns:



1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
 
# File 'lib/immutable/list.rb', line 1010

def delete_at(index)
  if index == 0
    tail
  elsif index < 0
    index += size if index < 0
    return self if index < 0
    delete_at(index)
  else
    LazyList.new { Cons.new(head, tail.delete_at(index - 1)) }
  end
end

#drop(number) ⇒ List

Return a List containing all items after the first number items from this List.

Examples:

Immutable::List[1, 3, 5, 7, 6, 4, 2].drop(3)
# => Immutable::List[7, 6, 4, 2]

Parameters:

  • number (Integer) —

    The number of items to skip over

Returns:



357
358
359
360
361
362
363
364
365
366
 
# File 'lib/immutable/list.rb', line 357

def drop(number)
  LazyList.new do
    list = self
    while !list.empty? && number > 0
      number -= 1
      list = list.tail
    end
    list
  end
end

#drop_while {|item| ... } ⇒ List, Enumerator

Return a List which contains all elements starting from the first element for which the block returns nil or false.

Examples:

Immutable::List[1, 3, 5, 7, 6, 4, 2].drop_while { |e| e < 5 }
# => Immutable::List[5, 7, 6, 4, 2]

Yields:

  • (item)

Returns:

  • (List, Enumerator) 


308
309
310
311
312
313
314
315
 
# File 'lib/immutable/list.rb', line 308

def drop_while(&block)
  return enum_for(:drop_while) unless block_given?
  LazyList.new do
    list = self
    list = list.tail while !list.empty? && yield(list.head)
    list
  end
end

#dup ⇒ List Also known as: clone

Return self. Since this is an immutable object duplicates are equivalent.

Returns:



1187
1188
1189
 
# File 'lib/immutable/list.rb', line 1187

def dup
  self
end

#each {|item| ... } ⇒ self

Call the given block once for each item in the list, passing each item from first to last successively to the block. If no block is given, returns an Enumerator.

Yields:

  • (item)

Returns:

  • (self) 


213
214
215
216
217
218
219
220
 
# File 'lib/immutable/list.rb', line 213

def each
  return to_enum unless block_given?
  list = self
  until list.empty?
    yield(list.head)
    list = list.tail
  end
end

#each_chunk(number) {|list| ... } ⇒ self, Enumerator Also known as: each_slice

Split the items in this list in groups of number, and yield each group to the block (as a List). If no block is given, returns an Enumerator.

Yields:

  • (list) —

    Once for each chunk.

Returns:

  • (self, Enumerator) 


740
741
742
743
744
 
# File 'lib/immutable/list.rb', line 740

def each_chunk(number, &block)
  return enum_for(:each_chunk, number) unless block_given?
  chunk(number).each(&block)
  self
end

#eql?(other) ⇒ Boolean

Return true if other has the same type and contents as this Hash.

Parameters:

  • other (Object) —

    The collection to compare with

Returns:

  • (Boolean) 


1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
 
# File 'lib/immutable/list.rb', line 1165

def eql?(other)
  list = self
  loop do
    return true if other.equal?(list)
    return false unless other.is_a?(List)
    return other.empty? if list.empty?
    return false if other.empty?
    return false unless other.head.eql?(list.head)
    list = list.tail
    other = other.tail
  end
end

#fill(object) ⇒ List #fill(object, index) ⇒ List #fill(object, index, length) ⇒ List

Replace a range of indexes with the given object.

Overloads:

  • #fill(object) ⇒ List

    Return a new List of the same size, with every index set to object.

    Examples:

    Immutable::List["A", "B", "C", "D", "E", "F"].fill("Z")
# => Immutable::List["Z", "Z", "Z", "Z", "Z", "Z"]

    Parameters:

    • object (Object) —

      Fill value.

  • #fill(object, index) ⇒ List

    Return a new List with all indexes from index to the end of the vector set to obj.

    Examples:

    Immutable::List["A", "B", "C", "D", "E", "F"].fill("Z", 3)
# => Immutable::List["A", "B", "C", "Z", "Z", "Z"]

    Parameters:

    • object (Object) —

      Fill value.

    • index (Integer) —

      Starting index. May be negative.

  • #fill(object, index, length) ⇒ List

    Return a new List with length indexes, beginning from index, set to obj. Expands the List if length would extend beyond the current length.

    Examples:

    Immutable::List["A", "B", "C", "D", "E", "F"].fill("Z", 3, 2)
# => Immutable::List["A", "B", "C", "Z", "Z", "F"]
Immutable::List["A", "B"].fill("Z", 1, 5)
# => Immutable::List["A", "Z", "Z", "Z", "Z", "Z"]

    Parameters:

    • object (Object) —

      Fill value.

    • index (Integer) —

      Starting index. May be negative.

    • length (Integer)

Returns:

Raises:

  • (IndexError) —

    if index is out of negative range.



1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
 
# File 'lib/immutable/list.rb', line 1058

def fill(obj, index = 0, length = nil)
  if index == 0
    length ||= size
    if length > 0
      LazyList.new do
        Cons.new(obj, tail.fill(obj, 0, length-1))
      end
    else
      self
    end
  elsif index > 0
    LazyList.new do
      Cons.new(head, tail.fill(obj, index-1, length))
    end
  else
    raise IndexError if index < -size
    fill(obj, index + size, length)
  end
end

#flat_map(&block) ⇒ List

Return a List which is realized by transforming each item into a List, and flattening the resulting lists.

Examples:

Immutable::List[1, 2, 3].flat_map { |x| Immutable::List[x, 100] }
# => Immutable::List[1, 100, 2, 100, 3, 100]

Returns:



248
249
250
251
252
253
254
255
256
 
# File 'lib/immutable/list.rb', line 248

def flat_map(&block)
  return enum_for(:flat_map) unless block_given?
  LazyList.new do
    next self if empty?
    head_list = List.from_enum(yield(head))
    next tail.flat_map(&block) if head_list.empty?
    Cons.new(head_list.first, head_list.drop(1).append(tail.flat_map(&block)))
  end
end

#flatten ⇒ List

Return a new List with all nested lists recursively "flattened out", that is, their elements inserted into the new List in the place where the nested list originally was.

Examples:

Immutable::List[Immutable::List[1, 2], Immutable::List[3, 4]].flatten
# => Immutable::List[1, 2, 3, 4]

Returns:



756
757
758
759
760
761
762
 
# File 'lib/immutable/list.rb', line 756

def flatten
  LazyList.new do
    next self if empty?
    next head.append(tail.flatten) if head.is_a?(List)
    Cons.new(head, tail.flatten)
  end
end

#group_by {|item| ... } ⇒ Hash Also known as: group

Passes each item to the block, and gathers them into a Hash where the keys are return values from the block, and the values are Lists of items for which the block returned that value.

Examples:

Immutable::List["a", "b", "ab"].group_by { |e| e.size }
# Immutable::Hash[
#   1 => Immutable::List["b", "a"],
#   2 => Immutable::List["ab"]
# ]

Yields:

  • (item)

Returns:



776
777
778
 
# File 'lib/immutable/list.rb', line 776

def group_by(&block)
  group_by_with(EmptyList, &block)
end

#hash ⇒ Integer

See Object#hash

Returns:

  • (Integer) 


1180
1181
1182
 
# File 'lib/immutable/list.rb', line 1180

def hash
  reduce(0) { |hash, item| (hash << 5) - hash + item.hash }
end

#indices(object) ⇒ List #indices {|item| ... } ⇒ List

Return a List of indices of matching objects.

Overloads:

  • #indices(object) ⇒ List

    Return a List of indices where object is found. Use #== for testing equality.

    Examples:

    Immutable::List[1, 2, 3, 4].indices(2)
# => Immutable::List[1]
  • #indices {|item| ... } ⇒ List

    Pass each item successively to the block. Return a list of indices where the block returns true.

    Examples:

    Immutable::List[1, 2, 3, 4].indices { |e| e.even? }
# => Immutable::List[1, 3]

    Yields:

    • (item)

Returns:



893
894
895
896
897
898
899
900
901
902
903
904
905
 
# File 'lib/immutable/list.rb', line 893

def indices(object = Undefined, i = 0, &block)
  return indices { |item| item == object } if not block_given?
  return EmptyList if empty?
  LazyList.new do
    node = self
    loop do
      break Cons.new(i, node.tail.indices(Undefined, i + 1, &block)) if yield(node.head)
      node = node.tail
      break EmptyList if node.empty?
      i += 1
    end
  end
end

#init ⇒ List

Return a List with all elements except the last one.

Examples:

Immutable::List["a", "b", "c"].init # => Immutable::List["a", "b"]

Returns:



651
652
653
654
 
# File 'lib/immutable/list.rb', line 651

def init
  return EmptyList if tail.empty?
  LazyList.new { Cons.new(head, tail.init) }
end

#inits ⇒ List

Return a List of all prefixes of this list.

Examples:

Immutable::List[1,2,3].inits
# => Immutable::List[
#      Immutable::List[1],
#      Immutable::List[1, 2],
#      Immutable::List[1, 2, 3]]

Returns:



691
692
693
694
695
696
 
# File 'lib/immutable/list.rb', line 691

def inits
  LazyList.new do
    next self if empty?
    Cons.new(List[head], tail.inits.map { |list| list.cons(head) })
  end
end

#insert(index, *items) ⇒ List

Return a new List with the given items inserted before the item at index.

Examples:

Immutable::List["A", "D", "E"].insert(1, "B", "C") # => Immutable::List["A", "B", "C", "D", "E"]

Parameters:

  • index (Integer) —

    The index where the new items should go

  • items (Array) —

    The items to add

Returns:



973
974
975
976
977
978
979
980
981
982
983
984
 
# File 'lib/immutable/list.rb', line 973

def insert(index, *items)
  if index == 0
    return List.from_enum(items).append(self)
  elsif index > 0
    LazyList.new do
      Cons.new(head, tail.insert(index-1, *items))
    end
  else
    raise IndexError if index < -size
    insert(index + size, *items)
  end
end

#inspect ⇒ String

Return the contents of this List as a programmer-readable String. If all the items in the list are serializable as Ruby literal strings, the returned string can be passed to eval to reconstitute an equivalent List.

Returns:

  • (String) 


1203
1204
1205
1206
1207
 
# File 'lib/immutable/list.rb', line 1203

def inspect
  result = 'Immutable::List['
  each_with_index { |obj, i| result << ', ' if i > 0; result << obj.inspect }
  result << ']'
end

#intersperse(sep) ⇒ List

Return a new List with sep inserted between each of the existing elements.

Examples:

Immutable::List["one", "two", "three"].intersperse(" ")
# => Immutable::List["one", " ", "two", " ", "three"]

Returns:



587
588
589
590
591
592
 
# File 'lib/immutable/list.rb', line 587

def intersperse(sep)
  LazyList.new do
    next self if tail.empty?
    Cons.new(head, Cons.new(sep, tail.intersperse(sep)))
  end
end

#last ⇒ Object

Return the last item in this list.

Returns:

  • (Object) 


658
659
660
661
662
 
# File 'lib/immutable/list.rb', line 658

def last
  list = self
  list = list.tail until list.tail.empty?
  list.head
end

#map {|item| ... } ⇒ List, Enumerator Also known as: collect

Return a List in which each element is derived from the corresponding element in this List, transformed through the given block. If no block is given, returns an Enumerator.

Examples:

Immutable::List[3, 2, 1].map { |e| e * e } # => Immutable::List[9, 4, 1]

Yields:

  • (item)

Returns:

  • (List, Enumerator) 


231
232
233
234
235
236
237
 
# File 'lib/immutable/list.rb', line 231

def map(&block)
  return enum_for(:map) unless block_given?
  LazyList.new do
    next self if empty?
    Cons.new(yield(head), tail.map(&block))
  end
end

#merge {|a, b| ... } ⇒ List

Merge all the nested lists into a single list, using the given comparator block to determine the order which items should be shifted out of the nested lists and into the output list.

Examples:

list_1 = Immutable::List[1, -3, -5]
list_2 = Immutable::List[-2, 4, 6]
Immutable::List[list_1, list_2].merge { |a,b| a.abs <=> b.abs }
# => Immutable::List[1, -2, -3, 4, -5, 6]

Yields:

  • (a, b) —

    Pairs of items from matching indices in each list.

Yield Returns:

  • (Integer) —

    Negative if the first element should be selected first, positive if the latter element, or zero if either.

Returns:



922
923
924
925
926
927
928
929
930
931
 
# File 'lib/immutable/list.rb', line 922

def merge(&comparator)
  return merge_by unless block_given?
  LazyList.new do
    sorted = reject(&:empty?).sort do |a, b|
      yield(a.head, b.head)
    end
    next EmptyList if sorted.empty?
    Cons.new(sorted.head.head, sorted.tail.cons(sorted.head.tail).merge(&comparator))
  end
end

#merge_by {|item| ... } ⇒ List

Merge all the nested lists into a single list, using sort keys generated by mapping the items in the nested lists through the given block to determine the order which items should be shifted out of the nested lists and into the output list. Whichever nested list's #head has the "lowest" sort key (according to their natural order) will be the first in the merged List.

Examples:

list_1 = Immutable::List[1, -3, -5]
list_2 = Immutable::List[-2, 4, 6]
Immutable::List[list_1, list_2].merge_by { |x| x.abs }
# => Immutable::List[1, -2, -3, 4, -5, 6]

Yields:

  • (item) —

    Once for each item in either list.

Yield Returns:

  • (Object) —

    A sort key for the element.

Returns:



948
949
950
951
952
953
954
955
956
957
 
# File 'lib/immutable/list.rb', line 948

def merge_by(&transformer)
  return merge_by { |item| item } unless block_given?
  LazyList.new do
    sorted = reject(&:empty?).sort_by do |list|
      yield(list.head)
    end
    next EmptyList if sorted.empty?
    Cons.new(sorted.head.head, sorted.tail.cons(sorted.head.tail).merge_by(&transformer))
  end
end

#partition {|item| ... } ⇒ List

Return two Lists, the first containing all the elements for which the block evaluates to true, the second containing the rest.

Examples:

Immutable::List[1, 2, 3, 4, 5, 6].partition { |x| x.even? }
# => [Immutable::List[2, 4, 6], Immutable::List[1, 3, 5]]

Yields:

  • (item) —

    Once for each item.

Returns:



1153
1154
1155
1156
1157
1158
1159
 
# File 'lib/immutable/list.rb', line 1153

def partition(&block)
  return enum_for(:partition) if not block_given?
  partitioner = Partitioner.new(self, block)
  mutex = Mutex.new
  [Partitioned.new(partitioner, partitioner.left, mutex),
   Partitioned.new(partitioner, partitioner.right, mutex)].freeze
end

#permutation(length = size) {|list| ... } ⇒ self, Enumerator

Yields all permutations of length n of the items in the list, and then returns self. If no length n is specified, permutations of the entire list will be yielded.

There is no guarantee about which order the permutations will be yielded in.

If no block is given, an Enumerator is returned instead.

Examples:

Immutable::List[1, 2, 3].permutation.to_a
# => [Immutable::List[1, 2, 3],
#     Immutable::List[2, 1, 3],
#     Immutable::List[2, 3, 1],
#     Immutable::List[1, 3, 2],
#     Immutable::List[3, 1, 2],
#     Immutable::List[3, 2, 1]]

Yields:

  • (list) —

    Once for each permutation.

Returns:

  • (self, Enumerator) 


1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
 
# File 'lib/immutable/list.rb', line 1097

def permutation(length = size, &block)
  return enum_for(:permutation, length) if not block_given?
  if length == 0
    yield EmptyList
  elsif length == 1
    each { |obj| yield Cons.new(obj, EmptyList) }
  elsif not empty?
    if length < size
      tail.permutation(length, &block)
    end

    tail.permutation(length-1) do |p|
      0.upto(length-1) do |i|
        left,right = p.split_at(i)
        yield left.append(right.cons(head))
      end
    end
  end
  self
end

#pop ⇒ List

Return a List containing all but the last item from this List.

Examples:

Immutable::List["A", "B", "C"].pop  # => Immutable::List["A", "B"]

Returns:



339
340
341
342
343
344
345
346
 
# File 'lib/immutable/list.rb', line 339

def pop
  LazyList.new do
    next self if empty?
    new_size = size - 1
    next Cons.new(head, tail.take(new_size - 1)) if new_size >= 1
    EmptyList
  end
end

#reverse ⇒ List

Return a List with the same items, but in reverse order.

Examples:

Immutable::List["A", "B", "C"].reverse # => Immutable::List["C", "B", "A"]

Returns:



392
393
394
 
# File 'lib/immutable/list.rb', line 392

def reverse
  LazyList.new { reduce(EmptyList) { |list, item| list.cons(item) }}
end

#rotate(count = 1) ⇒ Vector

Return a new List with the same elements, but rotated so that the one at index count is the first element of the new list. If count is positive, the elements will be shifted left, and those shifted past the lowest position will be moved to the end. If count is negative, the elements will be shifted right, and those shifted past the last position will be moved to the beginning.

Examples:

l = Immutable::List["A", "B", "C", "D", "E", "F"]
l.rotate(2)   # => Immutable::List["C", "D", "E", "F", "A", "B"]
l.rotate(-1)  # => Immutable::List["F", "A", "B", "C", "D", "E"]

Parameters:

  • count (Integer) (defaults to: 1) —

    The number of positions to shift items by

Returns:

Raises:

  • (TypeError) —

    if count is not an integer.



479
480
481
482
483
484
 
# File 'lib/immutable/list.rb', line 479

def rotate(count = 1)
  raise TypeError, 'expected Integer' if not count.is_a?(Integer)
  return self if empty? || (count % size) == 0
  count = (count >= 0) ? count % size : (size - (~count % size) - 1)
  drop(count).append(take(count))
end

#sample ⇒ Object

Return a randomly chosen element from this list.

Returns:

  • (Object) 


961
962
963
 
# File 'lib/immutable/list.rb', line 961

def sample
  at(rand(size))
end

#select {|item| ... } ⇒ List Also known as: find_all, keep_if

Return a List which contains all the items for which the given block returns true.

Examples:

Immutable::List["Bird", "Cow", "Elephant"].select { |e| e.size >= 4 }
# => Immutable::List["Bird", "Elephant"]

Yields:

  • (item) —

    Once for each item.

Returns:



267
268
269
270
271
272
273
274
275
276
277
 
# File 'lib/immutable/list.rb', line 267

def select(&block)
  return enum_for(:select) unless block_given?
  LazyList.new do
    list = self
    loop do
      break list if list.empty?
      break Cons.new(list.head, list.tail.select(&block)) if yield(list.head)
      list = list.tail
    end
  end
end

#size ⇒ Integer Also known as: length

Return the number of items in this List.

Returns:

  • (Integer) 


166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/immutable/list.rb', line 166

def size
  result, list = 0, self
  until list.empty?
    if list.cached_size?
      return result + list.size
    else
      result += 1
    end
    list = list.tail
  end
  result
end

#list.slice(index) ⇒ Object #list.slice(index, length) ⇒ List #list.slice(index..end) ⇒ Vector Also known as: []

Return specific objects from the List. All overloads return nil if the starting index is out of range.

Overloads:

  • #list.slice(index) ⇒ Object

    Returns a single object at the given index. If index is negative, count backwards from the end.

    Examples:

    l = Immutable::List["A", "B", "C", "D", "E", "F"]
l[2]  # => "C"
l[-1] # => "F"
l[6]  # => nil

    Parameters:

    • index (Integer) —

      The index to retrieve. May be negative.

    Returns:

    • (Object)
  • #list.slice(index, length) ⇒ List

    Return a sublist starting at index and continuing for length elements or until the end of the List, whichever occurs first.

    Examples:

    l = Immutable::List["A", "B", "C", "D", "E", "F"]
l[2, 3]  # => Immutable::List["C", "D", "E"]
l[-2, 3] # => Immutable::List["E", "F"]
l[20, 1] # => nil

    Parameters:

    • start (Integer) —

      The index to start retrieving items from. May be negative.

    • length (Integer) —

      The number of items to retrieve.

    Returns:

  • #list.slice(index..end) ⇒ Vector

    Return a sublist starting at index and continuing to index end or the end of the List, whichever occurs first.

    Examples:

    l = Immutable::List["A", "B", "C", "D", "E", "F"]
l[2..3]    # => Immutable::List["C", "D"]
l[-2..100] # => Immutable::List["E", "F"]
l[20..21]  # => nil

    Parameters:

    • range (Range) —

      The range of indices to retrieve.

    Returns:



838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
 
# File 'lib/immutable/list.rb', line 838

def slice(arg, length = (missing_length = true))
  if missing_length
    if arg.is_a?(Range)
      from, to = arg.begin, arg.end
      from += size if from < 0
      return nil if from < 0
      to   += size if to < 0
      to   += 1    if !arg.exclude_end?
      length = to - from
      length = 0 if length < 0
      list = self
      while from > 0
        return nil if list.empty?
        list = list.tail
        from -= 1
      end
      list.take(length)
    else
      at(arg)
    end
  else
    return nil if length < 0
    arg += size if arg < 0
    return nil if arg < 0
    list = self
    while arg > 0
      return nil if list.empty?
      list = list.tail
      arg -= 1
    end
    list.take(length)
  end
end

#sort ⇒ List #sort {|a, b| ... } ⇒ List

Return a new List with the same items, but sorted.

Overloads:

  • #sort ⇒ List

    Compare elements with their natural sort key (#<=>).

    Examples:

    Immutable::List["Elephant", "Dog", "Lion"].sort
# => Immutable::List["Dog", "Elephant", "Lion"]
  • #sort {|a, b| ... } ⇒ List

    Uses the block as a comparator to determine sorted order.

    Examples:

    Immutable::List["Elephant", "Dog", "Lion"].sort { |a,b| a.size <=> b.size }
# => Immutable::List["Dog", "Lion", "Elephant"]

    Yields:

    • (a, b) —

      Any number of times with different pairs of elements.

    Yield Returns:

    • (Integer) —

      Negative if the first element should be sorted lower, positive if the latter element, or 0 if equal.

Returns:



559
560
561
 
# File 'lib/immutable/list.rb', line 559

def sort(&comparator)
  LazyList.new { List.from_enum(super(&comparator)) }
end

#sort_by {|element| ... } ⇒ List

Return a new List with the same items, but sorted. The sort order is determined by mapping the items through the given block to obtain sort keys, and then sorting the keys according to their natural sort order (#<=>).

Examples:

Immutable::List["Elephant", "Dog", "Lion"].sort_by { |e| e.size }
# => Immutable::List["Dog", "Lion", "Elephant"]

Yields:

  • (element) —

    Once for each element.

Yield Returns:

  • a sort key object for the yielded element.

Returns:



575
576
577
578
 
# File 'lib/immutable/list.rb', line 575

def sort_by(&transformer)
  return sort unless block_given?
  LazyList.new { List.from_enum(super(&transformer)) }
end

#span {|item| ... } ⇒ Array

Return two Lists, one up to (but not including) the first item for which the block returns nil or false, and another of all the remaining items.

Examples:

Immutable::List[4, 3, 5, 2, 1].span { |x| x > 2 }
# => [Immutable::List[4, 3, 5], Immutable::List[2, 1]]

Yields:

  • (item)

Returns:

  • (Array) 


508
509
510
511
512
513
514
 
# File 'lib/immutable/list.rb', line 508

def span(&block)
  return [self, EmptyList].freeze unless block_given?
  splitter = Splitter.new(self, block)
  mutex = Mutex.new
  [Splitter::Left.new(splitter, splitter.left, mutex),
   Splitter::Right.new(splitter, mutex)].freeze
end

#split_at(number) ⇒ Array

Return two Lists, one of the first number items, and another with the remaining.

Examples:

Immutable::List["a", "b", "c", "d"].split_at(2)
# => [Immutable::List["a", "b"], Immutable::List["c", "d"]]

Parameters:

  • number (Integer) —

    The index at which to split this list

Returns:

  • (Array) 


495
496
497
 
# File 'lib/immutable/list.rb', line 495

def split_at(number)
  [take(number), drop(number)].freeze
end

#subsequences {|sublist| ... } ⇒ self

Yield every non-empty sublist to the given block. (The entire List also counts as one sublist.)

Examples:

Immutable::List[1, 2, 3].subsequences { |list| p list }
# prints:
# Immutable::List[1]
# Immutable::List[1, 2]
# Immutable::List[1, 2, 3]
# Immutable::List[2]
# Immutable::List[2, 3]
# Immutable::List[3]

Yields:

  • (sublist) —

    One or more contiguous elements from this list

Returns:

  • (self) 


1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
 
# File 'lib/immutable/list.rb', line 1133

def subsequences(&block)
  return enum_for(:subsequences) if not block_given?
  if not empty?
    1.upto(size) do |n|
      yield take(n)
    end
    tail.subsequences(&block)
  end
  self
end

#tails ⇒ List

Return a List of all suffixes of this list.

Examples:

Immutable::List[1,2,3].tails
# => Immutable::List[
#      Immutable::List[1, 2, 3],
#      Immutable::List[2, 3],
#      Immutable::List[3]]

Returns:



674
675
676
677
678
679
 
# File 'lib/immutable/list.rb', line 674

def tails
  LazyList.new do
    next self if empty?
    Cons.new(self, tail.tails)
  end
end

#take(number) ⇒ List

Return a List containing the first number items from this List.

Examples:

Immutable::List[1, 3, 5, 7, 6, 4, 2].take(3)
# => Immutable::List[1, 3, 5]

Parameters:

  • number (Integer) —

    The number of items to retain

Returns:



325
326
327
328
329
330
331
 
# File 'lib/immutable/list.rb', line 325

def take(number)
  LazyList.new do
    next self if empty?
    next Cons.new(head, tail.take(number - 1)) if number > 0
    EmptyList
  end
end

#take_while {|item| ... } ⇒ List, Enumerator

Return a List which contains all elements up to, but not including, the first element for which the block returns nil or false.

Examples:

Immutable::List[1, 3, 5, 7, 6, 4, 2].take_while { |e| e < 5 }
# => Immutable::List[1, 3]

Yields:

  • (item)

Returns:

  • (List, Enumerator) 


290
291
292
293
294
295
296
297
 
# File 'lib/immutable/list.rb', line 290

def take_while(&block)
  return enum_for(:take_while) unless block_given?
  LazyList.new do
    next self if empty?
    next Cons.new(head, tail.take_while(&block)) if yield(head)
    EmptyList
  end
end

#to_list ⇒ List

Return self.

Returns:



1194
1195
1196
 
# File 'lib/immutable/list.rb', line 1194

def to_list
  self
end

#transpose ⇒ List

Gather the first element of each nested list into a new List, then the second element of each nested list, then the third, and so on. In other words, if each nested list is a "row", return a List of "columns" instead.

Although the returned list is lazy, each returned nested list (each "column") is strict. So while each nested list in the input can be infinite, the parent List must not be, or trying to realize the first element in the output will cause an infinite loop.

Examples:

# First let's create some infinite lists
list1 = Immutable.iterate(1, &:next)
list2 = Immutable.iterate(2) { |n| n * 2 }
list3 = Immutable.iterate(3) { |n| n * 3 }

# Now we transpose our 3 infinite "rows" into an infinite series of 3-element "columns"
Immutable::List[list1, list2, list3].transpose.take(4)
# => Immutable::List[
#      Immutable::List[1, 2, 3],
#      Immutable::List[2, 4, 9],
#      Immutable::List[3, 8, 27],
#      Immutable::List[4, 16, 81]]

Returns:



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

def transpose
  return EmptyList if empty?
  LazyList.new do
    next EmptyList if any?(&:empty?)
    heads, tails = EmptyList, EmptyList
    reverse_each { |list| heads, tails = heads.cons(list.head), tails.cons(list.tail) }
    Cons.new(heads, tails.transpose)
  end
end

#union(other, items = ::Set.new) ⇒ List Also known as: |

Return a List with all the elements from both this list and other, with all duplicates removed.

Examples:

Immutable::List[1, 2].union(Immutable::List[2, 3]) # => Immutable::List[1, 2, 3]

Parameters:

  • other (List) —

    The list to merge with

Returns:



636
637
638
639
640
641
642
 
# File 'lib/immutable/list.rb', line 636

def union(other, items = ::Set.new)
  LazyList.new do
    next other._uniq(items) if empty?
    next tail.union(other, items) if items.include?(head)
    Cons.new(head, tail.union(other, items.add(head)))
  end
end

#uniq(&block) ⇒ List

Return a List with the same items, but all duplicates removed. Use #hash and #eql? to determine which items are duplicates.

Examples:

Immutable::List[:a, :b, :a, :c, :b].uniq      # => Immutable::List[:a, :b, :c]
Immutable::List["a", "A", "b"].uniq(&:upcase) # => Immutable::List["a", "b"]

Returns:



602
603
604
 
# File 'lib/immutable/list.rb', line 602

def uniq(&block)
  _uniq(::Set.new, &block)
end

#zip(others) ⇒ List

Combine two lists by "zipping" them together. The corresponding elements from this List and each of others (that is, the elements with the same indices) will be gathered into lists.

If others contains fewer elements than this list, nil will be used for padding.

Examples:

Immutable::List["A", "B", "C"].zip(Immutable::List[1, 2, 3])
# => Immutable::List[Immutable::List["A", 1], Immutable::List["B", 2], Immutable::List["C", 3]]

Parameters:

  • others (List) —

    The list to zip together with this one

Returns:



409
410
411
412
413
414
 
# File 'lib/immutable/list.rb', line 409

def zip(others)
  LazyList.new do
    next self if empty? && others.empty?
    Cons.new(Cons.new(head, Cons.new(others.head)), tail.zip(others.tail))
  end
end