Monads in ruby

monads.rb

module Monad
  # (a -> b) -> (a -> [b])
  def lift(f)
    lambda {|x| unit.call(f.call(x)) }
  end

  # (a -> b) -> (M a -> M b)
  def liftM(f)
    bind(lift(f))
  end
end

module ArrayMonad
  extend Monad
  extend self

  # a -> [a]
  def unit
    lambda {|x| [x] }
  end
    
  # (a -> [a]) -> ([a] -> [a])
  def bind(f)
    lambda {|xs| 
      output = []
      xs.each {|x| f.call(x).each {|y| output << y } } 
      output
    }
  end
end

module WriterMonad
  extend Monad
  extend self

  # (a -> [b, c])
  def unit
    lambda {|a| [a, []] }
  end
  
  # (a -> [b, c]) -> ([a, c] -> [b, c])
  def bind(f)
    lambda {|x|
      a,b = x
      value, log = f.call(a)
      [value, b + log]
    }
  end
end

class Array
  def composed(first_type, *additional_types)
    map {|f| 
      additional_types.inject(first_type.bind(f)) {|f, t| t.liftM(f) }
    }.inject {|f,g| f >> g }
  end

  def unit_composed(*types)
    units = types.map(&:unit).inject {|f, g| f >> g }
    units >> composed(*types)
  end
end

dup = lambda {|x| [x, x] }
filter = lambda {|x| [] }

xf = lambda {|x| [x, [1]] }
yf = lambda {|x| [x + 1, []] }

class Proc
  def >>(g)
    lambda {|values| g.call(call(values)) }
  end
end

plus1 = lambda {|i| i + 1 }

puts [dup, dup, dup].unit_composed(ArrayMonad, WriterMonad).call(3).inspect
puts [yf, yf, yf].unit_composed(WriterMonad, ArrayMonad).call(3).inspect
puts [xf, xf, yf, xf, yf].composed(WriterMonad).call([2, []]).inspect
puts [dup, dup, dup].composed(ArrayMonad).call([2]).inspect