November 27, 2015 by Daniel P. Clark

Iterative Evaluation

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. [1][2][3]

-Wikipedia

  1. Gatcomb, Joshua. “Understanding and Using Iterators”. Perl.com. Archived fromthe original on 2005-06-16. Retrieved 2012-08-08. A user-defined iterator usually takes the form of a code reference that, when executed, calculates the next item in a list and returns it. When the iterator reaches the end of the list, it returns an agreed-upon value.
  2. Watt, Stephen M. “A Technique for Generic Iteration and Its Optimization” (PDF). The University of Western Ontario, Department of Computer Science. Archived from the original (PDF) on 2006-09-16. Retrieved 2012-08-08. Iterators were introduced as constructs to allow looping over abstract data structures without revealing their internal representation.
  3. Alex Allain. “STL Iterators”. Cprogramming.com – Your resource for C and C++. Retrieved 2012-08-08. You can think of an iterator as pointing to an item that is part of a larger container of items.

In Ruby there are many ways to iterate over a collection of values and work with what we’re given.

3.times do |i|
  puts i
end
#0
#1
#2
# => 3

(0..3).each do |i|
  puts i
end
#0
#1
#2
#3
# => 0..3

x = 0
(puts x; x+=1) until x > 3
#0
#1
#2
#3
# => nil

And this barely scratches the surface of ways to iterate.  The way Ruby does iterators is with Enumerator instances.

3.times.class
#Enumerator
(0..3).each.class
#Enumerator
[].map.class
#Enumerator

The way Enumerators work in Ruby are hard to grasp at first if you haven’t had experience with them before.  Let’s make and use a “Hello World” Enumerator.

hw = Enumerator.new do |y|
  y << "Hello World"
end
# => #<Enumerator: #<Enumerator::Generator:0x00000000edc6a0>:each>

hw.each do |value|
  puts value
end
#Hello World
# => #<Enumerator::Yielder:0x00000000eb44e8>

It seems rather backwards in how it works.  But once you realize what’s happening it will make more sense.  What you write after the each method is a block that gets pass into Enumerator where the y is, and “Hello World” is the parameter then passed in to that block.  If you understand what procs are then it may help you to know that in Ruby blocks are procs and they can be passed around.  Let me demonstrate.  The code above behaves something like this.

# Our Proc to pass
printer = ->value{ puts value }

# instead of the block we'll hand it the Proc
hw.each &printer
#Hello World
# => #<Enumerator::Yielder:0x00000000e17058>

The each method handed in the block, or proc, of code into the Enumerator to be evaluated with the current value. So the above Enumerator block behaves like the following.

# y << "Hello World"
printer.call("Hello World")

Now to clear things up the Enumerator normally handles more than just one object in a list of things it iterates over.  What’s happening is there is a loop running in the Enumerator and it pulls in the block/proc each time the yielder is called.  So when you write an each block the each itself is not the loop that is running, the loop is inside the Enumerator and the each is just passing in the block of code to run on each value.

count_down_enum = Enumerator.new do |y|
  y << 3
  y << 2
  y << 1
  y << 0
end
# => #<Enumerator: #<Enumerator::Generator:0x00000000cd5a28>:each>

count_down_enum.each &printer
#3
#2
#1
#0
# => #<Enumerator::Yielder:0x00000000b08128>

Remember in this case each time you see y << it’s just like printer.call since printer was handed into the Enumerator by each.  Now lets put some logic into the Enumerator with a basic iterator inside.

evens_from_ten_to_zero = Enumerator.new do |y|
  10.downto(0) do |number|
    y << number if number.even?
  end
end
# => #<Enumerator: #<Enumerator::Generator:0x00000000ad3568>:each>

evens_from_ten_to_zero.each &printer
#10
#8
#6
#4
#2
#0
# => 10

