esercizio-fp.md

Esercizio

Option<T> := None | Some T
List<T> := Nil | Append List<T> T
Tree<T> := Leaf T | Branch List<Tree<T>>

Si possono anche assumere funzioni comode come get :: (List<T>, Int) -> T ed eventuali altre funzioni ragionevoli.

Altre cose di utlity

UID := Int
Mark := Start UID | End UID

Segnatura della funzione da scrivere

treeify :: (list: List<T>, marks: [(Int, Mark)]) -> Option<Tree<T>>

In particolare le posizioni dei vari "mark" sono ordinate, ovvero (notazione permettendo) l'array marks.*.0 è ordinato.

Se la lista di marks è invalida ritornare None, ad esempio se un nuovo blocco inizia e non viene chiuso prima del genitore (situazione in stile: ( [ ) ]).

Esempi di Output

treeify "abcabc" []
 => Branch [
        Leaf 'a', Leaf 'b', Leaf 'c', Leaf 'a', Leaf 'b', Leaf 'c'
    ]

treeify "abcabc" [(0, Start 1), (6, End 1)]
 => Branch [
        Branch [Leaf 'a', Leaf 'b', Leaf 'c', Leaf 'a', Leaf 'b', Leaf 'c']
    ]

treeify "abcabc" [(0, Start 1), (1, Start 2), (3, End 2), (3, Start 3), (5, End 3), (6, End 1)]
 => Branch [
        Branch [Leaf 'a', Branch [Leaf 'b', Leaf 'c'], Branch [Leaf 'a', Leaf 'b'], Leaf 'c']
    ]