De vele gezichten van Array

Geplaatst door Michiel de Mare do, 01 maa 2007 13:45:00 GMT

Een van de charmes van de Array in Ruby is dat je hem op zo veel verschillende manieren kunt gebruiken:

list = ['brood', 'spelen']
list << 'pindakaas'
list[1] # => 'spelen'

stack = []
stack.push 'Schoppen 10'
stack.push 'Ruiten Aas'
stack.push 'Harten Vrouw'
stack.pop # => 'Harten Vrouw'

queue = []
queue.unshift 1
queue.unshift 2
queue.shift # => 1
queue.unshift 3

matrix = [[1,2,3],[4,5,6]]
matrix.transpose # => [[1,4],[2,5],[3,6]]

pair = ['foo','bar']
pair.first # => 'foo'
pair.last # => 'bar'

Maar kunnen we Array voor meer datatypen gebruiken? De table bijvoorbeeld?

Een table is een array van rows, een row is een array van cellen. Het interessante van een table is de cross join operatie, ook bekend als de cartesian product, oftewel een SQL join zonder WHERE-clause. Dit levert alle permutaties op van alle rows. De tabel met alle letters vermenigvuldigd met zichzelf levert bijvoorbeeld alle tweeletterwoorden op.

Hoe willen we dat uitdrukken? Zo misschien?

  letters = ('a'..'z').to_a
  letters ** letters # => [['a','a'],['a','b']...['z','z']]
  vier_letter_woorden = ([letters] * 4).cross_join

En nu de implementatie!

class Array
  def tail
    self[1..-1] 
  end

  def cross_join(v = [],cl = [])
    if empty?
      cl << v 
    else 
      first.each {|x| tail. cross_join(v + [x], cl) }
      cl 
    end
  end

  def **(other)
    [self,other].cross_join
  end
end

Waar komt dit van pas? Overal waar je permutaties of combinaties nodig hebt, en dat is vaker dan je denkt!

3 reacties

Reacties

Laat een reactie achter

  1. Erik van Oosten zei ongeveer 20 uur later:

    Mooi ding!

    Wel een beetje vreemd dat je method cross_join als instance method definieerd en niet op self. Wat betekend bijvoorbeeld ('a'..'z').to_a.cross_join?

    Waar staan de v en cl eigenlijk voor?

  2. Michiel zei ongeveer 20 uur later:

    cross_join werkt alleen op arrays van arrays (net zoals transpose ook niet op alle arrays werkt). cl komt van collection en wordt aangemaakt zodra je cross_join zonder argument aanroept. Hierin wordt het eindresultaat opgebouwd. v (value) bevat de rows die al vermenigvuldigd zijn.

    Als self (de array) leeg is, dan zijn alle tables gedaan en is v een permutatie, die aan aan cl wordt toegevoegd, anders wordt v vermenigvuldigd met de eerste table.

  3. Jules zei 15 dagen later:

    Hier is een andere implementatie van *:

    module Enumerable def concatmap(&block) map(&block).inject{|x,y| x.concat(y)} end end

    def *(other)
  concatmap{|x| other.map{|y| [x,y]}}
end

    Zo werkt Haskell’s list monad.

 (Laat url/e-mail achter »)

   Voorvertoning