Anamorfismi, Fibonacci e C#
Qualche tempo fa abbiamo visto qui come costruire la successione di Fibonacci sfruttando gli iteratori e l'interfaccia IEnumerable<T>. Come possiamo generalizzare questo approccio?
Quello che abbiamo fatto è stato generare a partire da un seme una successione di valori finché una certa condizione non diventasse falsa.
Questo procedimento non è nuovo ed è stato applicato più volte, rimanendo nel mondo .NET basta guardare alla funzione Seq.Unfold di F#. Per chi volesse approfondire gli aspetti teorici di questo problema rimandiamo alla pagina wikipedia sugli anamorfismi.
Idealmente la funzione andrebbe aggiunta alla classe statica Enumerable ma questo ovviamente non è possibile quindi la metteremo in una classe statica apposita.
Prendendo come riferimento l'articolo wikipedia implementeremo la prima versione della funzione che chiameremo Unfold seguendo l'esempio di F#. La prima versione prevede la presenza di 3 parametri in ingresso:
- Un valore iniziale
- Una funzione generatrice
- Una funzione che restituisce un booleano e che rappresenta la condizione da testare prima di ogni generazione
Nonostante tutto l'implementazione della funzione è molto semplice
public static class Ext { public static IEnumerable<T> Unfold<T, U>(Func<U, Tuple<T, U>> generate, Func<U, bool> finished, U seed) { while (!finished(seed)) { var next = generate(seed); yield return next.Item1; seed = next.Item2; } } }
Il metodo risultante è generico con due Type Parameters, la parte più complicata è sicuramente la funzione generatrice che ha il compito di generare il valore da restituire e il seme dell'iterazione successiva.
Per chiarezza riproduciamo gli esempi della funzione Seq.Unfold presenti su MSDN. Come primo esempio vediamo come generare i numeri da 0 a 20:
Func<int, Tuple<int,int>> generate = p => new Tuple<int,int>(p,p+1); Func<int,bool> finished = p => p > 20; foreach(var item in Ext.Unfold(generate, finished, 0)) { Console.WriteLine(item); }
La funzione generatrice restituisce come valore l'intero corrispondente a seed e crea il nuovo seed sommando 1. Vediamo invece come generare i numeri di Fibonacci. La questione purtroppo si complica molto in quanto il seme e quindi lo stato da passare di volta in volta al metodo è una coppia di valori (i due che vanno sommati). Quindi il seed è definito come:
var seed = new Tuple<int,int>(0,1);
Il test di conclusione della generazione è ancora abbastanza semplice:
Func<Tuple<int, int>, bool> finished = p => p.Item2 > 200;
Il vero mostro è la funzione generatrice che data una tupla di interi genera un'altra tupla che contiene un intero e una tupla di interi
Func<Tuple<int,int>,Tuple<int,Tuple<int,int>>> generate = p => new Tuple<int,Tuple<int,int>>(p.Item2,new Tuple<int,int>(p.Item2, p.Item1+p.Item2));
Il codice per calcolare e stampare a video i numeri di Fibonacci è
var seed = new Tuple<int,int>(0,1); Func<Tuple<int, int>, bool> finished = p => p.Item2 > 200; Func<Tuple<int,int>,Tuple<int,Tuple<int,int>>> generate = p => new Tuple<int,Tuple<int,int>>(p.Item2,new Tuple<int,int>(p.Item2, p.Item1+p.Item2)); foreach (var item in Ext.Unfold(generate, finished, seed)) { Console.WriteLine(item); }
Ci rendiamo perfettamente conto che l'usabilità di questo metodo è molto bassa, il problema fondamentale è la presenza di tipi molto complessi. Infatti questo tipo di funzionalità, come si capisce anche dalle risorse che abbiamo linkato, è molto spesso legata ad un sistema di type inference più potente di quello di C# come ad esempio quello di F#. Il team di sviluppo di C# sta pensando di aggiungere un modo più rapido e fruibile di utilizzare e istanziare le tuple, se sarà così potremo forse riscrivere e utilizzare più comodamente il metodo Unfold!