Extreme Enthusiasm

C’è un libro bello e divertente che insegna a programmare in Lisp, che si chiama “The Little LISPer.” Per divertimento, proviamo a risolvere un esercizio da quel libro; ma da Rubyisti che siamo, lo facciamo in Ruby :-)

L’esercizio originale, a pag. 98:

What is (rember* a l), where a is cup, and l is ((coffee= cup ((tea) cup) (and (hick)) cup)?

Risposta:
((coffee) ((tea)) (and (hick)))

Questa rember* in pratica rimuove tutte le occorrenze del primo simbolo, in una lista comunque innestata. Una prima approssimazione potrebbe essere

def rember_star(a, l)
  l.reject {|x| x == a}
end

Infatti con questa passiamo questi test:

assert_equal [], rember_star(:anything, [])
assert_equal [], rember_star(:foo, [:foo])
assert_equal [:bar], rember_star(:foo, [:bar])
assert_equal [:a, :c], rember_star(:b, [:a, :b, :c])

Ma fallisce miseramente con questo:

assert_equal [[[]]], rember_star(:foo, [[[:foo]]])

<[[[]]]> expected but was
<[[[:foo]]]>.

perché reject non prevede di esaminare ricorsivamente gli array innestati. E poi la soluzione che vogliamo è una funzione definita ricorsivamente! Il punto è di rispolverare il vecchio muscolo della programmazione funzionale. Allora una prima versione, equivalente alla versione con reject:

def rember_star(a, l)
  if l.empty?
    []
  elsif l.first == a
    rember_star(a, l.rest)    
  else
    [l.first] + rember_star(a, l.rest)
  end
end

Nota: Ruby supporta Array#first ma, inspiegabilmente, non supporta Array#rest. Per fortuna Ruby è estendibile:

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

assert_equal [], [1].rest
assert_equal [2, 3, 4], [1, 2, 3, 4].rest

Ora, per risolvere pienamente l’esercizio, quello che resta è ricorrere non solo sulla coda della lista ma anche sulla testa:

def rember_star(a, l)
  if l.is_a? Symbol
    l
  elsif l.empty?
    []
  elsif l.first == a
    rember_star(a, l.rest)    
  else
    [rember_star(a, l.first)] + rember_star(a, l.rest)
  end
end

Di conseguenza dobbiamo aggiungere una “domanda” all’inizio: altrimenti ci ritroviamo a eseguire :foo.empty?, che produce un errore. Se la “lista” è stata montata fino a diventare un simbolo, restituiamo il simbolo. In questo modo riusciamo a passare anche il caso di test iniziale:

assert_equal [[:coffee], [[:tea]], [:and, [:hick]]], 
      rember_star(:cup, [[:coffee], :cup, [[:tea], :cup], [:and, [:hick]], :cup])

La programmazione funzionale è divertente! Ecco un problemino ulteriore (sempre da The Little LISPer):

What is (insertR* new old l), where new is roast, old is chuck, and l is
((how much (wood)) could ((a (wood) chuck)) (((chuck))) (if (a) ((wood chuck))) could chuck wood)


Risposta: ((how much (wood)) could ((a (wood) chuck roast)) (((chuck roast))) (if (a) ((wood chuck roast))) could chuck roast wood).

Riesci a scrivere insertR* in Ruby? O nel tuo linguaggio preferito?

Aggiornamento: aggiunta immagine copertina

This entry was posted on 20 October 2007 at 16:44 and is filed under Agile. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.