Sunday, September 22, 2013

AngularJS: weird design or brilliant idea?

Ahem, I have always thought the difference between parameters and arguments are there for a reason and I can use arbitrary parameter name for my function. It's probably called local scope. Well, not AngularJS $scope:
window.SomeCtrl = function($scope) { ... }  //works
window.SomeCtrl = function($myScope) { ... } //doesn't work
The reason why the latter doesn't work is because AngularJs pretends to be source code parser:
if (typeof fn == 'function') {
  if (!($inject = fn.$inject)) {
    $inject = [];
    fnText = fn.toString().replace(STRIP_COMMENTS, '');
    argDecl = fnText.match(FN_ARGS);
    forEach(argDecl[1].split(FN_ARG_SPLIT), function(arg){
      arg.replace(FN_ARG, function(all, underscore, name){
        $inject.push(name);
      });
    });
    fn.$inject = $inject;
  }
}
Not that I'm against reflection, but this looks like a super-reflection. Next step in this direction would be to modify source code on the fly and re-eval it.

Friday, September 20, 2013

Algebraic data types (unions) in Ruby

Let's consider a simple tree defined in Haskell as
data Tree a = Empty
          | Node a (Tree a) (Tree a)
Naive Ruby's approach would be defining class Node and assuming node is a leaf when both left and right sub-trees are nil (i. e. nil is representing an empty tree):
class Node
  def initialize(v, left, right)
    @v, @left, @right = v, left, right
  end

  def each(&block)
    @left.each(&block) if @left
    block[@v]
    @right.each(&block) if @right
  end
end
But it doesn't work well. First of all if @left is not a good recursive approach, but more importantly there is no standalone representation of an empty tree. But unions can be represented by using inheritance:
class Tree
  def self.empty
    Empty.new
  end

  def flatten
    vs = []
    each do |v|
      vs << v
    end
    vs
  end
end

class Empty < Tree
  def each
  end

  def append(v)
    Node.new(v, Tree.empty, Tree.empty)
  end
end

class Node < Tree
  def initialize(v, left, right)
    @v, @left, @right = v, left, right
  end

  def each(&block)
    @left.each(&block)
    block[@v]
    @right.each(&block)
  end    

  def append(v)
    if v < @v
      Node.new(@v, @left.append(v), @right)
    elsif v > @v
      Node.new(@v, @left, @right.append(v))
    else
      self
    end
  end
end

Tree.empty.append(1).append(0).append(3).flatten #=> [0, 1, 3]
Now I can add a bunch of methods to the Tree class based on each, e. g. map. I don't want to include Enumerable because that map will return me an array, but what I really want is the same data structure, i. e. Tree.
class Tree

...

  def fmap(&block)
    r = self.class.empty
    each do |v| 
      r = r.append(block[v])
    end
    r
  end
end