Yes.  I did just use an Enumerator inside an Enumerator.  This is perfectly fine to do and is expected if you want to implement more useful results in a Lazy way; as in Lazy Enumeration or Lazy Iteration.  Try and wrap your head around this one.

im_lazy = Enumerator.new do |y|
  y << "As you wish"
  y << "Feel free to take your time"
  y << "I've got all day"
  y << "I'll be going to sleep now"
  y << "ZZZzzz..."
end
# => #<Enumerator: #<Enumerator::Generator:0x00000001267798>:each>

im_lazy.next
# => "As you wish"

2 + 2
# => 4

im_lazy.next
# => "Feel free to take your time"

puts :some_other_work
#some_other_work
# => nil

im_lazy.next
# => "I've got all day"

Lazy Enumerators allow you to partially process some work and not waste extra CPU cycles.  If you have to do some complicated calculations and it could have infinite results this is where you really want lazy evaluation.

evens = (0..Float::INFINITY).lazy.select(&:even?)
# => #<Enumerator::Lazy: #<Enumerator::Lazy: 0..Infinity>:select>

evens.next
# => 0
evens.next
# => 2
evens.next
# => 4

One example of where this is necessary is this code kata I made on CodeWars.com Moving Slice Enumerator.  I found people trying to implement it by creating an Array of all the result slices and then calling to_enum on their end result.  Since this didn’t meat the challenge requirement of handling any string of a greater size I went ahead and added a 18 million character string.  The computer can’t build an Array of every slice of a string that long because it runs out of memory.  So this is one case where it has to be evaluated lazily.

Functional Forward Evaluation

Now one of the challenges I created on CodeWars.com is to write some code to figure out if you have a “set” in the card game Tonk.  Now I’ve had many refactorings of my own on the game I’m designing myself and how one might implement determining  a set.  Now ideally we would solve this with the minimal amount of code.

Now to determine a cards value from one compared to another we need to implement the <=> method and include Comparable.  This is the method Ruby uses to sort objects with.

class Card
  include Comparable
  def initialize(face)
    @ranks = "A23456789TJQK"
    @face = face
  end

  def rank
    @face[0]
  end

  def <=>(other)
    @ranks.index(self.rank) <=> @ranks.index(other.rank)
  end
end

Card.new("8s") > Card.new("2s")
# => true

Now to figure out if we have a straight we need to know that the cards are sequential.  Each card should be just 1 position different than the next.  So we can open up our Card class and add a method :sequential?

class Card
  def sequential?(other)
    (@ranks.index(self.rank) - @ranks.index(other.rank)).abs == 1
  end
end

Card.new("8s").sequential? Card.new("2s")
# => false 
Card.new("8s").sequential? Card.new("7s")
# => true 

Now it would be really nice if we could compare 5 cards in a row by doing something like cards.inject(:sequential?).  But inject uses an accumulative result and after the first evaluation the method :sequential? returns either true or false and as inject continues, it tries to call :sequential? on the truthy result and raises a “method not found” error.  So we need to have a method like :sequential? that doesn’t return true, but instead returns an Object we can continue evaluating with (continue calling the same method).  What might that look like?

# returns other if true
def ordered?(other)
  self.sequential?(other) ? other : nil
end

So now as long as it’s true that the cards are sequential we will step through them one by one because each true result returns the next card in the progression.  So in the case where we check Ace of Hearts and the Two of Hearts it returns the Two of Hearts.  Next it runs (injects) the same method on that result (the Two of Hearts) and tests the next card which may be the Three of Hearts.  But we have a problem, as soon as we get a false evaluation it returns nil.  And the iteration will then want to call :ordered? on nil and we again get a no method error.

At this point we know if the error is raised then we do not have a straight and so we can simply implement rescue and have a working solution.  But that feels very hacky to use an Exception catch as a determiner.  A rookie move would be to implement a monkey patch of the method :ordered? on NilClass.

