Problem set 9 (Ruby)

Explanations

Naming a code block

Recall how we pass a block to a function:


def dostuff 
  yield(7)
end

puts dostuff {|x| x + 9}

This code passes the block {|x| x + 9} to the method dostuff which calls the block on 7

Below is an alternative way to accomplish exactly the same thing (try it!). The difference, however, is that the block now is now a parameter with a name code. Note the syntax of the parameter: &code since we are passing the address of the block. Also note that instead of yield I now call a method call on the code that makes it execute with the parameter given to call.


def dostuff(&code) 
  code.call(7)
end

puts dostuff {|x| x + 9}

This style of passing blocks to a function is very important since it allows you to re-pass the code to function calls inside the function that initially gets the code. This enables recursion with a block being passed as a parameter to the recursive call.

Unfortunately, there does not seem to be a way to pass two code blocks to a function. It is possible to pass another parameter as a lambda-procedure. This is covered in the optional material below.

Writing your own class that "implements" Enumerable

Suppose we want to write a class of nested arrays so that we can call methods of Enumerable interface on such arrays. The code below shows the beginning of such an implementation. Your task will be to add more methods to this class.

Enumerable is a module which for the purposes of this problem set is similar to a Java interface: it gives a list of methods that a class supports but does not provide an implementation. Note that Ruby does not mandate that all methods are actually implemented. The initialize method stores whatever is passed to it in the variable @narray. The intended value is an array of arbitrary nesting, as shown in the call to new below. Note that p na just prints the address of the object since no to_s is defined.


class NestedArray 
  include Enumerable # Enumerable is a module, not a class
                     # modules are included, not subclassed
  def initialize obj
    @narray = obj
  end 
end

# testing the new class
na = NestedArray.new([[6,7],[8],[[9, 6]]])
p na
#p na.each {|z| puts (z + z)} # need to define each for this to work

Now we define an each method for the NestedArray. The method is recursive. However, to use recursion, we need to pass the sub-arrays to the recursive call. The private method _each does that, and the public each just calls the private one. In Ruby private and public keywords apply to a group of methods, i.e. all methods defined after "private" and until "public" are private.

Study the code for the recursive call carefully. Note that obj is just a normal array so we can use its each method. Likewise you can use other methods of the sub-arrays in your code so your code would be really not that long.


class NestedArray 
  # defining each for nested arrays 
private
# a private recursive method, iterates over nested arrays
# with the code block in &code
# unfortunately, you can only pass one code parameter
 def _each (obj,&code)
    obj.each do |x| 
      if (x.instance_of? Array) 
        _each(x,&code)
      else 
        code.call(x)
      end
    end
 end
 public 
 # the public each method, calls the recursive one with the 
 # nested arrays storage as the parameter
 def each(&code)
   _each(@narray, &code)
 end    
end

na.each {|y| puts "Here is #{y}"}

Problem set assignment

Your task is to implement the following public methods of the NestedArray class. Consult the description of Enumerable module for methods' behavior.

  1. write to_s method to print all the nested array. Make sure that all the nested elements are printed and the structure of the nesting is displayed.
  2. write find method that returns any one element (in any of the nested arrays) for which the given block is not false. For instance, if I consider the nested array NestedArray.new([[6,7],[8],[[9, 6]]]).find {|y| y > 7} then the method may return 8. Note that returning 9 would not be wrong. If the block is false on all elements, nil is returned.
  3. write any? method that returns true if the block returns a value other than false or nil on at least one element, otherwise it returns false
  4. write map method that returns a new nested array of the same structure with the results of running block once for every element. For instance,
    
    NestedArray.new([[6,7],[8],[[9, 6]]]).map {|y| y * y} 
    
    returns a NestedArray object [[36,49],[64],[[81, 36]]].
  5. write inject method that takes a "seed" and works on all elements according to the definition in the Enumerable module. For instance,
    
    NestedArray.new([[6,7],[8],[[9, 6]]]).inject(1) {|prod, y| prod * y} 
    
    returns the product of all elements: 18144.

Don't worry about default parameters or type mismatches for any of the methods: they need to work on the correct input and are allowed to break on any incorrect data.

You may define any private methods that you find helpful. If you run into any problems with making methods private, you can make your helper methods public without loss of credit, just use _ in front of the name to distinguish "private" methods from public ones.

There are two ways to approach this problem: use the each method above as a sample and just write all the other methods one by one, or write a more general traverse-like method and use it to generate all of the needed methods. The latter approach requires using a lambda rather than a block since we need to pass two functions to traverse (action and combine), but we can pass only one block. The optional material below shows how to create first-class functions using a lambda.

You may use either approach. No extra credit is given for the lambda approach because once you get "traverse" to work, the rest of the methods can be written in 20 minutes, if not less, so you are simplifying the work quite a bit.

For convenience all the code used in this page can be copy/pasted from here.

Optional material: lambda notation and first-class functions

It is possible to define and use first-class functions in Ruby. They are defined using a familiar lambda notation (see below). You can pass as many functions as you want to a function. Note that to call the function, you use call method, just like for a block. Syntactically, however, blocks are different from lambdas and allow you to write more natural code where blocks are used as a "loop" body. You cannot do it with a lambda.

Lambda can be used to pass the "combine" function to a traverse-like general function in NestedArray. Then the "traverse" function can be used to generate all of the methods you are trying to define. If you are using this approach, don't forget about the "seed" parameter to "traverse".


#################### Optional material ##################################
###### may be used to write a traverse-like function in #################
###### Nested Array to write all other methods as calls to traverse #####
 
# creating a function that you can pass to another function
add_two = lambda {|x| x + 2}
p add_two.call(5)

repeat = lambda {|y, z| y.call(y.call(z))}

# functions can now be passed around 
# cannot do it with blocks :-(
def call_two_functions(f1, f2) 
 return f2.call(f1, 5)
end

p call_two_functions(add_two, repeat)

CSci 4651 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.