Hashes vs Lambdas

Question

I found two examples that looked close to each other for finding Fibonacci numbers:

• Lambda

  fibonacci = ->(x){ x < 2 ? x : fibonacci[x-1] + fibonacci[x-2] }
  fibonacci[6]  # => 8
  

• Hash

  fibonacci = Hash.new{ |h,x| h[x] = x < 2 ? x : h[x-1] + h[x-2] }
  fibonacci[6]  # => 8 
  

I used both hashes and lambdas in ruby before, but not like this. This is more of a way of storing a function:

if x < 2
  x
else
 fibonacci[x-1] + fibonacci[x-2]

1. Can you explain in detail how this is working? Is this using recursion?
2. What are the differences between hashes like this and lambdas?

Answer 1

What are the differences between hashes like this and lambdas?

lambdas and hashes have nothing in common. Your question is like asking:

What are the differences between methods and arrays?

It's just that Hashes can specify a default value for a non-existent key:

h = Hash.new(10)

h["a"] = 2
puts h["a"]
puts h["b"]

--output:--
2
10 

Hashes also provide a way to dynamically specify the default value: you can provide a block. Here is an example:

h = Hash.new do |h, key|
  h[key] = key.length
end

puts h['hello']
puts h['hi']
p h

--output:--
5
2
{"hello"=>5, "hi"=>2}

When you access a non-existent key, the block is called, and the block can do whatever you want. So someone cleverly figured out that you could create a hash and specify a default value that calculated fibonacci numbers. Here is how it works:

h = Hash.new do |h, key| 
  if key < 2  
    h[key] = key
  else 
    h[key] = h[key-1] + h[key-2] 
  end
end

That creates the Hash h, which is a Hash with no keys or values. If you then write:

puts h[3]

...3 is a non-existent key, so the block is called with the args h and 3. The else clause in the block executes, which gives you:

h[3-1] + h[3-2]

or:

h[2] +  h[1]

But to evaluate that statement, ruby has to first evaluate h[2]. But when ruby looks up h[2] in the hash, the key 2 is a non-existent key, so the block is called with the args h and 2, giving you:

(h[2-1] + h[2-2]) + h[1]

or:

(h[1] + h[0])    + h[1]

To evaluate that statement, ruby first has to evaluate the first h[1], and when ruby tries to look up h[1] in the hash, 1 is a non existent key, so the block is called with the args h and 1. This time the if branch executes, causing this to happen:

 h[1] = 1

and 1 is returned as the value of h[1], giving you this:

 (1 + h[0])      + h[1]

Then ruby looks up h[0], and because 0 is a non-existent key, the block is called with the args h and 0, and the if clause executes and does this:

h[0] = 0

and 0 is returned as the value of h[0], giving you this:

(1 + 0)        + h[1]

Then ruby looks up h[1] in the hash, and this time the key 1 exists, and it has a value of 1, giving you:

(1 + 0)        + 1

And that is equal to 2, so h[3] is set equal to 2. After calling h[3], you get this output:

puts h[3]
p h

--output:--
2
{1=>1, 0=>0, 2=>1, 3=>2}

As you can see, the previous calculations are all cached in the hash, which means that those calculations don't have to be performed again for other fibonacci numbers.

Answer 2

Yes it is using recursion. If we look at the code in the {}-brackets we can figure out the answer. Let's start looking at the hash. The values after new keyword is the default value. A value that will be assigned if the value does not already exist in the hash.

hash = Hash.new
p hash['new_value'] #=> nil

default_value_hash = Hash.new(0)
puts default_value_hash['new_value'] #=> 0

hash_with_block = Hash.new{|h,x| x}
puts hash_with_block['new_value'] #=> 'new_value'

So when we declare

 fibonacci = Hash.new{ |h,x| h[x] = x < 2 ? x : h[x-1] + h[x-2] }

we are basically saying - Create a new hash with a default value. If we ask for a number (x) smaller or equal to two, just return the input (x). Else, give us the sum of the dictionary values where the key is x-1 and x-2. Basically the Fibonacci algorithm. If x-1 and x-2 does not exist, it runs the same code again until the two basic input values are 1 and 2.

The difference between the two approaches is that the hash saves the values (in a hash...). This can be a huge advantage in some cases. Every time the lambda is called it needs to recalculate the values for all numbers below the called value.

# Let's create a counter to keep track of the number of time the lambda is called.
# Please do not use global variables in real code. I am just lazy here.
@lambda_counter = 0

fibonacci_lambda = ->(x){ 
  @lambda_counter += 1
  x < 2 ? x : fibonacci_lambda[x-1] + fibonacci_lambda[x-2]
}

p (1..20).map{|x| fibonacci_lambda[x]}
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

p @lambda_counter # => 57290
# lambda called 57290 times!

@hash_counter = 0

fibonacci_hash = Hash.new{ |h,x|
  @hash_counter += 1
  h[x] = x < 2 ? x : h[x-1] + h[x-2]
}

p (1..20).map{|x| fibonacci_hash[x]}
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

p @hash_counter # => 21
# Only called 21 times!

The reason for the big difference in calls is the nature of recursion. The lambda does not store its values and when the value for 10 is calculated it recalculates the value for 3 more than 20 times. In the hash this value can be stored and saved for later.

Answer 3

In the first case, you are defining a recursion which will be called recursively.

In the case of the hash, the values will also be computed recursively, but stored and then access for giving the result.

• Lambda

  fibonacci = ->(x){ x < 2 ? x : fibonacci[x-1] + fibonacci[x-2] }
  fibonacci[6]
  fibonacci # => <Proc:0x2d026a0@(irb):5 (lambda)>
  

• Hash

  fibonacci = Hash.new{ |h,x| h[x] = x < 2 ? x : h[x-1] + h[x-2] }
  fibonacci[6] 
  fibonacci # => {1=>1, 0=>0, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8}
  

In one case, you are not leaving any footprint in memory, whereas the hash will continue to keep the computed value. So it depends on what you need.

If you need to access fibonacci[6] one more time, the lambda will recompute the result, whereas the hash will give you the result immediately without redo the calculations.