Module: Hamster::List

Includes:
Enumerable
Included in:
EmptyList
Defined in:
lib/hamster/list.rb

Overview

A List can be constructed with Hamster.list or 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 #cons 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, #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 (private)


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

def method_missing(name, *args, &block)
  if name.to_s.match(CADR)
    # Perform compositions of car and cdr operations. 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.
    # The order in which the 'a's and 'd's appear is the inverse of the order in which
    # the corresponding operations are performed.
    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 = Hamster::List[:a, :b, :c]
# => Hamster::List[:a, :b, :c]

Returns:


144
145
146
# File 'lib/hamster/list.rb', line 144

def self.[](*items)
  items.to_list
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:

Hamster.list(:a, :b) << :c
# => Hamster::List[:a, :b, :c]

Parameters:

  • item (Object)

    The item to add

Returns:


186
187
188
# File 'lib/hamster/list.rb', line 186

def <<(item)
  append(Hamster.list(item))
end

#listObject #listObject #listObject Also known as: slice

Element reference. Return the item at a specific index, or a specified, contiguous range of items (as a new list).

Overloads:

  • #listObject

    Return the item at index.

    Parameters:

    • index (Integer)

      The index to retrieve.

  • #listObject

    Return a sublist starting at index start and continuing for length elements.

    Parameters:

    • start (Integer)

      The index to start retrieving items from.

    • length (Integer)

      The number of items to retrieve.

  • #listObject

    Return a sublist specified by the given range of indices.

    Parameters:

    • range (Range)

      The range of indices to retrieve.

Returns:

  • (Object)

731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
# File 'lib/hamster/list.rb', line 731

def [](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

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

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

Examples:

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

Parameters:

  • other (List)

    The list to add onto the end of this one

Returns:


353
354
355
356
357
358
# File 'lib/hamster/list.rb', line 353

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)

705
706
707
708
709
710
711
712
713
714
# File 'lib/hamster/list.rb', line 705

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(&block) ⇒ Array

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

Examples:

Hamster.list(1, 3, 4, 2, 5).break { |x| x > 3 }
# => [Hamster::List[1, 3], Hamster::List[4, 2, 5]]

Returns:

  • (Array)

496
497
498
499
# File 'lib/hamster/list.rb', line 496

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)

1090
1091
1092
# File 'lib/hamster/list.rb', line 1090

def cached_size?
  false
end

#chunk(number) ⇒ List

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

Examples:

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

Returns:


654
655
656
657
658
659
660
# File 'lib/hamster/list.rb', line 654

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

#clearList

Return an empty List.

Returns:


503
504
505
# File 'lib/hamster/list.rb', line 503

def clear
  EmptyList
end

#combination(n) ⇒ List

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

Examples:

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

Returns:


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

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

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

Create a new List with item added at the front.

Examples:

Hamster.list(:b, :c).cons(:a)
# => Hamster::List[:a, :b, :c]

Parameters:

  • item (Object)

    The item to add

Returns:


172
173
174
# File 'lib/hamster/list.rb', line 172

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

#cycleList

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

Examples:

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

Returns:


432
433
434
435
436
437
# File 'lib/hamster/list.rb', line 432

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

#delete(obj) ⇒ List

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

Examples:

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

Parameters:

  • obj (Object)

    The object to remove.

Returns:


875
876
877
878
879
880
# File 'lib/hamster/list.rb', line 875

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 lazy list containing the same items, minus the one at index. If index is negative, it counts back from the end of the list.

Examples:

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

Parameters:

  • index (Integer)

    The index of the item to remove

Returns:


891
892
893
894
895
896
897
898
899
900
901
# File 'lib/hamster/list.rb', line 891

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 lazy list containing all items after the first number items from this List.

Examples:

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

Parameters:

  • number (Integer)

    The number of items to skip over

Returns:


333
334
335
336
337
338
339
340
341
342
# File 'lib/hamster/list.rb', line 333

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

#drop_while(&block) ⇒ List, Enumerator

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

Examples:

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

Returns:

  • (List, Enumerator)

284
285
286
287
288
289
290
291
# File 'lib/hamster/list.rb', line 284

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

#dupList Also known as: clone

Return self.

Returns:


1047
1048
1049
# File 'lib/hamster/list.rb', line 1047

def dup
  self
end

#eachself

Call the given block once for each item in the list, passing each item from first to last successively to the block.

Returns:

  • (self)

194
195
196
197
198
199
200
201
# File 'lib/hamster/list.rb', line 194

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

#each_chunk(number, &block) ⇒ self 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).

Returns:

  • (self)

665
666
667
668
669
# File 'lib/hamster/list.rb', line 665

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)

1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
# File 'lib/hamster/list.rb', line 1026

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(obj) ⇒ List #fill(obj, start) ⇒ List #fill(obj, start, length) ⇒ List

Replace a range of indexes with the given object.

Examples:

list = Hamster.list("a", "b", "c", "d")
list.fill("x")       # => Hamster::List["x", "x", "x", "x"]
list.fill("z", 2)    # => Hamster::List["a", "b", "z", "z"]
list.fill("y", 0, 2) # => Hamster::List["y", "y", "c", "d"]

Overloads:

  • #fill(obj) ⇒ List

    Return a new List of the same size, with every item set to obj.

  • #fill(obj, start) ⇒ List

    Return a new List with all indexes from start to the end of the list set to obj.

  • #fill(obj, start, length) ⇒ List

    Return a new List with length indexes, beginning from start, set to obj.

Returns:


921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
# File 'lib/hamster/list.rb', line 921

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 lazy list which is realized by transforming each item into a List, and flattening the resulting lists.

Examples:

Hamster.list(1, 2, 3).flat_map { |x| Hamster.list(x, 100) }
# => Hamster::List[1, 100, 2, 100, 3, 100]

Returns:


227
228
229
230
231
232
233
234
235
# File 'lib/hamster/list.rb', line 227

def flat_map(&block)
  return enum_for(:flat_map) unless block_given?
  LazyList.new do
    next self if empty?
    head_list = Hamster.list(*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

#flattenList

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:

Hamster.list(Hamster.list(1, 2), Hamster.list(3, 4)).flatten
# => Hamster::List[1, 2, 3, 4]

Returns:


681
682
683
684
685
686
687
# File 'lib/hamster/list.rb', line 681

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(&block) ⇒ 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.

Returns:


694
695
696
# File 'lib/hamster/list.rb', line 694

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

#hashInteger

See Object#hash

Returns:

  • (Integer)

1041
1042
1043
# File 'lib/hamster/list.rb', line 1041

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

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

Return a List of indices where the given object is found, or where the given block returns true.

Overloads:

  • #indices(obj) ⇒ List

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

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

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

Returns:


776
777
778
779
780
781
782
783
784
785
786
787
788
# File 'lib/hamster/list.rb', line 776

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
    while true
      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

#initList

Return a lazy list with all elements except the last one.

Examples:

Hamster.list("a", "b", "c").init # => Hamster::List["a", "b"]

Returns:


579
580
581
582
# File 'lib/hamster/list.rb', line 579

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

#initsList

Return a lazy list of all prefixes of this list.

Examples:

Hamster.list(1,2,3).inits
# => Hamster::List[
#      Hamster::List[1],
#      Hamster::List[1, 2],
#      Hamster::List[1, 2, 3]]

Returns:


619
620
621
622
623
624
# File 'lib/hamster/list.rb', line 619

def inits
  LazyList.new do
    next self if empty?
    Cons.new(Hamster.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:

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

Parameters:

  • index (Integer)

    The index where the new items should go

  • items (Array)

    The items to add

Returns:


854
855
856
857
858
859
860
861
862
863
864
865
# File 'lib/hamster/list.rb', line 854

def insert(index, *items)
  if index == 0
    return items.to_list.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

#inspectString

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)

1063
1064
1065
1066
1067
# File 'lib/hamster/list.rb', line 1063

def inspect
  result = "Hamster::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:

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

Returns:


534
535
536
537
538
539
# File 'lib/hamster/list.rb', line 534

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

#lastObject

Return the last item in this list.

Returns:

  • (Object)

586
587
588
589
590
# File 'lib/hamster/list.rb', line 586

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

#map(&block) ⇒ List Also known as: collect

Return a lazy list in which each element is derived from the corresponding element in this List, transformed through the given block.

Examples:

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

Returns:


210
211
212
213
214
215
216
# File 'lib/hamster/list.rb', line 210

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(&comparator) ⇒ 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. The comparator should take 2 parameters and return 0, 1, or -1 if the first parameter is (respectively) equal to, greater than, or less than the second parameter. Whichever nested list’s #head is determined to be “lowest” according to the comparator will be the first in the merged List.

Examples:

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

Returns:


805
806
807
808
809
810
811
812
813
814
# File 'lib/hamster/list.rb', line 805

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(&transformer) ⇒ 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 = Hamster::List[1, -3, -5]
list_2 = Hamster::List[-2, 4, 6]
Hamster::List[list_1, list_2].merge_by { |x| x.abs }
# => Hamster::List[1, -2, -3, 4, -5, 6]

Returns:


829
830
831
832
833
834
835
836
837
838
# File 'lib/hamster/list.rb', line 829

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(&block) ⇒ List

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

Examples:

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

Returns:


1014
1015
1016
1017
1018
1019
1020
# File 'lib/hamster/list.rb', line 1014

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, &block) ⇒ 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:

Hamster.list(1, 2, 3).permutation.to_a
# => [Hamster::List[1, 2, 3],
#     Hamster::List[2, 1, 3],
#     Hamster::List[2, 3, 1],
#     Hamster::List[1, 3, 2],
#     Hamster::List[3, 1, 2],
#     Hamster::List[3, 2, 1]]

Returns:

  • (self, Enumerator)

959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
# File 'lib/hamster/list.rb', line 959

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

#popList

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

Examples:

