Wednesday, July 10, 2019

Fsharp code kata: Prisoner Dilemma

This blog is about the Prisoner Dilemma in F#

(github code:

This code is about:
defining the possible strategies
defining the player types
creating an iterated prisoner dilemma tournament
playing a tournament.
computing the scores in a tournament.

Let's with the description and the code:

1) Each move can be : Cooperates, or Defect

2) the result of a single game between two players is this record

Let's also define the mutual score of a jointmove.

3) given a JointMove, we get a score determined by both the players moves:
To determine the JointScore, given a JointMove we have the following function

I want to have a version of the previous function that allows me to "parametrize" the scores, and chack the  P>R>T>S rule at compile time

In the "iterated" version, two players play repeatedly. each player remembers the history of the jointMoves and can use it to decide the next move.

So a player adopts a Strategy, which is a function from jointMoves list to a Move:

type Strategy = JointMove list -> Move

We may also want to label a strategy with a name, so we define a type of record called StrategyInfo:

type StrategyInfo = {Name: string; Strategy:Strategy}

We want to give to each player a name and a StrategyInfo (which means a strategy with a name):
type Player = {Name: string; StrategyInfo: StrategyInfo}

Any game, at a certain state, involves two players, and a list of jointMove that they made:

type Game = { Player1:Player; Player2:Player; JointmoveHistory: JointMove list }

A "tick" is the joint play of both player in a game. The result will be the same game with their joint moves added to the history of moves:

A function for "ticking" a game n time will be useful:

Now, let's try some simple cases, not before defining the naive strategy, the cooperator:

let (cooperatorStrategy:Strategy) =
     fun _ ->

We want two create a cooperatorstrategyInfo, and two cooperators players, which use the same strategyInfo:

let cooperatorStrategyInfo = {Name="cooperatorStrategy";Strategy=cooperatorStrategy}
let cooperator1 = {Name = "cooperator1";StrategyInfo= cooperatorStrategyInfo}
let cooperator2 = {Name = "cooperator2";StrategyInfo= cooperatorStrategyInfo}

let's define a new game:
let aGame = {Player1=cooperator1;Player2=cooperator2;JointmoveHistory=[]}

let's tick it one time:

game |> tick

the result is a game with a one item in the history of moves.
let't "3 ticks" the game, using the nTicks function:

nTick game 3

the resulting game has a history of moves longest 3.

We can't do so much with a single game.
We need a way to define a tournament, which is based on a list of games, and a number representing the "ticks for game"

(edit July 11 - 2019: in the new version I dropped the tornment type, and always use the games, by playing a game for n "ticks" using the function playGameNTimes)

type Tournment = {Games:Game list; TicksForGame: int}

What the previous code actually means is, described in a procedural way:
for each player, get any player which is different from the current player, and create a game of them. The result will be "flattened" by the List(@) [] operator.
The resulting operation will be the game, and the function will return a structure given by the games and the ticks for each game.
This will ensure that for each pair of players there will be a game with it as the first and second player (and vice-versa).

To play a tournament, we just have to tick each game:
Given a game, we may want to get the total score of the game (given by cumulating all the scores):

For a list of games, we want to get all the players and score for game, and put them in triplets (player1, player2, jointScore):

We want to compute the score in a set of games for a single player.

And we want also the scores for all the players.
(it looks redundant having a way to re-extract players that we already used from the beginning, but for now I found easier to get back players from the games, also because in future "evolutionary" versions of the game players may mutate).

Now suppose that we will start a tournment between four players:
a cooperator, a defector, a random, and a titForTat
I define a strategyInfo for each of them:

    let cooperatorStrategyInfo = {Name="cooperatorStrategy";Strategy=cooperatorStrategy}
    let defectorStrategyInfo = {Name="defectorStrategy"; Strategy=defectorStrategy}
    let randomStrategyInfo = {Name="randomStrategy";Strategy=randomStrategy}
    let titForTatStrategyInfo = {Name="titForTatStrategy";Strategy=titForTatStrategy}

To define a single player, like a cooperator, we may  say:
    let cooperatorPlayer = {Name="cooperator";StrategyInfo=cooperatorStrategyInfo}

