Splitter test

di leonardo maffi, 15 febbraio 2006

[Torna all'indice]

Un piccolo problema di programmazione che potete provare a risolvere col vostro linguaggio di programmazione preferito.

Data una sequenza L1 di oggetti lunga a piacere e una sequenza P lunga a piacere di predicati (cioè funzioni che dato un valore in ingresso restituiscono un valore Booleano in uscita, ad esempio se un dato numero è pari), restituire in uscita una sequenza di sequenze, la prima deve contenere tutti gli oggettti di L1 per i quali il primo predicato è vero. La seconda sequenza deve contenere tutti gli elementi per i quali il primo predicato è falso e il secondo è vero, la terza sequenza deve contenere tutti gli elementi per i quali il primo e secondo predicato sono falsi e il terzo è vero, ecc. Così via fino a che rimangono elementi o i predicati finiscono.

Un esempio, per semplicità uso un array di numeri (potete rendere il vostro programma in grado di accettare un array di qualunque tipo di oggetti, oppure più semplicemente solo un array di numeri, ad esempio interi):

L1 = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]

I predicati sono, nell'ordine:
numero pari?
numero negativo?
numero>3?
numero positivo?
numero <1000?
numero >2000?

Risultato:
[-4, -2, 0, 2, 4], [-5, -3, -1], [5], [1, 3], [], [], []

Cioè le sottosequenze restituite sono: numeri pari (tra quelli di ingresso), numeri dispari negativi, i numeri dispari maggiori di 3, i numeri dispari positivi positivi, i numeri minori di 1000 tra quelli rimasti, i numeri maggiori di 2000 tra quelli rimasti.

La formulazione del problema è un po' elastica, non è necessario che la formattazione dell'output sia identica a questa, e se volete potete interrompere il programma quando la lista dei dati di partenza si è svuotata.

Qui di sotto riporto la mia soluzione in Python (una funzione), seguita da un esempio di chiamata della funzione, seguita da l'output relativo (non si tratta del mio programma più corto, ho tenuto di conto che sia ben leggibile). Ho anche aggiunto la spiegazione riga per riga del mio programma.

Questo problema era stato risolto originariamente in Lisp (sotto c'è anche una soluzione in Lisp), io ho trovato una soluzione in Python, per fare un confronto tra i due linguaggi e per fare esercizio.

Riferimento originale:
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/aac5c3f43b3ffe7e/a4f6fac0cc9b1738


S
P
O
I
L
E
R

S
P
O
I
L
E
R

S
P
O
I
L
E
R

Una mia soluzione in Python:

def split(seq, *predicates):
    "Split progressively the given sequence using some predicates."
    if not predicates: return [seq]
    results = [], []
    for el in seq:
        results[not predicates[0](el)].append(el)
    return [results[0]] + split(results[1], *predicates[1:])


print split(range(-5,6), lambda n: n%2==0, lambda n: n<0, lambda n: n>3,
            lambda n: n>0, lambda n: n<1000, lambda n: n<2000)


Output:
[[-4, -2, 0, 2, 4], [-5, -3, -1], [5], [1, 3], [], [], []]

Spiegazione mia soluzione:

- La prima riga prende in ingresso la sequenza e un numero arbitrario di parametri che vengono inseriti in una tuple dei predicates (l'asterisco indica un mumero a piacere di parametri).
- la seconda riga e "superflua", è una docstring, puo' essere acceduta ad esempio con un
print split.__doc__
- La terza riga resituisce una lista che contiene la sequenza dei valori nel caso che non siano stati passati dei predicati (una sequenza è vera se non è vuota).
- La quarta riga crea results, una tupla con due liste vuote dentro.
- la quinta riga scansiona la sequenza data, el è l'elemento corrente di seq
- la sesta riga viene eseguita per tutti gli elementi di seq. predicates[0] è il primo predicato, predicates[0](el) applica tale funzione ad el. Il risultato è un booleano, che in Python è anche un intero 0 o 1 (è True o False solo nel codice o quanto lo si stampa, ma internamente è un numero intero). Per cui questo numero viene usato come indice di results (le tuple sono immutabili, ma stiamo mutando quello che contiene uno degli oggetti mutabili che contiene), per cui results[not predicates[0](el)] individua la prima o seconda lista di results. A tale lista si appende in coda l'el.
- la settima riga effettua una chiamata ricorsiva (è una variante della ricorsione in coda, per cui un buon compilatore funzionale potrebbe trasformarla in una piu' efficiente iterativa), e resituisce una lista che contiene la lista dei valori per cui il predicato è vero (dato che c'era un not prima di predicates[0](el) ), unita (+, cioè un append tra sequenze) al risultato della split sui rimanenti dati e applicata con tutti i predicati rimasti, eccetto il primo. predicates[1:] indica tutti gli elementi di una sequenza a partire dal primo escluso, usa la sintassi di slicing. L'asterisco davanti indica che tale lista va fatta esplodere, dato che io ho scelto che la funzione split accetti i predicati "sfusi" e non impacchettati in una sequenza come diceva il testo del problema. Se volessi rispettare tale testo mi basterebbe togliere i due asterischi dal programma.


Usando le macro (che a dire il vero in questo problema non sarebbero necessarie) in Lisp lo stesso programma (ma iterativo invece che ricorsivo) potrebbe essere (presumo che una persona con esperienza in Lisp possa scrivere un programma più corto di questo) (credo che l'autore sia Pascal Costanza):

(defmacro predicate-collect (list &body predicates)
   (let ((collectors (mapcar (lambda (predicate)
                                (declare (ignore predicate))
                                (gensym "COLLECT"))
                             predicates))
         (collect-t (gensym "COLLECT")))
      `(with-collectors (,@collectors ,collect-t)
          (dolist (l ,list)
            (cond ,@(mapcar (lambda (predicate collector)
                              `((funcall ,predicate l) (,collector l)))
                             predicates collectors)
                  (t (,collect-t l)))))))


Un esempio d'uso:

> (predicate-collect '(-5 -4 -3 -2 -1 0 1 2 3 4 5)
   (function evenp)
   (lambda (n) (< n 0))
   (lambda (n) (> n 3)))
   (-4 -2 0 2 4)
   (-5 -3 -1)
   (5)
   (1 3)

In questa occasione Python fa bella figura se confrontato col Lisp (ma sono due soluzioni abbastanza diverse e non del tutto confrontabili). Il linguaggio Lisp ha comunque altri vantaggi, è compilabile e potenzialmente molto veloce, e le sue macro permettono di fare cose altrimenti molto difficili o che richiederebbero più codice.

[Torna all'indice]