func_list_specs.rb

require "../list"
require "spec"

describe "Create a FuncList" do

  # Called before each example.
  before(:each) do
    @subject = FuncList.new
  end

  # Called after each example.
  after(:each) do
    # Do nothing
  end

  it "should create a FuncList" do
    @subject.is_a? FuncList
  end
  
  it "should create an empty FuncList" do
    @subject.is_empty?
  end
  
end

describe "Create a FuncList with FuncList::cons" do

  # Called before each example.
  before(:each) do
    @value1 = OpenStruct.new
    @value1.children = [1,2,3,4]
    
    @value2 = OpenStruct.new
    @value2.children = [5,6,7,8]

    @subject = FuncList::cons(@value1, FuncList::cons(@value2, FuncList::empty))
  end

  # Called after each example.
  after(:each) do
    # Do nothing
  end

  it "should have a head value of @value1" do
    @subject.head.should == @value1
  end
  
  it "should have a tail value of a FuncList containing a head of @value2 and a tail of an empty FuncList" do
    @subject.tail.head.should == @value2
    @subject.tail.tail.is_a? FuncList
    @subject.tail.tail.is_empty?
  end
  
end

describe "Summing a FuncList of integers" do

  before(:each) do    
    @subject = FuncList::cons(1, FuncList::cons(2, FuncList::cons(3, FuncList::cons(4, FuncList::cons(5, FuncList::empty)))))
  end
  
  after(:each) do
    # Do nothing
  end
  
  it "should sum the numbers" do
    result = sum_list( @subject )
    result.should == 15
  end
  
  private
  
  def sum_list( numbers )
    numbers.is_empty? ? 0 : numbers.head + sum_list( numbers.tail )
  end

end

describe "Mapping a function to add two to each number in a FuncList" do

  before(:each) do    
    @subject = FuncList::cons(1, FuncList::cons(2, FuncList::cons(3, FuncList::cons(4, FuncList::cons(5, FuncList::empty)))))
  end
  
  after(:each) do
    # Do nothing
  end
  
  it "should add two to the head" do
    result = @subject.map { |x| x+2 }
    result.head.should == 3
  end
  
  it "should add two to the head of the tail" do
    result = @subject.map { |x| x+2 }
    result.tail.head.should == 4
  end

end

describe "Filtering a FuncList for numbers divisible by 2" do
  
  before(:each) do    
    @subject = FuncList::cons(1, FuncList::cons(2, FuncList::cons(3, FuncList::cons(4, FuncList::cons(5, FuncList::empty)))))
  end
  
  after(:each) do
    # Do nothing
  end
  
  it "should filter 2 to the head" do
    result = @subject.filter { |x| x%2 == 0 }
    result.head.should == 2
  end
  
  it "should filter 4 to head of the tail" do
    result = @subject.filter { |x| x%2 == 0 }
    result.tail.head.should == 4
  end
  
end

describe "Folding a range of 1..5" do
  
  before(:each) do    
    @subject = FuncList::cons(1, FuncList::cons(2, FuncList::cons(3, FuncList::cons(4, FuncList::cons(5, FuncList::empty)))))
  end
  
  after(:each) do
    # Do nothing
  end
  
  it "should return 120 when the seed is 1" do
    result = @subject.fold( 1, Proc.new { |x, y| x * y } )
    result.should == 120
  end
  
  it "should return 600 when the seed is 5" do
    result = @subject.fold( 5, Proc.new{ |x, y| x * y } )
    result.should == 600
  end

end

list.rb

module List

  def bind( &block )
    # Map then flatten (this is, after all, called flatMap in Scala for a reason).
    # Unfortunately, the Array#flatten flattens all levels and we just want the first level flattened,
    # so we have to use inject to get the desired flattening.
    map( &block ).inject( [] ) { |combined, arr| combined + arr }
  end
  
  def filter( &block )
    filtered = []
    self.each { |el| filtered << el if block.call(el) }
    filtered
  end
  
  def fold( init, &block )
    temp = init
    self.each { |el| block.call( el, temp ) }
    temp
  end

end

class Array
  include List
end

class FuncList
  include Enumerable
  
  attr_reader :head
  attr_reader :tail

  def initialize( head = nil, tail = [] )
    @head = head
    @tail = tail
  end
  
  def FuncList::empty
    new
  end
  
  def FuncList::cons( head, tail )
    new( head, tail )
  end
  
  def bind( &block )
    # Map then flatten (this is, after all, called flatMap in Scala for a reason).
    map( &block ) # Need to define a flatten method that pulls up the FuncLists within the FuncList by one level.
  end
  
  def map( &block )
    head = block.call( @head )
    tail = @tail.is_empty? ? @tail : @tail.map( &block )
    FuncList::cons( head, tail )
  end
  
  def filter( &block )
    if (is_empty?)
      self
    else
      tail = @tail.filter( &block )
      block.call( @head ) ? FuncList::cons(@head, tail) : tail
    end
  end
  
  def fold( init, aggregator )
    if (is_empty?)
      init
    else
      aggregator.call( @tail.fold( init, aggregator ), @head )
    end
  end
  
  def is_empty?
    head == nil && tail == []
  end
  
end

list_specs.rb

require "../list"
require "spec"

describe "Use a list monad" do

  # Called before each example.
  before(:each) do
    value1 = OpenStruct.new
    value1.children = [1,2,3,4]
    
    value2 = OpenStruct.new
    value2.children = [5,6,7,8]
    
    @subject = [ value1, value2 ]
  end

  # Called after each example.
  after(:each) do
    # Do nothing
  end

  it "creates an Array monad" do
    #To change this template use File | Settings | File Templates.
    @subject.is_a? Array
  end

  it "should have a property children with the first child having a value of 1" do
    @subject.first.children.first.should == 1
    @subject.first.children.length.should == 4
  end

  it "should return a flattened array of all children" do
    result = @subject.bind { |i| i.children }
    result.first.should == 1
    result.length.should == 8
  end
end

describe "Test monad rules" do

  # monad rules taken from http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/01identity
  # and http://james-iry.blogspot.com/2007_10_01_archive.html
  
  it "should return the same values for map and bind, passing monad rule 0" do
    f = Proc.new { |x| x*2 }
    m = [5]
    m.map( &f ).first.should == m.bind { |x| [ f[x] ] }.first
  end

  it "should have the same effect as calling the block directly, passing monad rule 1" do
    f = Proc.new { |y| [y.to_s] }
    x = 1
    [x].bind { |y| f[y] }.first.should == f[x].first
  end

  it "should return the same value as the original, wrapped up again, passing monad rule 2" do
    x = [1]
    x.bind { |y| [y] }.first.should == x.first
  end
  
  it "should return equivalent results when calling nested blocks or calling them sequentially, passing monad rule 3" do
    f = Proc.new { |x| [x*2] }
    g = Proc.new { |x| [x+1] }
    m = [3]
    n = [3]
    n.bind { |x| f[x].bind { |y| g[y] } }.first.should == m.bind { |x| f[x] }.bind { |x| g[x] }.first
  end

end