But we rather want to have a chunk of cooperators, sharing the same strategy, so we have the following function:

Now suppose we want to make a tornment between 5 cooperators, 5 titForTat, 5 defectors, and 5 randoms:

let cooperatorPlayers = makeNPlayersByStrategyInfo cooperatorStrategyInfo 5
let titForTatPlayers = makeNPlayersByStrategyInfo titForTatStrategyInfo 5
let randomPlayers = makeNPlayersByStrategyInfo randomStrategyInfo 5
let defectorPlayers = makeNPlayersByStrategyInfo defectorStrategyInfo 5

We put all players in a single list:

let allPlayers = cooperatorPlayers@titForTatPlayers@randomPlayers@defectorPlayers

we create a tournment, making all players play against each other, with 10 ticks for game:

let tournment = makeTournment allPlayers 10

we run the tournment:

let playedGames = playTournment tournment

Now we can see all the scores, sorted from the lowest:

sortedPlayersScore playedGames;;

this is the sketch of the result, showing that in this kind of tournament the defector is generally stronger.
This is just a particular case, where the defectors win as long as there are many cooperators to spoil. When there are many defectors (or free riders) they will perform lower because a game between defectors will end up in a lower total outcome, compared to, say cooperator vs cooperator (or titForTat vs titForTat).
Analyzing the prisoner dilemma theory is beyond the goal of this post.

val it : (Player * int) list =
  [({Name = "cooperatorStrategy_4";
     StrategyInfo = {Name = "cooperatorStrategy";
                     Strategy = ;};}, 1208);
   ({Name = "cooperatorStrategy_2";
     StrategyInfo = {Name = "cooperatorStrategy";
                     Strategy = ;};}, 1210);
   ({Name = "cooperatorStrategy_0";
     StrategyInfo = {Name = "cooperatorStrategy";
                     Strategy = ;};}, 1216);
                     Strategy = ;};}, 1536);
   ({Name = "defectorStrategy_3";
     StrategyInfo = {Name = "defectorStrategy";
                     Strategy = ;};}, 1540);
   ({Name = "defectorStrategy_4";
     StrategyInfo = {Name = "defectorStrategy";
                     Strategy = ;};}, 1554);
   ({Name = "defectorStrategy_0";
     StrategyInfo = {Name = "defectorStrategy";
                     Strategy = ;};}, 1566);
   ({Name = "defectorStrategy_2";
     StrategyInfo = {Name = "defectorStrategy";
                     Strategy = ;};}, 1568)]

Future development:
- implementing evolution
- implementing real time chart visualization

Sunday, April 14, 2019

A free Orders System in F# (part 1)

I recently added to my github a new open source solution for managing orders in a restaurant.

This is a first post about the description of the product:

Main features:

1) managing ingredients, and categories of ingredients
2) managing courses, and categories
3) managing ingredients composing the courses (receipts)
4) collecting orders,
5) defining users roles,
6) managing variations of orders items (in term of add ons or drop off of ingredients)
7) managing price variations related to order items variations
8) printing orders by associating printer for course categories
9) displaying order items
10) managing payment by eventually subdividing the bill
11) print a fiscal cash drawer (by using an external software).

A walkthrough:

1) main menu:

many of those items are visible and usable only by the administrator.

2) manage ingredients:

Clicking on manage ingredients we have get this form to create a new category of ingredients, and create a new one and call it "vegetables".

After creating the new category, I have a button that allows me to select the category itself:

