Higher order functions in ruby

higher-order-functions.rb

list = (1..10).to_a

# a little monkey patching first so we have the rest method for array
class Array
  # list with zero or more elements
  # [].rest => []
  # [1].rest => []
  # [1,2,3].rest => [2,3]
  def rest
    _,*rest = *self
    rest
  end
end

# we define 3 functions
def sum_squares(list)
  if list.empty?
    0
  else
    list.first**2 + sum_squares(list.rest)
  end
end

def sum_cubes(list)
  if list.empty?
    0
  else
    list.first**3 + sum_cubes(list.rest)
  end
end

# pi aproximation
def sum_pi(list)
  if list.empty?
    0
  else
    n = list.first
    8.0 / ((4*n-3) * (4*n-1)) + sum_pi(list.rest)
  end
end

sum_squares(list)
sum_cubes(list)
sum_pi(list)

# there is a pattern in this functions!
#
# introducing
# higher order functions

def sum(term,list)
  if list.empty?
    0
  else
    term[list.first] + sum(term,list.rest)
  end
end

square = lambda { |x| x*x }
cube = lambda { |x| x*x*x }
pi_term = lambda { |x| 8.0 / ((4*x-3) * (4*x-1)) }

sum_squares(list) == sum(square,list)
sum_cubes(list) == sum(cube,list)
sum_pi(list) == sum(pi_term,list)

# what if don't always want to sum the terms?
# from http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.3
def accumulate(operation, term, initial, list)
  if list.empty?
    initial
  else
    operation[term[list.first],
                accumulate(operation, term, initial, list.rest)]
  end
end

sum = lambda { |x,y| x + y }
subst = lambda { |x,y| x - y }
mult = lambda { |x,y| x * y }
div = lambda { |x,y| x / y.to_f }

sum_squares(list) == accumulate(sum,square,0,list)
accumulate(subst,cube,1,list)
accumulate(div,square,1,list)
accumulate(mult, square, 1, list)

# what else can we do with this new function we created

# we can create the map function passing the correct functions as parameters
def map(fn, list)
  accumulate(
    lambda { |x,y| [fn[x]] + y },
    lambda { |x| x },
    [],
    list
  )
end

identity = lambda { |x| x }
map(identity, list) == list.map(&identity)
map(square, list) == list.map(&square)

# or we can get the lenght of a list
def length(list)
  accumulate(
    lambda { |x,y| 1 + y },
    lambda { |x| x },
    0,
    list
  )
end

length(list) == list.length