An Object Oriented way to get by this nil scenario is to create a Null Object Pattern; a DuckType for a nil result on the Card Object.  Basically we need an Object that will respond to the same methods that Card does, but we don’t need it to know anything.  So let’s re-implement the :ordered? function to return or DuckType of NullCard.  I’m going to implement the NullCard object using the Identity Function pattern.  Any method you call on it (that’s not defined on Object) will return self.

class Card
  # returns other if true
  def ordered?(other)
    self.sequential?(other) ? other : NullCard.new
  end

  class NullCard
    def method_missing(m,*a,&b)
      self
    end
  end
end

So now once we get a false evaluation in the :ordered? method it returns an instance of NullCard.  And whenever the :ordered? method is called on the NullCard instance it no longers raises an error but returns itself.  So now the inject method will work successfully over the entire Array of cards and if it is not a straight we will have a NullCard as the result of Inject.  If it is a straight we will have a valid card.  Now we can implement the straight evaluation method.

def straight(cards)
  !(cards.sort.inject(:ordered?).is_a? NullCard)
end

We want it to answer true whenever the result is not a NullCard.  So now we have a design pattern to implement ever possible check between cards by putting an individual check method on the card that will return the “other” card to continue the progression.

But wait a minute.  If the inject method gets a NullCard instance on the first thing it checks, then it wastes many iterations by continuing through the entire Array of cards.  Wouldn’t it be nice to have inject work like a lazy enumerator?  This is the perfect situation for using Ruby’s Refinements.  We want the inject behavior, but we would like to stop it just after the class type has changed.  Here’s the refinement.

module ClassyInject
  refine Array do
    def inject(m)
      result, *array = self.dup
      stop_iteration = false

      loop do
        break if array.empty?
        other = array.shift
        stop_iteration = result.class != other.class

        result = result.send(m, other)
        break if stop_iteration
      end
      result
    end
  end
end

In the above implementation we use a stop_iteration flag to catch when the class changes, but still allow the result to be changed into the NullCard class before breaking out.

Now all we have to do is call using ClassyInject before our straight evaluation and it will refine inject only within that lexical scope.  Inject will not be effected anywhere else in the program because we used a refinement to keep it in just one spot.  And we improved performance by ending the iteration as soon as we have what we need.

using ClassyInject

def straight(cards)
  !(cards.sort.inject(:ordered?).is_a? NullCard)
end

This is a very functional, simplistic, and performant way to evaluate any scenario.  Each step along the way we don’t need to have any history of what has happened or know what lies ahead.  At any one point it’s a simple evaluation between two objects.

If you would like to see this used in practice for different kinds of Card set evaluation check out my ruby gem cards_lib.  Here is my set evaluator file cards_lib/is_set.rb

Note: You may create an alternative method name, with the same code, rather than a refinement on inject which can return false as soon as the class changes.  Then you won’t need to have the .is_a? NullCard check and you won’t need to use the Null Object Pattern either.  But I wanted to demonstrate a good example for iteration and making a more efficient inject method.

Summary

I learned how Enumerators work by coming across a need for it in one of my CodeWars kata challenges.  Having lazy evaluation is by far one of the best methods of getting stuff done.  And writing things in a functional way where you don’t have to build up any state has many huge advantages in software design (eg: multi-threading, recursion, and simplicity).  The Rust language has all of their iterators as lazy iterators.  In Rust the only requirement for implementing an iterator is defining the next method.  They give you all the other goodies on top of that one method.

Learn and use lazy evaluation with iterators/enumerators and you will have a powerful advantage moving forward in software development.

As always I hope you’ve enjoyed this!  Please comment, share, subscribe to my RSS Feed, and follow me on twitter @6ftdan!

God Bless!
-Daniel P. Clark

Image by Marcy Leigh via the Creative Commons Attribution-NonCommercial-NoDerivs 2.0 Generic License

#enumerator#evaluation#iterator#lazy#patterns#ruby

Leave a Reply

Your email address will not be published / Required fields are marked *