Produzindo código mais elegante com combinators (em C#)

Olá pessoal. Tudo certo?!

No post de hoje, mostro como implementar combinators em C#.

Combinators são “higher-order functions” que usam somente funções e outros combinators para entregar novas funcionalidades. A idéia central é escrever funções muito simples que, mais tarde, são combinadas para gerar novas funções mais poderosas.

Aprender a utilizar adequadamente combinators permite a geração de códigos mais elegantes, com menos duplicação e melhor performance.

Naturalmente, não pretendo esgotar o assunto. Vou escrever outros posts mostrando mais aplicações práticas para o conceito. Entretanto, considero que os exemplos que mostro hoje são suficientes para “despertar” alguma criatividade.

Como de costume, o código-fonte está integralmente disponível

Código inicial

Para ilustrar o conceito de hoje, escolhi fazer uma implementação simples (recursiva) de Fibonacci. Observe:

public void Run()
{
	Console.WriteLine("Starting...");
	var f30 = Fibonacci(30);
	var f35 = Fibonacci(35);
	var f40 = Fibonacci(40);
	var f45 = Fibonacci(45);
	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

public int Fibonacci(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	return Fibonacci(n-1) + Fibonacci(n - 2);
}

O que esse código faz?! Basicamente, calcula o valor de alguns elementos da série de Fibonacci apresentando o resultado no final.

Alguma dúvida?! Acho que não.

Considere, agora, essa versão modificada:

public void Run2()
{
	Func<int, int> fibonacci = Fibonacci;
	
	Console.WriteLine("Starting...");
	var f30 = fibonacci(30);
	var f35 = fibonacci(35);
	var f40 = fibonacci(40);
	var f45 = fibonacci(45);
	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

Eis algo muito importante. C# trata código como “dado”. Ou seja, podemos atribuir facilmente um método como valor para uma variável e, depois disso, usar essa variável (delegate) para evocar o método.

Eis que surge a oportunidade de usar combinators

O que você faria para imprimir, em cada execução do método de Fibonacci, o valor que foi calculado?! Pensou em algo assim?

public void Run2()
{
	Func<int, int> fibonacci = Fibonacci;
	
	Console.WriteLine("Starting...");
	var f30 = fibonacci(30);
	Console.WriteLine("Input: {0}  Result: {1}", 30, f30);

	var f35 = fibonacci(35);
	Console.WriteLine("Input: {0}  Result: {1}", 35, f35);

	var f40 = fibonacci(40);
	Console.WriteLine("Input: {0}  Result: {1}", 40, f40);

	var f45 = fibonacci(45);
	Console.WriteLine("Input: {0}  Result: {1}", 45, f45);

	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

Ruim, não?!

O problema que temos aqui é a repetição da lógica e o claro aumento da quantidade de linhas no método. Além disso, aumentam as chances de existirem erros “copy/paste” (sabe do que estou falando, não?)

Para resolver isso, usamos um combinator. Vamos escrever o primeiro

public static class Combinators
{
	public static Func<T, TResult> Print<T, TResult>(Func<T, TResult> func)
	{
		return (input) =>
		{
			var result = func(input);
			Console.WriteLine("Input: {0}  Result: {1}", input, result);
			return result;
		};
	}
}	

O método Print é um combinator. Ou seja, um high-order function que “amplia” a funcionalidade de outra função (passada como parâmetro).

Agora, vamos escrever uma versão decente do código que calcula os valores de alguns elementos de Fibonacci imprimindo os valores na medida em que são calculados.

public void Run3()
{
	Func<int, int> fibonacci = Combinators.Print<int, int>(Fibonacci);
	
	Console.WriteLine("Starting...");
	var f30 = fibonacci(30);
	var f35 = fibonacci(35);
	var f40 = fibonacci(40);
	var f45 = fibonacci(45);
	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

Bem melhor, não?! Perceba que essa versão é “quase idêntica” a original. Ou seja, não corrompemos nosso código e introduzimos novas características (ampliando a função armazenada em fibonacci).

Um combinator para “controlar o tempo”

Caso tenha implementado, alguma vez, a abordagem recursiva de Fibonacci, sabe que quanto mais alto for o elemento que desejamos descobrir o valor, mais tempo é necessário para computação.

Como você faria para medir o tempo de cada execução do método?! Espero que esteja pensando em combinators…

public static class Combinators
{
	public static Func<T, TResult> Time<T, TResult>(Func<T, TResult> func)
	{
		return (input) =>
		{
			var before = DateTime.Now;
			var result = func(input);
			Console.WriteLine("Time to this input: {0}", DateTime.Now - before);
			return result;
		};
	}
}

Esse combinator monitora o tempo necessário para execução do método que lhe é atribuído. Observe:

public void Run4()
{
	Func<int, int> fibonacci = Combinators.Time<int, int>( 
		Combinators.Print<int, int>(Fibonacci)
	    );
	
	Console.WriteLine("Starting...");
	var f30 = fibonacci(30);
	var f35 = fibonacci(35);
	var f40 = fibonacci(40);
	var f45 = fibonacci(45);
	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

Pronto! Agora nossa “fibonacci” calcula o valor de um elemento, imprime o resultado na tela e, ainda, registra/exibe o tempo total.

Um pouco de memoization

Como já mostrei em posts anteriores, uma técnica comum para melhorar a performance de alguns códigos é “memorizar” resultados de computações anteriores evitando que processamento repetido seja executado. Essa técnica é conhecida como “Memoization” (consulte outros posts tratando desse tema).

Aqui um combinator para esse propósito:

public static class Combinators
{
	public static Func<T, TResult> Memoize<T, TResult>(Func<T, TResult> func)
	{
		var memo = new Dictionary<T, TResult>();
		
		return (input) =>
		{
			if (memo.ContainsKey(input))
			{
				return memo[input];
			}
			var result = func(input);
			memo.Add(input, result);
			return result;
		};
	}
}

Infelizmente, devido a natureza recursiva do Fibonacci, a utilização desse combinator não é trivial. Mas, é possível…

class Holder<T>
{
	public T Value { get; set; }
}

public void Run5()
{
	var holder = new Holder<Func<int, int>>();
	
	Func<int, int> fibonacci = (input) =>
		{
			if (input == 0) return 0;
			if (input == 1) return 1;
			return holder.Value(input - 1) + holder.Value(input - 2);
		};
	
	holder.Value = Combinators.Memoize<int, int>(fibonacci);
	
	fibonacci = Combinators.Print<int, int>(
		Combinators.Time<int, int>(holder.Value)
		);

	Console.WriteLine("Starting...");
	var f30 = fibonacci(30);
	var f35 = fibonacci(35);
	var f40 = fibonacci(40);
	var f45 = fibonacci(45);
	Console.WriteLine("Results: {0}, {1}, {2}, {3}", f30, f35, f40, f45);
	Console.WriteLine("Done!");
}

Bonito, não?! O ponto a destacar é que não “contaminamos” a lógica do fibonacci com memoization. Apenas, “combinamos”!

Era isso!