The Little Pickaxer

Cover from The Little LISPer

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

4 Responses to “The Little Pickaxer”

  1. Ugo Cei Says:

    “Questa rember* in pratica rimuove tutte le occorrenze del primo simbolo, in una lista comunque innestata.”

    Innestata? Non sapevo che le liste fossero piante ;)

    Questa come tradurre “I pretend to have a horse in my factory” come “Pretendo di avere un orso nella mia fattoria”.

    ;))))

  2. Marco Trinci Says:

    rember_star(A, [A|Rest]) -> rember_star(A,Rest);
    rember_star(A, [First|Rest]) -> [rember_star(A,First)] ++ rember_star(A,Rest);
    rember_star(_, A) -> A.

    rember_star_test_() -> [
    ?_assertMatch ([], rember_star(anything, [])),
    ?_assertMatch ([], rember_star(foo, [foo])),
    ?_assertMatch ([bar], rember_star(foo, [bar])),
    ?_assertMatch ([a, c], rember_star(b, [a, b, c])),
    ?_assertMatch ([[[]]], rember_star(foo, [[[foo]]])),
    ?_assertMatch ([[coffee], [[tea]], [e, [hick]]], rember_star(cup, [[coffee], cup, [[tea], cup], [e, [hick]], cup]))
    ].

    insertR_star(A, B, [A|Rest]) -> [A,B] ++ insertR_star(A,B,Rest);
    insertR_star(A, B, [First|Rest]) -> [insertR_star(A,B,First)] ++ insertR_star(A,B,Rest);
    insertR_star(_, _, A) -> A.

    insertR_star_test_() -> [
    ?_assertMatch ([], insertR_star(anything, anything, [])),
    ?_assertMatch ([foo,chuck], insertR_star(foo, chuck, [foo])),
    ?_assertMatch ([bar], insertR_star(foo, anything, [bar])),
    ?_assertMatch ([a,b,chuck,c], insertR_star(b, chuck, [a, b, c])),
    ?_assertMatch ([[[foo, chuck]]], insertR_star(foo, chuck, [[[foo]]])),
    ?_assertMatch (
    [[how, much, [wood]], could, [[a, [wood], chuck, roast]], [[[chuck, roast]]], [se, [a], [[wood, chuck, roast]]], could, chuck, roast, wood]
    , insertR_star(chuck,roast,
    [[how, much, [wood]], could, [[a, [wood], chuck]], [[[chuck]]], [se, [a], [[wood, chuck]]], could, chuck, wood]
    ))].

  3. Matteo Vaccari » Blog Archive » Queste funzioni “*” Says:

    […] Quindi la rember* non altro che la reject applicata ad alberi (ovvero liste comunque innestate. S Ugo, alla fine queste liste sono piante :-). […]

  4. Let’s start with Django! « If ain’t broken don’t fix it Says:

    […] So far I’m in love with it. All the niceties of ROR without the dark arts part. Of course if you are able to read and enjoy The little LISPer you probably are much more intelligent than me. […]

Leave a Reply