p Tree.empty.append(1).append(0).append(3).fmap { |x| - x }.flatten #=> [-3, -1, 0]
Meanwhile the implementation of fmap is based on two methods: self.empty and append, so if I define those methods for any other class I can get fmap for free (I will rename them to fempty and fappend so I don't clash with Ruby names). I have always wondered why map over a Hash returns an Array while it should have returned a Hash:
module Functor
  def fmap(&block)
    r = self.class.fempty
    each do |v| 
      r = r.fappend(block[v])
    end
    r
  end
end

class Hash
  include Functor

  class << self
    alias :fempty :new
  end

  # Not very functional
  def fappend(kv)
    k, v = kv
    self[k] = v
    self
  end
end

{ :a => 1 }.fmap { |k, v| [k, 3] } #=> {:a => 3}
Linked list can be defined in a similar fashion:
class List
  include Functor

  class << self
    alias :fempty :new
  end

  def to_a
    xs = []
    each do |x|
      xs << x
    end
    xs
  end
end

class Empty < List
  def each
  end

  def fappend(v)
    Cons.new(v, List.fempty)
  end
end

class Cons < List
  def initialize(h, t)
    @h, @t = h, t
  end

  def each(&block)
    block[@h]
    @t.each(&block)
  end

  def fappend(v)
    Cons.new(v, self)
  end
end

List.fempty.fappend(1).fappend(2).fmap{ |x| x + 1 }.to_a #=> [2, 3]

Tuesday, May 22, 2012

Point-free and arrows in Ruby

Extending point free functionality I came to a conclusion that using Array as a base for function fanout/composition was not really a good idea. From one side it's concise and convenient, but using "direction" doesn't look right, it can't be easily extended to more complex cases, messing with Array#to_proc would better be avoided, and last but not least instantiating Array object and calling to_proc each time leads to possible performance issue. Besides, there is a syntax which makes same thing almost as concise as an Array, and it's Proc#[], and Proc object doesn't need to be converted when passing as a block. So let's start with fanout/composition:
PComp = 
  lambda do |*xs|
    if xs.empty?
      PId
    else
      ph, *ps = xs.map(&:to_proc)
      lambda do |*ys|
        r = ph[*ys]
        ps.each do |p|
          r = p[r]
        end
        r
      end
    end
  end
  
PSplat =
  lambda do |*xs|
    ps = xs.map(&:to_proc)
    lambda { |*ys| ps.map { |p| p[*ys] } }
  end
So example in my previous post can be rewritten as:
Order.find(...) \
  .map(&PComp[:order_items, 
              :map.with_args(&PComp[:item, :item_group, PSplat[:id, :name]])]) \
  .inject([], &:<<).uniq
Slightly longer, but still looks good and action is obvious here so I don't need to count brackets. Now it also looks quite similar to Haskell arrows. PSplat resembles &&&, only Ruby isn't strong typed so I don't need to limit myself with a fixed number of elements (pair in Haskell). What about *** then? Well, let's call it PZip:
PZip =
  lambda do |*xs|
    ps = xs.map(&:to_proc)
    lambda do |ys| 
      ps.zip(ys).map do |p, e|
        p[e]
      end
    end
  end
How does this help? Let's say I need to find frequencies:
[1,2,2,3,3,3,4,5].group_by(&lambda { |x| x }).map{ |k, v| [k, v.length] }
First of all lambda { |x| x } is used pretty often in point-free style (Haskell's id), why not define it as:
PId = 
  lambda do |x| 
    x
  end
Now I can rewrite frequencies as:
[1,2,2,3,3,3,4,5].group_by(&PId).map(&PZip[PId, :length])
In fact in this particular example PZip acts like Haskell's second, but it's just because I chose this simple case. Now let's say I want to find all orders that match certain criteria:
Order.find(:all).select{ |order| order.customer.has_discount? && order.paid? && order.shipped? }
I can rewrite it as:
Order.find(:all).select(&PComp[PSplat[PComp[:customer, :has_discount?], :paid?, :shipped?], :all?])
or just
Order.find(:all).select(&PAll[PComp[:customer, :has_discount?], :paid?, :shipped?])
if I define additional lambdas (and it will be faster as they use lazy evaluation in all?(&block) and any?(&block)):
PAny =
  lambda do |*xs|
    ps = xs.map(&:to_proc)
    lambda { |*ys| ps.any? { |p| p[*ys] } }
  end

PAll =
  lambda do |*xs|
    ps = xs.map(&:to_proc)
    lambda { |*ys| ps.all? { |p| p[*ys] } }
  end

Friday, November 25, 2011

Symbol#to_proc and point free programming in Ruby

Let's say we have this schema:

class Order < ActiveRecord::Base
  has_many :order_items
end

class OrderItem < ActiveRecord::Base
  belongs_to :item
end

class Item < ActiveRecord::Base
  belongs_to :item_group
end

class ItemGroup < ActiveRecord::Base
end

And what I want to do is to find all item groups for certain orders. Straightforward approach:

Order.find(...).map { |order| 
  order.order_items.map { |order_item| 
    order_item.item.item_group 
  } 
}.flatten.uniq

Let's start from the inner part:

order_items.map { |order_item| order_item.item.item_group }

If I wanted to find items, then it would be much shorter:

order_items.map(&:item)

Could it be easier if I were able to write

order_items.map(&[:item, :item_group])

Certainly it could and all I need to do is to define Array#to_proc:

class Array
  def to_proc
    raise ArgumentError.new("empty collection") if empty?
    psh, *pst = map(&:to_proc)
    lambda do |*args| 
      pst.inject(psh[*args]) { |v, p| p[v] }
    end
  end
end

so my original statement can be rewritten as

Order.find(...).map{ |order| order.order_items.map(&[:item, :item_group] }.flatten.uniq

What about the outer part? To find all items I could use

Order.find(...).map(&[:order_items, :map?])

But how am I going to pass a block? There are two steps involved. First, I want to convert symbol to a lambda, which calls block behind the scene, and I also want my Array#to_proc to take Proc objects. Second step is trivial:

class Array
  def to_proc
    raise ArgumentError.new("empty collection") if empty?
    ps = 
      map do |e|
        case e 
        when Symbol
          e.to_proc
        when Proc
          e
        end
      end
    psh, *pst = ps
    lambda do |*args| 
      pst.inject(psh[*args]) { |v, p| p[v] }
    end
  end
end

And now I want to define Symbol#with_args which is going to call a method with arguments and block:

class Symbol
  def with_args(*args, &block)
    p = lambda { |e| e.__send__(self, *args, &block) }
    lambda { |e| p[e] }
  end
end

So original statement becomes even shorter

Order.find(...).map(&[:order_items, :map.with_args(&[:item, :item_group]).flatten.uniq

So I finally removed all "points", i. e. any mentionigs of block arguments.

Why this is important and what I have actually saved here? Well, Ruby has what I can call "loose" scoping, block arguments don't shadow outer scope, neither Ruby produce any warning about that. In deeply nested statements naming can become a serious issue. Of course, I could create small method for every step with it's own scope, but it doesn't help readability at all.

Now, Ruby has a nice deconstruction of block arguments

[[1,[2,3]], [4,[5,6]]].map { |x, (y, z)| z } # => [3,6]

and I want to prepare data for my view, and in fact I don't need whole item group model, I just need to keep name and id so I can write in my view

%ul
  - item_groups.each do |id, name|
    %li= link_to name, item_group_path(id)

my controller code then becomes

item_groups = Order.....map{ |item_group| [item_group.id, item_group.name] }

Now we have the same "point" again, we have to name item_group to convert it to a pair. If we could only write

...map(&[:id, :name])

but this place is already taken. Well, is it? What if I pass nested array and will change "direction" with each level (I will name previous case as "vertical", and this new way as "horizontal"):

class Array
  def to_proc(horizontal = nil)
    raise ArgumentError.new("empty collection") if empty?
    ps = 
      map do |e|
        case e 
        when Array
          e.to_proc(!horizontal)
        when Symbol
          e.to_proc
        when Proc
          e
        end
      end
    if horizontal
      lambda { |*args| ps.map { |p| p[*args] } }
    else
      psh, *pst = ps
      lambda do |*args| 
        pst.inject(psh[*args]) { |v, p| p[v] }
      end
    end
  end
end

Now we can write

...map(&[[:id, :name]])

Wait a second, now the whole statement can be written differently

Order.find(...).map(&[:order_items, 
                      :map.with_args(&[:item, 
                                       :item_group, 
                                       [:id, :name]])]).flatten(1).uniq

Meanwhile just remembering good old Symbol#to_proc I can rewrite it as

Order.find(...) \
  .map(&[:order_items, 
         :map.with_args(&[:item, :item_group, [:id, :name]])]) \
  .inject([], &:<<).uniq

or even

Order.find(...) \
  .map(&[:order_items, 
         :map.with_args(&[:item, :item_group, [:id, :name]])]) \
  .inject(Set.new, &:+).to_a

which brings us to another point -- can we actually join map and inject into one inject? There is a small problem here. Imagine we want to find sum of squares

[1,2,3].inject(0) { |a, x| a + x ** 2 }

can we write it in point-free style? Something like

[1,2,3].inject(0, &[:**.with_args(2), :+])

This obviously won't work as inject passes a and x, so what is actually getting to ** is a, not x, and then the result of ** is a number, not an array needed for sum. We need to somehow "slice" arguments and apply ** to a second one, but return both of them, and then "splat" an array and call block with more than one argument

[1,2,3].inject(0, &[slice_args(1, &:**.with_args(2)), :splat.with_args(&:+)])

We need to add two more methods:

def slice_args(index = 0, &block)
  lambda do |*args|
    args[index] = block[args[index]]
    args
  end
end

class Array
  def splat(&block)
    block[*self]
  end
end

So original example can be rewritten as

Order.find(...).inject(Set.new, 
                       &[slice_args(1, &[:order_items, 
                                         :map.with_args(&[:item, 
                                                          :item_group, 
                                                          [:id, :name]])]), 
                         :splat.with_args(&:+)]).to_a

There is a pattern here. I take an object and apply some transformation (e.g. an array) to it and get similar structure as a result. What if I use hash instead of an array? Obviously I should get hash back. To make this happen I define Hash#to_proc:

class Hash
  def kv_map(&block)
    block ||= k_lambda
    inject(self.class.new) do |kv, (k, v)|
      kv[k] = block[v]
      kv
    end
  end

  def to_proc
    ps = 
      kv_map do |e|
        case e
        when Array, Hash
          e.to_proc
        when Symbol
          e.to_proc
        when Proc
          e
        else
          lambda { e }
        end
      end
    lambda { |*args| ps.kv_map{ |p| p[*args] } }
  end
end

class Array
  def to_proc(horizontal = nil)
    raise ArgumentError.new("empty collection") if empty?
    ps = 
      map do |e|
        case e 
        when Array
          e.to_proc(!horizontal)
        when Hash
          e.to_proc
        when Symbol
          e.to_proc
        when Proc
          e
        else
          lambda { e }
        end
      end
    if horizontal
      lambda { |*args| ps.map { |p| p[*args] } }
    else
      psh, *pst = ps
      lambda do |*args| 
        pst.inject(psh[*args]) { |v, p| p[v] }
      end
    end
  end
end

Now I can write things like

K_LAMBDA = lambda{ |x| x }

[1,2,3].map(&{:i => K_LAMBDA, :i_sq => :**.with_args(2)}) 
#=> [{:i_sq=>1, :i=>1}, {:i_sq=>4, :i=>2}, {:i_sq=>9, :i=>3}]

All of this may seem a bit theoretical, but it does save some typing and make code more readable if used wisely.

Thursday, June 16, 2011

Ruby thread pool in Erlang style

require "thread"

POOL_SIZE = 5

items_to_process = (0..100).to_a

message_queue = Queue.new

start_thread = 
  lambda do
    Thread.new(items_to_process.shift) do |i|
      puts "Processing #{i}"
      message_queue.push(:done)
    end
  end

items_left = items_to_process.length

[items_left, POOL_SIZE].min.times do
  start_thread[]
end

while items_left > 0 
  message_queue.pop
  items_left -= 1
  start_thread[] unless items_left < POOL_SIZE
end

Monday, May 9, 2011

JS-like containers in Rails

Quite often I need to pass complex data structure to a view. Obvious solution would be a hash, the drawback is that too much typing involved. Impressed by Javascript syntax I decided to create similar object in Ruby, and it was easy:

require "set"

class JContainer
  include Enumerable
  
  def initialize(props = {})
    @props = Set.new
    set_props(props)
  end
  
  def [](k)
    instance_variable_get("@#{k}")
  end
  
  def []=(k, v)
    k_sym = k.to_sym
    unless @props.include?(k_sym)
      @props.add(k_sym)
      (
        class << self
          self
        end
      ).instance_eval do 
        attr_accessor k_sym
      end
    end
    instance_variable_set("@#{k}", v)
    v
  end

  def ==(j_container)
    self.class === j_container && props == j_container.props
  end
  
  def set_props(props)
    props.each{ |k, v| self[k] = v }
    self
  end
  
  def props
    Hash[*(@props.map{ |p| [p, self[p]] }.flatten(1))]
  end

  def to_json
    props.to_json
  end
  
  def each
    props.each{ |k, v| yield [k, v]}
  end

  private
  
  def method_missing(k, v = nil)
    k_s = k.to_s
    if k_s.chomp!("=")
      self[k_s] = v
    else
      self[k]
    end
  end
end
So now I can do things like:
js = JContainer.new(:x => 0, :y => 1, :z => 2)
js.a = [1,2,3]
js["b"] = 2
js[:a]
js[:c]
[js.x, js.y]
js.props
JContainer.new(:x => 0, :y => 1, :z => 2) == JContainer.new(:x => 0, :y => 1, :z => 2)
JContainer.new(:x => 0, :y => 1, :z => 2) != JContainer.new(:x => 0, :y => 1, :z => 3)
JContainer.new(:x => 0, :y => 1, :z => 2).map{|k, v| [k, v] }
(0..9).map{|i| JContainer.new(:x => i)}.map(&:x)

Limited argument matching in Ruby

class Object
  def closure(&block)
    block[self]
  end
end

[1,2].closure{ |x, y| x + y } # => 3 
[[1, 2], 3].closure{ |(x, y), z| z + y } # => 5

In fact, closure can also be used for creating "limited namespace" when chaining function calls:

[1,2,3].map{ |e| e * 2 }.closure{ |a| [a[1], a[0] + a[2]] } # => [4, 8]