The category is "visible", but I can switch it to "invisible" by clicking the button "modifica visibilita'" (will be translated into "switch visibility).

I click the button of the category, and I can see all the existing items of the category (there is no one, yet), search, or create a new one. I do create a new one.

I am not going through all the options of this form. I just create a new ingredient with default values and call it "green salad".

So now in the ingredients->vegetables page I have this:

I skip all the description of the options related to "prices", "usages", and "load" for now.

Course categories works in similar way, and it is possible to specify the ingredients for each course as well.

Next post will be about collecting orders.
Anyway, I do have some video demo of an earlier version of the product:

Tuesday, December 11, 2018

Porting a simple toy app to Elmish

In the past I developed a toy app/kata (Animalquiz) for learning purposes. First version was Java, then I ported it to F#.

This post is about making the  F# version run under Elmish.

Roughly speaking, an Emish based application consists in a set of possible messages, a model to represent the current state of the application, and an update function that given a message and a model, returns a new model (and a list of other messages,  but I can skip this part and assume that this list will always be returned as empty, that is ok for my purposes).

My original AnimalQuiz was console based (also with a gtk# interface), and it was based on a sort of model-view-update patten, even if I wasn’t aware of it.

So I expect there will not be so much work to do to put it under Elmish.

First step is creating a project based on the Elmish-Fable template.
According to the documentation that you can find in
to install the Fable-Elmish-React template you need the following command:
dotnet new -i "Fable.Template.Elmish.React::*"

To create a new project:
dotnet new fable-elmish-react -n awesome

The template created contains three sample (sub)apps: 
  • The “Home” app which shows us a simple textbook where the content will be coped in a text area (using “onchange” property).
  • The classical counter app called “Counter sample”. 
  • The “About” which just shows some static text (which is just static text).

I want to add the AnimalQuiz as a fourth application, so what I'll do is:
  1. make a clone of one of them, and call the cloned app “AnimalQuiz”, 
  2. make the cloned app accessible from the outer menu.
  3. modify the cloned app, to  behave as the AnimalQuiz app.

The app I clone is the “Home” app, so I just copy the three file of it in a new folder called AnimalQuiz. In each module declaration I'll substitute "AnimalQuiz" to "Home".

I have to add the following rows in the in the project file awesome.fsproj, in that order,  to make sure they will be compiled:
<Compile Include="AnimalQuiz/Types.fs" />
<Compile Include="AnimalQuiz/View.fs" />
<Compile Include="AnimalQuiz/State.fs" />

Now the step 2: I want to make extra app reachable by the outer menu, so as follows there are the files that I have to change at it, and how I have to change them:
module App.Types: the message and the model will reference the message and the models of the sub apps:

Module Global (file Global.fs): I extend the Page discriminated union, and the toHash function:

Then I need to change the App.State module (only the row with some animalQuiz string are mine):

Last thing to do is modifying App.View module in two parts.
One is the definition of the menu:

Another one is the definition of the pageHtml internal to the root definition:

This is enough to make the new app visible and selectable from the outer menu.

Now is time to take a look to the actual app, that, until now, is just a copy of Home, but I'm going to change everything there.

The model is the following:

Those data are useful to manage an interaction between the user and the engine, but I am not going to explain all of them, with the exception of the CurrentState, which is of the type State, that describe the different states of the interaction with the user:

What follows are the messages:

The model include also a history of messages. The history of messages is useful because I can do any "replay n steps from the beginning" by applying n times the messages of the history from the initial state using the fold function.

For instance there is an "undo" that applyes the list of the messages from the initial state a nuber of times given by the length of the history minus one:

| (Undo,_) -> 
     let msgHistoryTruncated = model.MessageHistory |> List.take (List.length model.MessageHistory - 1)
     msgHistoryTruncated |> List.fold (fun (acc,_) x -> update x  acc   )  (initState,[])

repo is here

Wednesday, September 26, 2018

Transforming a nested F# list to Javascript using tail recursion

If I need some javascript in a Suave view, I can include a reference to an external javascript like in the following code:

script ["type","text/javascript"; "src","/externalJavascript.js"] []

Another way to insert javascript code is by adding the code directly by the Raw tag:

script [] [Raw("alert('hello');")]

I can use both way to pass parameters to the external javascript file:

script [] [Raw("var myVar = 123")];
script ["type","text/javascript"; "src","/externalJavascript.js"] []

In this way, the externalJavascript.js may access to the myVar variable as a global variable.

This can be a "hack" to pass parameters to the javascript.

The reason for doing it is being able to make the html page richer, avoiding "round trip" with the server. In this case I wanted to be able to  to add and remove dinamically some element to the options list, on the base of the element selected in another select option list.

However using this way to pass parameters, means generating the javascript code as a string.

An example is if I have a nested list in F#, as follows:

[(1,[(1,2M);(3,4M)]);(11,[(11,22M);(33,44M)] ) ]

and I want to transform in an equivalent javascript map:

new Map([[11, new Map([[11,22],[33,44],])],[1, new Map([[1,2],[3,4],])],]);

From the web page perspective, the key of the map (11) is the element that, when selected in the first select option list, will change the content of the second select option list, populating it with its value, which is a list with two pairs: (11,22), (33,44)

(as you can imagine, such data comes from a database, and is generated by a combination of map operations):
I tried to solve using regular expressions, but the way regular expressions changes from unix (vim) style and the libraries is annoying for me. So I decided that  a tail recursive function could be cleaner and better, so I come up with the following:

I'm sure there are cleaner ways to enrich the view, for instance using frameworks like Fable and Elmish, but I haven't found yet the time to try to figure out how to integrate them.

So at the moment, the solution is just using F# with Suave.IO (and Postgres), adding some "tricks" if I need to make the page more dynamic on the client side.

EDIT: instead of using a recursive function, I can just use the fold operator:
for instance the first inner function can be rewritten as follows:

let javascriptListPairs l = l |> List.fold (fun acc (x,y)  -> acc + "["+(string)x+","+(string)y+"],") ""

Friday, July 20, 2018

checkboxes with Suave.IO, using dotliquid tamplates

Using checkboxes with Suave.Io

The Suave.IO web library for F# adopts two ways of rendering html.

By using Suave.form/Suave.html the page is represented as a native F# list, which basically consists in html elements, or nodes, and forms which are defined by specific records. Invalid html page is impossible in this way because the syntax check is strict.

Suave.dotliquid instead adopts old fashion html text + some variable substitution at server side.

However, Suve.Form/Suave.html misses support for checkboxes yet.

We can't do the following stuff to render a checkbox form, whereas we can do if we used other supported types for html widget (see

Defining the form.

type UserEdit = {
    Enabled: bool
    CanVoidOrder: bool
    CanManageAllorders: bool
    CanChangeThePrices: bool

let userEdit: Form =
   Form ( [
            Checkbox ((fun f -> <@ f.Enabled @>), [])
            Checkbox ((fun f -> <@ f.CanVoidOrder @>), [])
            Checkbox ((fun f -> <@ f.CanManageAllorders @>), [])
            Checkbox ((fun f -> <@ f.CanChangeThePrices @>), [])

REnd the form in the ui:

       { Form = Form.userEdit
         Fieldsets =
             [ { Legend = "Modify user"
                 Fields =
                       { Label = "enabled"
                         Html = Checkbox (fun f -> <@ f.Enabled @>) ["value", true]  )
                       { Label = "can manage all orders"
                         Html = Checkbox (fun f -> <@ f.CanVoidOrder @>) ["value", true]  )
                       { Label = "can void order"
                         Html = Checkbox (fun f -> <@ f.CanManageAllorders @>)["value", true]  )
                       { Label = "can change the prices"
                         Html = Checkbox (fun f -> <@ f.CanChangeThePrices @>)["value", false]  )

         SubmitText = "modify" }

This is probably how it will be possible in the future, but is not possible yet. bool and chekbox are not supported.

So I needed dotliquid templating to overcome, where any html is valid, because it is actual html plain text code.

A recap of checkboxes in html:

<form method="post">
<input name="myName1" nbsp="" type="checkbox" />myValue1</input>
<input name="myName2" nbsp="" type="checkbox" />myValue2</input>
<input type="submit" update="" />

In posting this form, it evaluates myName1 to myValue1 if checked, and  myValue2 to myValue2  if checked.

So what I we can do to use dotliquid forms for checkboxes is using option types. I don't really care about the value passed, but only if they are passed or not. For that reason option types fit the purpose.

type UserEdit = {
    Enabled: string option
    CanVoidOrder: string option
    CanManageAllorders: string option
    CanChangeThePrices: string option

//wa can leave the following empty (no validators an so on)..
let userEdit: Form =
   Form ( [

So the code in App.fs would be like:

type modelForLiquid = {name: string} // how to pass parameters to the template, if needed

let manageUser (Db.user) =
choose [
     GET  >=>
          let o = {name = "yourname"}
"template.html") o
     POST >=>
          bindToForm Form.userEdit (fun form ->
              let ctx  = db.getContext()
              let isEnabled = form.Enabled.isSome
              let canVoidOrder = form.CanVoidOrder.isSome
              Db.UpdateUser user.UserId isEnabled canVoidOrder ... ctx


Something similar should be needed for radiobuttons.

What we need to be sure about is that we use POST rather than GET in the form, and how html pass the parameters. Basically they are a list of name value pairs.
The POST part of our code in the controller (App.fs usually) can handle them in a straightforward way as seen in the code above.

Can be good to know, just in case ;-)

Wednesday, March 22, 2017

criteri di priorità per backlog item, basati su misure di valore e costo

In questo post accenno ad un criterio di ordinamento per priorità di "product backlog item" considerando alcune possibili misure del valore e del costo, e la loro incertezza.


In metodi di organizzazione del lavoro di tipo "leggero", empirico  (definiti "agili" - come Scrum, Xp, Kanban) usati nello sviluppo di prodotti principalmente software, si ha un insieme chiamato "product backlog" costituito da "product backlog item" (p.b.i.) che specificano piccole funzionalità le quali, tutte insieme, una volta realizzate, costituiranno il prodotto intero.

Per fare un esempio, se il prodotto è un un word processor, si può avere tra le sue funzionalità, cioè tra i suoi p.b.i.:
- poter sottolineare,
- "" mettere in grassetto,
- "" creare elenchi numerati,
- "" giustificare il testo in vari modi,
- "" salvare e leggere in vari formati, e così via...

Questi metodi "leggeri" prevedono che il prodotto sia utilizzabile anche in ogni sua versione intermedia, parziale (cioè che implementi un sottoinsieme di p.b.i. rispetto al backlog).
Quindi è importante che i p.b.i. siano il più possibile indipendenti tra loro (non si dà il caso che per lavorare su uno bisogna prima averne completato un altro, anche se in alcuni casi è comunque inevitabile).

Un p.b.i. portato a termine, deve essere effettivamente rilasciabile, funzionante, usabile, testabile, e testato. Il test dovrebbe essere ripetibile in modo automatico, così da poterlo rieseguire rapidamente, per esempio per rilevare eventuali errori di regressione in successivi rilasci (nel caso nuove aggiunte compromettano funzionalità precedenti). Se i test non fossero automatici, sarebbe difficile fare piccoli rilasci per incrementare le funzionalità del prodotto, perché i test di regressione manuali si accumulerebbero, e rallenterebbero il tutto (a meno che non si sia in grado di affidarsi ad altri metodi rapidi per garantire la non regressione, tipo test massivi fatti magari da una certa fetta di utenti).

Un p.b.i. completato si chiama "running tested feature" (r.t.f.),  nel caso di un prodotto software.

Priorità per valore

In genere i p.b.i. su cui lavorare per prima, cioè per i rilasci delle prime iterazioni, sono scelti in base ad un ordine tale che quelli di valore maggiore (e costo minore, vedi sezione successiva) abbiano la priorità.

Il motivo dovrebbe essere ovvio, ma se non lo fosse, una giustificazione è la seguente.

Immaginiamo che si faccia il contrario, cioè che si portino a termine prima i p.b.i. più marginali, ininfluenti.
In tal caso il valore totale erogato nel corso di un certo tempo, e in modo particolare all'inizio del ciclo di vita, sarà minore del valore totale erogabile nello stesso tempo. Allora i finanziatori del progetto potrebbero percepire che questo abbia uno scarso valore nel complesso, e quindi decidere di chiuderlo.

Dunque è meglio selezionare gli item di maggiore valore per prima.

Per "misurare" questo valore occorre fare dei ragionamenti diversi caso per caso.
Faccio un esempio:

Diciamo che il prodotto è un portale, e vogliamo che gli utenti possano interagire se "riconosciuti", per esempio tramite autenticazione da parte di un provider esterno in cui abbiano già un account, che può essere un social network come Google Plus o Facebook.

Più utenti si attirano e più si genera valore (per esempio attraverso l'aumento del numero atteso di click sugli ad pubblicitari).
Inoltre un utente autenticato, quindi "riconosciuto", porta a maggiori probabilità di click sugli ad perché questi sono più mirati.

In una valutazione a grana grossa, si può dire che la scelta che genera più valore è semplicemente quella dell'autenticazione tramite il social che ha un maggior numero di utenti iscritti
Questa valutazione la vedo accettabile  se assumo che:
. la propensione a cliccare un ad pubblicitario da parte di un particolare utente sia indipendente dal tipo di social network in cui abbia un account
. la probabilità di "atterrare" sul nostro portale e decidere di interagirvi sia indipendente dal social network a cui si appartiene.
(se ho motivo di ritenere che queste assunzioni siano lontane dal vero, devo fare un ragionamento più complicato, che include certe correlazioni).

La scelta più razionale è scegliere prima di lavorare sul b.p.i. che ci aspettiamo generi più valore (a parità di costo di implementazione).

Inoltre questa scelta, non solo è preferibile, ma magari genera un tale numero di utenti da rendere praticamente inutile cercarne di altri implementando poi l'autenticazione tramite altri social network (se non esistono altri criteri di "misura del valore" che inducano comunque a farlo, come motivi di equità o raccomandazioni da parte di autorità antitrust etc...).

Come conclusione di questa piccola analisi:
. è utile scegliere prima i p.b.i. che generino un maggior valore (anche rapportato al costo, come dirò dopo)
. serve un criterio per misurare questo valore (che non sempre è economico, o almeno non direttamente)
. il criterio di misura deve esser accurato quanto basta. Per esempio nel caso in questione, non serve sapere quanti utenti ha l'uno o l'altro social network, basta sapere quale dei due ne ha di più
. il modello in base al quale misuro questo valore deve essere semplice, se so che un modello più complicato (che tiene conto di eventuali correlazioni) aggiungerebbe una accuratezza di cui posso fare a meno.

Tener conto delle correlazioni significa assumere che il maggior numero di potenziali click sugli ad lo misuro non solo in base al numero di utenti ma anche alla maggiore o minore propensione a cliccare gli ad dell'uno o dell'altro, ovvero dal tipo di social network da cui provengono. Così la misura sarebbe stata più complicata, ma più accurata.

Non dovrebbe valere solo il beneficio, ma anche il costo nel criterio di scelta della priorità.

Priorità per costo

Per costo si intende sostanzialmente il numero di giornate di lavoro, ovvero il tempo che pensiamo ci vorrà.

Se per me (per il team di lavoro) è più difficile, complicato, lungo implementare l'autenticazione Google Plus rispetto a Facebook, mentre il valore è equivalente, allora è razionale scegliere Facebook (a parità di valore).

Tra l'altro, se scegliamo il p.b.i. "autenticazione tramite Facebook" che è più rapido, allora questo inizierà a produrre valore in tempi più brevi, sarà costato di meno, e forse genererà valore anche di tipo informativo (per esempio consentirà di verificare quanto aumenteranno i click sugli ad, e se varrà la pena cercare di aumentarli, implementando poi anche un altro p.b.i. simile).

Unendo insieme i due ragionamenti fatti, la priorità dipende da un confronto tra i rapporti valore/costo.

In definitiva i criteri razionali saranno del tipo: scegliere A se probabilmente ha un miglior rapporto valore costo rispetto al terminare B.

Ma si tratta di un confronto tra valori ipotetici.
Sappiamo che potrebbe rivelarsi errato (era meglio scegliere B piuttosto che A) ma questo non potremmo mai verificarlo se non, magari, a posteriori. Però è possibile attribuire un grado di confidenza alla valutazione che facciamo.

Stimatori calibrati

Possiamo dare un grado di fiducia nella stima del confronto (maggiore o minore) tra due valori non noti.

Per esempio 50% significa assoluta mancanza di confidenza: esprimersi in merito per noi è come tirare una moneta.
100% significa assoluta certezza.

Uno "stimatore calibrato" è chi sia in grado di dare un grado di fiducia a ciò su cui si esprime (tra due scelte alternative) che corrisponda alla probabilità di avere ragione (usando un criterio di probabilità "soggettivo").

Quindi se lo stimatore calibrato sostiene che ne è sicuro al 60%, allora la probabilità sarà del 60%, o meglio - siccome parliamo di probabilità soggettive - sarà conveniente, rispetto alle conoscenze che ha lo stimatore, una scommessa per cui la vincita corrisponda ad almeno 10/6 della somma giocata. (vedi "gioco equo")

Diventare uno "stimatore calibrato" è una capacità che si può imparare.

In sostanza lo stimatore calibrato non è chi abbia un alto grado di fiducia in una scelta tra due possibilità, ma chi sappia far coincidere tale grado di fiducia con la probabilità di aver ragione (edit: chi, sulla base di criteri razionali dell'agente giocatore, sia disposto a fare una scommessa con ammontare della vincita non inferiore a quella equa rispetto al livello di fiducia espresso).

(per estensione poi il concetto di stimatore calibrato si applica anche alla "stima" di valori puntuali, dove si tratta di individuare "intervalli di confidenza del 90%", ma questo è un approfondimento a parte).

I dubbi su questo eventuale modello decisionale per la priorità, come descritti qui, sono:
- gli esempi presentati sono semplici per motivi di comunicazione, ma certi casi concreti possono essere ben più complicati.
- nell'esempio ho trattato i confronti tra valori e costi separatamente, evitando di mostrare la decisione basata sul confronto dei rapporti tra i due (sempre per evitare di complicare troppo il ragionamento)
- ultimo, ma non per importanza, parliamo di sistemi che reagiscono alle previsioni che lo riguardano: misurare il valore di una cosa come il tempo che ci metterò per fare una cosa, ne altera il valore stesso, e non è detto che sia un bene (stime ottimistiche possono indurre ad una certa "fretta" che poi incide negativamente sulla qualità). 
Questo aspetto in parte è comunque mitigato dal fatto che non si tratta di "previsioni puntuali", ma basate su un confronto, cioè
ho affermato che ci si basa sul fatto che A < B, senza dover dire quanto misura A né quanto misura B in termini numerici di qualsiasi tipo.


Un modello di scelta razionale basata su "stime calibrate" nel confronto tra p.b.i. può essere in grado di orientare certe scelte di priorità nell'ambito di metodi di sviluppo/lavoro/progetto cosiddetti "agili".

rif. How To Measure Anything - Douglas W. Hubbard
gioco equo:

Sunday, October 9, 2016

Simple decision trees using xml in F# and Fsharp.Data.Xsd package

This post is about new xml based "Open" and "Save" features, and is the follow up of my latest post about "animal quiz" game
 ( The "game" is a simple "dialog based yes-no decision tree builder" based on console or on gtk (enabled by the "gui" parameter on command line) written in F# (under Mac Os X using Mac/Xamarin/Visual Studio Code+Ionide).

Sources are on github:

Here I share some ideas about the solution I implemented for those "Open" and "Save" features.

I used an Xml/Xsd  package available via nuget PM> Install-Package FSharp.Data.Xsd

(webpage )

For me a convenient way to represent the tree in Xml for me is represented by the following examples.

Single node decision tree containing just one element


A two leaves decision tree with a single yes-no question on the root to distinguish those two leaves (i.e. single animal) nodes:

        is it big?

The following xml schema can validate the previous instances (and more of course, that I verified by some NUnit based tests )

<xs:schema xmlns:xs="" elementFormDefault="qualified"
    <xs:element name="node">
                    <xs:element name="animal" type="xs:string"/>
                        <xs:element name="question" type="xs:string"/>
                        <xs:element name="yesBranch">
                                    <xs:element ref="node"/>
                        <xs:element name="noBranch">
                                    <xs:element ref="node"/>

(I don't know if this implementation is the simplest possible, but I know that it works)

According to this schema, a node is a sequence of one of the two choices:
a single element named animal, or a sequence of following three element:
-a question (to distinguish categories of animals by yes or not)
-a "yesBranch" (which contains the subtree related to the "yes" answer to that question)
- a "noBranch" (which contains the subtree related to the "no" answer to that question

yesBranch and noBranch of course use recursivity so they contain again the "node" element, which is the root of this xml type.

I need to wrap xml tree from and to the internal representation of the tree. They   are logically equivalent (though field names may slightly differ from the corresponding xml elements, and that is still ok for me):

type KnowledgeTree = AnimalName of string | SubTree of Tree
and Tree = {QuestionstringYesBranchKnowledgeTreeNoBranchKnowledgeTree}

Wrapping internal tree representation to the corresponding xml string is based on producing plain xml text recursively:

let rec treeToXml tree =
    match tree with 
        | AnimalName name -> "<node><animal>" + name + "</animal></node>"
        | SubTree {Question=questionYesBranch=yBranchNoBranch=nBranch } ->  
           "<node><question>" + question + "</question>" + "<yesBranch>" + treeToXml yBranch + "</yesBranch><noBranch>" + treeToXml nBranch + "</noBranch></node>"

(this function does not depend on the Schema: if I want change the schema, I need to change treeToXml accordingly, few lines of code anyway)

To wrap the xml representation to an object, I followed the official documentation which introduces a XmlProvider type which needs to see the schema.

For instance I have

 type KnowledgeBaseXmlSchema = XmlProvider<Schema="""
        <xs:schema xmlns:xs=""
            elementFormDefault="qualified" attributeFormDefault="unqualified">
            <xs:element name = "node">


and then use the Parse method from the "KnowledgeBaseXmlSchema" as follows:

let xmlWrapped = KnowlegeBaseXmlSchema.Parse """<node>

Now the xmlWrapped object is coherent, in term of its fields and their types, with the xml datatype as defined by the schema. Particularly optional nodes are represented by option types.

Let's see go a little bit through this:
The Animal got from the KnowledgeBaseSchema.Parse is option because it follows the element in the schema which says it is optional as well. The editor Visual Studio Code+Ionide help detects statically this kind of things.

The other way around is true. If an element is mandatory, it is not "wrapped" into an option anymore:
so in the following lines of code, the myNode is not option, but its type is
XmlProvider<...>.Node,  and in fact is a mandatory element according to the xml schema.

All that said, let's take a look to the xmlToTree function:

let rec xmlToTree (tree:KnowledgeBaseXmlSchema.Node) =      
    match tree.Animal with
    | Some x -> AnimalName x
    | None ->  match (tree.Question,tree.YesBranch,tree.NoBranch) with 
      | (Some y1,Some y2,Some y3) -> SubTree {Question=y1YesBranch=xmlToTree y2.Node ; NoBranch = xmlToTree y3.Node }
      | _ -> failwith "error wrapping xml tree"  

I had to specify the type (KnowledgeBaseXmlSchema.Node) of the parameter, tree, because the type inferences does not work in some cases (and this is one of these cases)

(such thing is not terrible, because in the rare case type inferences won't work, I can just inspect the parameter type we are going to pass to it and then modify the function signature accordingly)

As I mentioned, the "Animal" is an instance of an option type so I have to pattern match it by the "Some X" syntax, and if it the match ha success, then the corresponding internal tree can be simply instantiated by:


(single node tree)

If the root is not an animal (leaf node), then it should match the "None" part of the pattern matching instead, and in that case I assume that there must be a sequence of the following elements: a Question, a YesBranch and a Nobranch which are options as well.
So I try to match them as a triplet like (Some y1, Some y2, Some y3) and simply build a "SubTree" represented by the Question and the recursive call of the same function to the yesBranch and noBranch subnodes.
(note that this implementation is recursive, but it is not tail-recursive)

(Nunit tests are available in this file on github if needed to play more with what I share in this post

Conclusion is:
- options types are useful
- the fact that optional nodes are represented by option types by using an xml/xsd processing library is very useful
-kudos to static analysis tool provide by editors. They helps checking those things before compiling or testing.

About possible new feature I may add to this toy project:
-adding scrollbars on the main window (to easily visualize trees when they will grow)
-indenting xml output files, to make them more human readable
-better error handling in xml processing, and asking confirmation in case of re-writing existing file, for obvious reasons.

Thanks for reading. Enjoy.