4 ms·

One of the most beautiful things in Ruby that I have ever seen is this fibonacci code. fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 k[v-1] + k

One of the most beautiful things in Ruby that I have ever seen is this fibonacci code. fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 k[v-1] + k[v-2] end

hit8run 3y ago
Let’s make it a one liner :D fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] } Example: fib[123] # => 22698374052006863956975682 Makes use of memoization.
- nix-zarathustra 3y ago
  Yes, I was going off of memory and thought that it was memoising it, but I made a mistake and fixed it. fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 k[v] = k[v-1] + k[v-2] end I like yours better though, it seems a lot simpler with the less than 2 check.
inopinatus 3y ago
Or an Ackermann: A = Hash.new { |a,(m,n)| a[[m,n]] = m==0 ? n+1 : n==0 ? a[[m-1,1]] : a[[m-1, a[[m, n-1]]]] } A[[3,4]] #=> 125 A.inspect #=> ... long However, the application utility of a self-populating lazily-evaluated lookup structure goes further. A hash with a default function works great as a simple caching wrapper for all manner of results, for example when talking to slow or fine-grained APIs.
devoutsalsa 3y ago
With caching... fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 unless k.key? v k[v] = k[v-1] + k[v-2] end k[v] end
- psychoslave 3y ago
  Wouldn't you get the same result using memoization idiomatic syntaxes? k[v] ||= k[v-1] + k[v-2]
  - devoutsalsa 3y ago
    That was the first thing I tried, but it blew the stack :) You can still blow the stack if you pick a number that's too high, like k[20000] or something. But if you pick a lower number & cache that, then you can (eventually) call a higher number without blowing the stack. This recursive approach is a horribly inefficient algorithm anyway, so I don't think it's worth optimizing :)
  - vidarh 3y ago
    No, because that is equivalent to k[v] || (k[v] = k[v-1] + k[v-2]) And that first k[v] (unlike k.key?(v)) will trigger the Hash.new block again, so it'll recurse until it runs out of stack. But neither check is necessary, because the Hash.new block will only ever get called if k.key?(v) is false. If you want a more compact version, you could do: fib = Hash.new do |k,v| next 1 if v == 0 || v == 1 k[v] = k[v-1] + k[v-2] end
- oddx 3y ago
  But caching doesn't required here. Hash.new calls block only if value isn't initialialized.
  - devoutsalsa 3y ago
    I just did it for fun. This particular recursive approach is super slow for numbers of nontrivial size, so I was just curious if I could even make the caching work in the block. It's not worth optimizing a suboptimal query when a more efficient option is available anyway.
    - deleted 3y ago
      [deleted]
    - sinkwool 3y ago
      You don't need the `unless k.key? v` guard. The `Hash.new` block only gets called when the key is not present in the hash.
      - devoutsalsa 3y ago
        The caching makes it faster the trade off being more using more memory. I just wanted to see if it’d work.
StackOverlord 3y ago
You can also recursively define fib as a lazy sequence that is the pairwise sum of fib and fib shifted by one. (Clojure, from Rosetta Code). (def fib (lazy-cat [0 1] (map + fib (rest fib)))) => (take 10 fib) (0 1 1 2 3 5 8 13 21 34) Explanation: 0 1 1 2 3 5 ; this is fib + 1 1 2 3 5 8 ; this is (rest fib) --------------- 1 2 3 5 8 13 ; this is (map + fib (rest fib)) ; and the sequence needs to be initialized with (lazy-cat [0 1] ...

One of the most beautiful things in Ruby that I have ever seen is this fibonacci code. fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 k[v-1] + k[v-2] end

hit8run 3y ago

Let’s make it a one liner :D fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] } Example: fib[123] # => 22698374052006863956975682 Makes use of memoization.

nix-zarathustra 3y ago
Yes, I was going off of memory and thought that it was memoising it, but I made a mistake and fixed it. fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 k[v] = k[v-1] + k[v-2] end I like yours better though, it seems a lot simpler with the less than 2 check.

inopinatus 3y ago

Or an Ackermann: A = Hash.new { |a,(m,n)| a[[m,n]] = m==0 ? n+1 : n==0 ? a[[m-1,1]] : a[[m-1, a[[m, n-1]]]] } A[[3,4]] #=> 125 A.inspect #=> ... long However, the application utility of a self-populating lazily-evaluated lookup structure goes further. A hash with a default function works great as a simple caching wrapper for all manner of results, for example when talking to slow or fine-grained APIs.

devoutsalsa 3y ago

With caching... fib = Hash.new do |k, v| next 1 if v == 0 || v == 1 unless k.key? v k[v] = k[v-1] + k[v-2] end k[v] end

psychoslave 3y ago
Wouldn't you get the same result using memoization idiomatic syntaxes? k[v] ||= k[v-1] + k[v-2]
- devoutsalsa 3y ago
  That was the first thing I tried, but it blew the stack :) You can still blow the stack if you pick a number that's too high, like k[20000] or something. But if you pick a lower number & cache that, then you can (eventually) call a higher number without blowing the stack. This recursive approach is a horribly inefficient algorithm anyway, so I don't think it's worth optimizing :)
- vidarh 3y ago
  No, because that is equivalent to k[v] || (k[v] = k[v-1] + k[v-2]) And that first k[v] (unlike k.key?(v)) will trigger the Hash.new block again, so it'll recurse until it runs out of stack. But neither check is necessary, because the Hash.new block will only ever get called if k.key?(v) is false. If you want a more compact version, you could do: fib = Hash.new do |k,v| next 1 if v == 0 || v == 1 k[v] = k[v-1] + k[v-2] end
oddx 3y ago
But caching doesn't required here. Hash.new calls block only if value isn't initialialized.
- devoutsalsa 3y ago
  I just did it for fun. This particular recursive approach is super slow for numbers of nontrivial size, so I was just curious if I could even make the caching work in the block. It's not worth optimizing a suboptimal query when a more efficient option is available anyway.
  - deleted 3y ago
    [deleted]
  - sinkwool 3y ago
    You don't need the `unless k.key? v` guard. The `Hash.new` block only gets called when the key is not present in the hash.
    - devoutsalsa 3y ago
      The caching makes it faster the trade off being more using more memory. I just wanted to see if it’d work.

StackOverlord 3y ago

You can also recursively define fib as a lazy sequence that is the pairwise sum of fib and fib shifted by one. (Clojure, from Rosetta Code). (def fib (lazy-cat [0 1] (map + fib (rest fib)))) => (take 10 fib) (0 1 1 2 3 5 8 13 21 34) Explanation: 0 1 1 2 3 5 ; this is fib + 1 1 2 3 5 8 ; this is (rest fib) --------------- 1 2 3 5 8 13 ; this is (map + fib (rest fib)) ; and the sequence needs to be initialized with (lazy-cat [0 1] ...