Monday, October 25, 2010

Codebreaker in F#

(english version of this post comes later, may be :D )

Ho studiato un po' di F#, finalizzando lo studio ad un kata, quello del codebreaker (marking guess), già a suo tempo affrontato in C# (http://www.vimeo.com/13072671) (ma che non ho mai commentato).

Ecco il link di questa nuova versione in F#: http://www.vimeo.com/16177730



codebreaker, marking guess, in F# from tonyx on Vimeo.




Imparare un linguaggio nuovo è stato uno dei miei buoni propositi quando sono tornato dalla Software Craftsmanship conference tenutasi a Bletchley Park il 7 ottobre. A proposito: non ho scritto nessun post sull'argomento. Forse è un po' tardi per questo, vabbe', sopravvoliamo.

Un commento, a grandi linee su questo codebreaker in F#

Uso un piccolo wrapper (gu' presente nel file sorgente) che consente l-uso stringhe anziché liste in modo da poter scrivere "xxxx" anziché ['x';'x';'x';'x'].

Oppure un test del tipo AssertEquals(['m'] , guess ['y'; 'x';'x';'x'] ['r';'g';'b';'y'] ) lo posso scrivere così shouldBe "m" guess "yxxx" "rgby"

È zucchero sintattico.


Nella sostanza: non si tratta di una mera trasposizione in F# dell'algoritmo usato nella versione C#.

Ho tentato soprattutto di sfruttare le caratteristiche di questo linguaggio ed in particolare dei costrutti ricorsivi, e poi ho fatto un po' più di refactoring, e di separazione di responsabilità (anche se penso che siano mancati alcuni passi alla fine).

Per esempio:

nel secondo test il colore corretto (ma che non è non nella giusta posizione) è il primo, e siccome uso il pattern matching [H::T] dove H è la testa della lista, viene facile usare H per la logica che mi serve ai fini del caso rappresentato dal test, e tenere la coda T per il resto (la chiamata ricorsiva).

Il codice per passare il secondo test è


let mark guess secret =
match guess with
| H::T when List.contains H -> ['m']
| _ -> []



Il codice per passare il terzo test (in cui il match è il secondo elemento, ovvero la testa della coda T) è:

let rec mark guess secret
match guess with
|H::T when List.contains H secret -> ['p']
|H::T -> mark T secret
_ -> []

Notare ce ho aggiunto il "rec" (per dire al compilatore che mark verrà chiamata ricorsivamente) ed ho eseguito la chiamata ricorsiva sulla coda (mark T secret).

Il caso aggiuntivo del doppio match si risolve aggiungendo, in caso di match, oltre alla 'p', il risultato della chiamata ricorsiva in coda (mark T secret)

Non ho intenzione di spiegare tutto il kata, e sorvolo il caso dei test sui match non posizionali perché è del tutto analogo.

Mi limito ad osservare che verso la fine un po' di lavoro viene fatto per togliere alle funzioni di match posizionale e non posizionale la responsabilità di costruire il risultato (sequenze d 'p' ed 'm') e spostarlo verso un'altra funzione, facendo in modo che suddette funzioni si limitino a contare i match, lasciando ad altri il compito di rappresentarlo con dei 'p' 'm', o come si vuole.

In soldoni, per esempio la funzione di calcolo dei match posizionali, è prima questa (che restituisce tanti 'p' quanti sono suddetti match):


let rec positionalMatch guess secret =
match guess, secret with
| H::T, H1, T1 when H = H1 -> 'p' @ positionalMatch T T1
| H::T, H1, T1 -> positionalMatch T T1
| _ -> []

ma poi diventa questa


let rec positionalMatch guess secret =
match guess, secret with
| H::T, H1, T1 when H = H1 -> 1 + positionalMatch T T1
| H::T, H1, T1 -> positionalMatch T T1
| _ -> 0

che appunto accumula il risultato in un numero, anziché in una sequenza.

Per la trasformazione del numero in sequenza utilizzo questo trucchetto, che mostra qualche finezza di questo linguaggio:

[1..count] |> Seq.fold (fun acc x -> acc @ ['p']) []


che più o meno potrebbe essere spiagato come:
mandare la sequenza da uno fino a count in "pipeline" ad una funzione che opera accumulando un certo valore appendendovi un 'p' e partendo da una lista vuota, e restituendo alla fine tale risultato.

In altri linguaggi sarebbe bastato forse scrivere qualcosa come ['p']*count, per ottenere la stessa cosa, ma comunque... sempre meglio che un ciclo for.

Per finire:

È facile intuire che il codice che conta i match non posizionali include nel conteggio anche quelli posizionali, cosa che non va bene nel risultato. Bisogna restituire questi match al netto dei match posizionali, che vanno indicati in modo diverso (con i 'p').

Questo problema veniva risolto (nella vecchia versione del kata) con un trucchetto: eliminando dalla concatenazione del risultato posizionali + non posizionali un numero di caratteri pari ai posizionali stessi.

Però se il risultato richiesto fosse stato invertito (prima i non posizionali e poi i posizionali) questa cosa non avrebbe funzionato.

Per prevenire questo problema è meglio fare in modo che i non posizionali siano già al "netto" dei posizionali prima di concatenarli. In questo modo si introduce minore resistenza a certi cambiamenti desiderati (come questo di invertire le 'p' con le 'm').

È un po' quanto fatto qui (anche se c'è spazio per miglioramenti), aiutati dal fatto che i match, dopo il refactoring, vengono effettivamente contati, indipendentemente dal fatto che poi verranno rappresentati con dei 'p', dei 'm' o in un particolare ordine o altro.

Ma non mi prolungo oltre, anche se da dire ne avrei.
Penso che I kata non vadano commentati. Vanno fatti, vanno visti, vanno "goduti" e, ovviamente, vanno migliorati.

Per riferimenti:

La versione di Corey Haines (con una rapida introduzione del problema)
http://katas.softwarecraftsmanship.org/?p=27 (a sua volta presa dal testo su Rspec)

La versione in IronPython di Mark Heath:
http://vimeo.com/15329417

La mia versione in C#:
http://katas.softwarecraftsmanship.org/?p=168

No comments: