Solving a Pycon puzzle... in Haskell
I was at Pycon Ireland last week-end. The event was quite successful and amazingly so considering it was a first for Dublin.
One of the highlights was one of those puzzles made of 13 plastic pieces to reassemble into a 4x4x4 cube (all pieces composed by 5 or 4 basic 1x1x1 cubes), brought by the guy at the Google stand. On Sunday, during the sprint session, the most successful one in terms of attendance and enthusiasm was an effort to solve the puzzle in python, cut short by the end of Pycon. The project seems to be ongoing at this time.
As the problem is very combinatorial in flavour, I thought the best tool for the job would be Haskell, which lends itself to concise expression of mathematical ideas. So I made an attempt at the implementation. Running it all night long gave me a few tens of solutions.
Some Haskell constructs are particularly interesting in the solution.
The monadic >>= operation for lists was used for the generation of all possible roto-translations of the pieces. If a function
f :: Bitmap -> [ Bitmap ] f bm = ... a certain list of Bimaps derived from bm ...yields a family of variations of a piece representation (for instance all translations, or all rotations around an axis), and g is another such function, then the expression
f bm >>= greturns all variations generated by g of all variations generated by f of the initial piece bm.
In the solution this is used in
-- All 24 rotations rotations bm = rotationsx bm >>= axischangex
which generates all the
Modelli di controllo di accessi come tipi Haskell
Prendendo spunto dalla lettura di uno dei miei blog preferiti, mi è capitato di dare una scorsa al documento intitolato A Survey of Access Control Models, che descrive modelli di controllo di accessi di complessità crescente. Questa complessità crescente si manifesta nella dipendenza da fattori intermedi sempre più ricchi e mi è venuta la tentazione di esprimere queste dipendenze come signature di funzioni in Haskell. Ecco cosa ne è uscito fuori.
Pillole di Haskell - ricerca di duplicati
Di recente ho dovuto scrivere una funzioncina in Haskell per trovare elementi duplicati in una lista. Anche se non necessariamente il più furbo, trovo che il metodo che ho usato fornisca un esempio interessante di programmazione funzionale in questo linguaggio.
L'idea (semplice) è la seguente: ordiniamo la lista (il che richiede che gli elementi siano confrontabili, cioè che appartengano alla classe Ord) e poi cerchiamo due elementi consecutivi uguali. Mostro come implementare quest'idea, procedendo per applicazioni consecutive di funzioni.
Haskell: che tipo vuoi?
Diverse cose sono fonte di meraviglia per chi si avvicina ad Haskell. Molti dei linguaggi di uso comune (Java, C, C++, perl, Python e simili) hanno una qualche forma di polimorfismo, che permette di applicare uno stesso metodo o funzione a tipi diversi, con un risultato che dipende dal tipo degli argomenti o dell'oggetto su cui viene invocato.
Ad esempio:1 + 3 => 4 "questo" + "quello" => "questoquello"
"a".clone() => una nuova stringa "a" connection.clone() => un nuovo oggetto di classe ConnectionIn perl esiste anche un tipo (limitato) di dipendenza inversa, in cui il tipo di risultato dipende non dagli argomenti, ma dal contesto in cui il metodo viene chiamato.
@a = localtime(); # list context # @a contiene ora una lista con secondi, minuti, ore etc., tipo ( 45, 42, 20, 24, 2, 109, 2, 82, 0 ) $a = localtime(); # scalar context # $a contiene ora la stringa "Tue Mar 24 20:44:07 2009"
In Haskell l'inferenza dei tipi fa sì che il tipo della funzione invocata dipende dalle informazioni che il type checker ricava dal contesto in cui viene chiamata.
Dipendenze esplicite
Uno dei punti di forza dello stile di programmazione funzionale è che la dipendenza della valutazione di una funzione dai suoi parametri è espressa in maniera esplicita. Questo può costituire un peso per lo sviluppatore nella fase di scrittura del codice, ma rappresenta un vantaggio notevole nelle fasi successive di debugging e manutenzione.
Nello stile di programmazione imperativa, può (legittimamente) capitare che un frammento di codice
a = 1; print ( sambucaBottles() ); a = 2; print ( sambucaBottles() );dia per risultato la stampa a schermo di
1 bottiglia di sambuca 2 bottiglie di sambucaAd esempio, questo accadrebbe se a fosse una variabile disponibile alla funzione sambucaBottles e se questa avesse un'implementazione del tipo (in pseudo-code)
Pillole di Haskell - un uso di id
La funzione id (per identity=identità) in Haskell prende il suo argomento e lo restituisce immutato. La sua definizione è
id :: a -> a id x = xid è quindi l'elemento neutro per composizione di funzioni, cioè per ogni f :: a -> b, si ha che
f = f . id = id . f
id non sembra di grande utilità in quanto, di fatto, non fa niente. La sua applicazione a un argomento si può sempre omettere, così come la sua composizione con un'altra funzione. L'unico uso possibile sembrerebbe quello di essere passata come argomento a una funzione di ordine superiore che si aspetti una generica funzione a->a. Chiaramente, nei soli casi in cui passare id abbia senso nella logica del programma.
...MA...
se pure id non ha effetti dal punto di vista computazionale, possiamo utilizzarla per avere vantaggi in fase di compilazione.
Se definiamo una nuova funzione
myid :: A -> A myid = id
dove A è uno specifico tipo di dati (un ADT o un type, anche parzialmente specificati), allora myid forza il tipo dell'argomento, anche nel caso in cui questo sia a priori generico.