Module: Immutable::List

Includes:
Enumerable
Included in:
Cons, LazyList, Realizable
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.

Constant Summary collapse

CADR = 
/^c([ad]+)r$/

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 `a`s and `d`s 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

.from_enum(items) ⇒ Object

This method exists distinct from ‘.[]` since it is ~30% faster than splatting the argument.

Marking as private only because it was introduced for an internal refactoring. It could potentially be made public with a good name.



150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/immutable/list.rb', line 150

def self.from_enum(items)
  # use destructive operations to build up a new list, like Common Lisp's NCONC
  # this is a very fast way to build up a linked list
  list = tail = Cons.allocate
  items.each do |item|
    new_node = Cons.allocate
    new_node.instance_variable_set(:@head, item)
    tail.instance_variable_set(:@tail, new_node)
    tail = new_node
  end
  tail.instance_variable_set(:@tail, EmptyList)
  list.tail
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 ‘List`s, 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 ‘List`s 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 ‘List`s, 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

#pretty_print(pp) ⇒ Object

Allows this ‘List` to be printed at the `pry` console, or using `pp` (from the Ruby standard library), in a way which takes the amount of horizontal space on the screen into account, and which indents nested structures to make them easier to read.



1215
1216
1217
1218
1219
1220
 
# File 'lib/immutable/list.rb', line 1215

def pretty_print(pp)
  pp.group(1, 'Immutable::List[', ']') do
    pp.breakable ''
    pp.seplist(self) { |obj| obj.pretty_print(pp) }
  end
end

#respond_to?(name, include_private = false) ⇒ Boolean

Returns:

  • (Boolean) 


1223
1224
1225
 
# File 'lib/immutable/list.rb', line 1223

def respond_to?(name, include_private = false)
  super || !!name.to_s.match(CADR)
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 ‘List`s, 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 ‘List`s, 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