This is a continuation of my posts on
functional collection patterns in Ruby.
When using a language with high order functions, one can abstract out many common patterns on collections. So far I've described Map, Filter, Reduce (also known as foldl, foldr, or inject), Zip, and Flatmap.
ScanLWhen using a pattern such as Reduce, sometimes you want all of the intermediate results of the folding, instead of just the final result. In Haskell, these functions are referred to as "scanl" and "scanr". The r or l on the end specify which way the folding occurs.
For example, the following shows its use:
irb(main):239:0> [1,2,3,4].scanl(0) {|acc, e| acc + e}
=> [1, 3, 6, 10]
To illustrate scanl, I will use the bowling example from "Agile Software Development" by Bob Martin.
Assume that I've already implemented all of the logic except for scoring. The frame are represented using an array, and each frame can have up to three values, reflecting the score that should be added for the frame.
irb(main)> game = BowlingGame.new
irb(main)> [4,3,3,7,4,6,10,9,1,10,10,10,7,3,10,10,10].map {|t| game.throw t}
irb(main)> game
=> #<BowlingGame:0xb7c85c78
@first_throw=true,
@frames=
[[4, 3, nil], [3, 7, 4], [4, 6, 10],
[10, 9, 1], [9, 1, 10], [10, 10, 10],
[10, 10, 7], [10, 7, 3], [7, 3, 10],
[10, 10, 10]],
@maximum_frames=10,
@continuations=[#<Proc:0xb7c6a7fc@(irb):54>, #<Proc:0xb7c6a7c0@(irb):52>]>
What I want to do is call "to_a" on the game, and get back a multidimensional array that looks like what I would see in a real bowling alley. This can be achieved using scanl and zip.
def score
@frames.scanl(0) {|acc, frame|
acc + frame.score
}
end
The way scanl works is that it takes an initial value and a block. It acts like inject, folding from the left, but instead of returning one scalar value, it returns an array of all of the intermediate scalar values.
irb(main)> game.score
=> [7, 21, 41, 61, 81, 111, 138, 158, 178, 208]
Now that I have the scores, I can zip them up with each frame's corresponding throws
def to_a
(@frames[0..8].map {|x| x.throws} + [@frames[9]]).zip(score)
end
Now, "game.to_a" evaluates to something which could be displayed on a real bowling alley monitor.
[[[4, 3], 7],
[[3, 7], 21],
[[4, 6], 41],
[[10], 61],
[[9, 1], 81],
[[10], 111],
[[10], 138],
[[10], 158],
[[7, 3], 178],
[[10, 10, 10], 208]]
Complete Source Code
module Enumerable
def scanr(initial_value, &block)
as_array = self.to_a
if as_array.empty?
[initial_value]
else
result = as_array[1..-1].scanr(initial_value,&block)
[block.call(as_array[0],result[0])] + result
end
end
def scanl(initial_value, &block)
as_array = self.to_a
if as_array.empty?
[]
else
head = block.call(initial_value, as_array[0])
[head] + as_array[1..-1].scanl(head,&block)
end
end
end
class Array
def strike?
10 == self[0]
end
def spare?
!strike? and 10 == self[0] + if self[1] then self[1] else 0 end
end
def throws
return [self[0]] if strike?
self[0..1]
end
def score
reject {|x| x.nil?}.inject {|acc,x| acc + x}
end
end
class BowlingGame
def initialize
@frames = []
@first_throw = true
@continuations = []
@maximum_frames = 10
end
def current_frame
@frames[-1]
end
def throw(pins)
add_pins_to_current_frame(pins)
add_pins_to_previous_frames(pins)
remember_to_add_future_pins_to_this_frame
update_first_throw
self
end
def add_pins_to_current_frame(pins)
if @first_throw and @frames.size < @maximum_frames
@frames << [pins,nil,nil]
elsif @frames.size <= @maximum_frames
@frames[-1][1] = pins
end
end
def add_pins_to_previous_frames(pins)
@continuations = @continuations.map {|cont| cont.call(pins)}.select {|x| x.class == Proc}
end
def remember_to_add_future_pins_to_this_frame
cf = current_frame
if cf.strike?
@continuations << Proc.new {|pins|
cf[1] = pins
Proc.new {|pins| cf[2] = pins}
}
elsif cf.spare?
@continuations << Proc.new {|pins| cf[2] = pins}
end
end
def update_first_throw
@first_throw = !current_frame[1].nil? || current_frame.strike?
end
def score
@frames.scanl(0) {|acc, frame|
acc + frame.score
}
end
def to_a
(@frames[0..8].map {|x| x.throws} + [@frames[9]]).zip(score)
end
end