Hamster.list("A", "B", "C").pop  # => Hamster::List["A", "B"]

Returns:


315
316
317
318
319
320
321
322
# File 'lib/hamster/list.rb', line 315

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

#reverseList

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

Examples:

Hamster.list("A", "B", "C").reverse  # => Hamster::List["C", "B", "A"]

Returns:


368
369
370
# File 'lib/hamster/list.rb', line 368

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 = Hamster.list("A", "B", "C", "D", "E", "F")
l.rotate(2)   # => Hamster::List["C", "D", "E", "F", "A", "B"]
l.rotate(-1)  # => Hamster::List["F", "A", "B", "C", "D", "E"]

Parameters:

  • count (Integer) (defaults to: 1)

    The number of positions to shift items by

Returns:

Raises:

  • (TypeError)

452
453
454
455
456
457
# File 'lib/hamster/list.rb', line 452

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

#sampleObject

Return a randomly chosen element from this list.

Returns:

  • (Object)

842
843
844
# File 'lib/hamster/list.rb', line 842

def sample
  at(rand(size))
end

#select(&block) ⇒ List Also known as: find_all, keep_if

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

Examples:

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

Returns:


245
246
247
248
249
250
251
252
253
254
255
# File 'lib/hamster/list.rb', line 245

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

#sizeInteger Also known as: length

Return the number of items in this List.

Returns:

  • (Integer)

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

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

#sort(&comparator) ⇒ List

Return a List with the same items, but sorted either in their natural order, or using an optional comparator block. The block must take 2 parameters, and return 0, 1, or -1 if the first one is equal, greater than, or less than the second (respectively).

Returns:


513
514
515
# File 'lib/hamster/list.rb', line 513

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

#sort_by(&transformer) ⇒ List

Return a new List with the same items, but sorted. The sort order will be determined by mapping the items through the given block to obtain sort keys, and then sorting the keys according to their natural sort order.

Returns:


522
523
524
525
# File 'lib/hamster/list.rb', line 522

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

#span(&block) ⇒ Array

Return 2 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:

Hamster.list(4, 3, 5, 2, 1).span { |x| x > 2 }
# => [Hamster::List[4, 3, 5], Hamster::List[2, 1]]

Returns:

  • (Array)

480
481
482
483
484
485
486
# File 'lib/hamster/list.rb', line 480

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 2 Lists, one of the first number items, and another of all the remaining items.

Examples:

Hamster.list("a", "b", "c", "d").split(2)
# => [Hamster::List["a", "b"], Hamster::List["c", "d"]]

Parameters:

  • number (Integer)

    The index at which to split this list

Returns:

  • (Array)

468
469
470
# File 'lib/hamster/list.rb', line 468

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:

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

Yields:

  • (sublist)

    One or more contiguous elements from this list

Returns:

  • (self)

995
996
997
998
999
1000
1001
1002
1003
1004
# File 'lib/hamster/list.rb', line 995

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

#tailsList

Return a lazy list of all suffixes of this list.

Examples:

Hamster.list(1,2,3).tails
# => Hamster::List[
#      Hamster::List[1, 2, 3],
#      Hamster::List[2, 3],
#      Hamster::List[3]]

Returns:


602
603
604
605
606
607
# File 'lib/hamster/list.rb', line 602

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

#take(number) ⇒ List

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

Examples:

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

Parameters:

  • number (Integer)

    The number of items to retain

Returns:


301
302
303
304
305
306
307
# File 'lib/hamster/list.rb', line 301

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(&block) ⇒ List, Enumerator

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

Examples:

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

Returns:

  • (List, Enumerator)

267
268
269
270
271
272
273
274
# File 'lib/hamster/list.rb', line 267

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_listList

Return self.

Returns:


1054
1055
1056
# File 'lib/hamster/list.rb', line 1054

def to_list
  self
end

#transposeList

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 lazy 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 = Hamster.iterate(1, &:next)
list2 = Hamster.iterate(2) { |n| n * 2 }
list3 = Hamster.iterate(3) { |n| n * 3 }

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

Returns:


414
415
416
417
418
419
420
421
422
# File 'lib/hamster/list.rb', line 414

def transpose
  return EmptyList if empty?
  LazyList.new do
    next EmptyList if any? { |list| list.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:

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

Parameters:

  • other (List)

    The list to merge with

Returns:


564
565
566
567
568
569
570
# File 'lib/hamster/list.rb', line 564

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(items = ::Set.new) ⇒ List

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

Examples:

Hamster.list(:a, :b, :a, :c, :b).uniq # => Hamster::List[:a, :b, :c]

Returns:


548
549
550
551
552
553
554
# File 'lib/hamster/list.rb', line 548

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

#zip(others) ⇒ List

Gather the corresponding elements from this List and others (that is, the elements with the same indices) into new 2-element lists. Return a lazy list of these 2-element lists.

Examples:

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

Parameters:

  • others (List)

    The list to zip together with this one

Returns:


383
384
385
386
387
388
# File 'lib/hamster/list.rb', line 383

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