Module: Immutable::List
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
-
.[](*items) ⇒ List
Create a new ‘List` populated with the given items.
-
.empty ⇒ List
Return an empty ‘List`.
-
.from_enum(items) ⇒ Object
This method exists distinct from ‘.[]` since it is ~30% faster than splatting the argument.
Instance Method Summary collapse
-
#<<(item) ⇒ List
Create a new ‘List` with `item` added at the end.
-
#add(item) ⇒ List
(also: #cons)
Create a new ‘List` with `item` added at the front.
-
#append(other) ⇒ List
(also: #concat, #+)
Return a ‘List` with all items from this `List`, followed by all items from `other`.
-
#at(index) ⇒ Object
Retrieve the item at ‘index`.
-
#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.
-
#cached_size? ⇒ Integer
Return ‘true` if the size of this list can be obtained in constant time (without traversing the list).
-
#chunk(number) ⇒ List
Split the items in this list in groups of ‘number`.
-
#clear ⇒ List
Return an empty ‘List`.
-
#combination(n) ⇒ List
Return a ‘List` of all combinations of length `n` of items from this `List`.
-
#cycle ⇒ List
Concatenate an infinite series of copies of this ‘List` together into a new `List`.
-
#delete(obj) ⇒ List
Return a ‘List` with all elements equal to `obj` removed.
-
#delete_at(index) ⇒ List
Return a ‘List` containing the same items, minus the one at `index`.
-
#drop(number) ⇒ List
Return a ‘List` containing all items after the first `number` items from this `List`.
-
#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`.
-
#dup ⇒ List
(also: #clone)
Return ‘self`.
-
#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.
-
#each_chunk(number) {|list| ... } ⇒ self, Enumerator
(also: #each_slice)
Split the items in this list in groups of ‘number`, and yield each group to the block (as a `List`).
-
#eql?(other) ⇒ Boolean
Return true if ‘other` has the same type and contents as this `Hash`.
-
#fill(obj, index = 0, length = nil) ⇒ List
Replace a range of indexes with the given object.
-
#flat_map(&block) ⇒ List
Return a ‘List` which is realized by transforming each item into a `List`, and flattening the resulting lists.
-
#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.
-
#group_by {|item| ... } ⇒ Hash
(also: #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.
-
#hash ⇒ Integer
See ‘Object#hash`.
-
#indices(object = Undefined, i = 0, &block) ⇒ List
Return a ‘List` of indices of matching objects.
-
#init ⇒ List
Return a ‘List` with all elements except the last one.
-
#inits ⇒ List
Return a ‘List` of all prefixes of this list.
-
#insert(index, *items) ⇒ List
Return a new ‘List` with the given items inserted before the item at `index`.
-
#inspect ⇒ String
Return the contents of this ‘List` as a programmer-readable `String`.
-
#intersperse(sep) ⇒ List
Return a new ‘List` with `sep` inserted between each of the existing elements.
-
#last ⇒ Object
Return the last item in this list.
-
#map {|item| ... } ⇒ List, Enumerator
(also: #collect)
Return a ‘List` in which each element is derived from the corresponding element in this `List`, transformed through the given block.
-
#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.
-
#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.
-
#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.
-
#permutation(length = size) {|list| ... } ⇒ self, Enumerator
Yields all permutations of length ‘n` of the items in the list, and then returns `self`.
-
#pop ⇒ List
Return a ‘List` containing all but the last item from this `List`.
-
#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.
- #respond_to?(name, include_private = false) ⇒ Boolean
-
#reverse ⇒ List
Return a ‘List` with the same items, but in reverse order.
-
#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.
-
#sample ⇒ Object
Return a randomly chosen element from this list.
-
#select {|item| ... } ⇒ List
(also: #find_all, #keep_if)
Return a ‘List` which contains all the items for which the given block returns true.
-
#size ⇒ Integer
(also: #length)
Return the number of items in this ‘List`.
-
#slice(arg, length = (missing_length = true)) ⇒ Object
(also: #[])
Return specific objects from the ‘List`.
-
#sort(&comparator) ⇒ List
Return a new ‘List` with the same items, but sorted.
-
#sort_by {|element| ... } ⇒ List
Return a new ‘List` with the same items, but sorted.
-
#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.
-
#split_at(number) ⇒ Array
Return two ‘List`s, one of the first `number` items, and another with the remaining.
-
#subsequences {|sublist| ... } ⇒ self
Yield every non-empty sublist to the given block.
-
#tails ⇒ List
Return a ‘List` of all suffixes of this list.
-
#take(number) ⇒ List
Return a ‘List` containing the first `number` items from this `List`.
-
#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`.
-
#to_list ⇒ List
Return ‘self`.
-
#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.
-
#union(other, items = ::Set.new) ⇒ List
(also: #|)
Return a ‘List` with all the elements from both this list and `other`, with all duplicates removed.
-
#uniq(&block) ⇒ List
Return a ‘List` with the same items, but all duplicates removed.
-
#zip(others) ⇒ List
Combine two lists by “zipping” them together.
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.
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.
132 133 134 |
# File 'lib/immutable/list.rb', line 132 def self.[](*items) from_enum(items) end |
.empty ⇒ List
Return an empty ‘List`.
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.
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.
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`.
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`.
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.
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).
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.
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.
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`.
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.
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.
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.
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`.
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`.
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.
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`.
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`.
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`.
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.
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.
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.
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.
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`
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.
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.
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.
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`.
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`.
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.
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.
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`.
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.
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`.
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.
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.
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`.
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
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.
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.
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.
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.
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`.
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.
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.
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 (`#<=>`).
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.
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.
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.)
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.
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`.
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`.
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`.
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.
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.
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.
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.
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 |