No processo de aprendizagem de linguagens funcionais por vezes ficamos abismados com a simplicidade com que são abordados alguns algoritmos que tipicamente damos como complexos. Aqui há uns dias estava a resolver uns exercícios de Lisp quando dei por mim a observar a implementação de um QuickSort nesta linguagem:
(defun partition (fun array)
(list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
(if (null array) nil
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
(retirado do artigo na wikipedia)
Assim de repente isto tem um aspecto bem mais simples do que as implementações comuns em C#, Java ou qualquer outra linguagem orientada a objectos. No fundo, o conceito do algoritmo diz para escolher um elemento e juntar a lista ordenada de todos os menores com o elemento e com a lista ordenada de todos os maiores. Simples, não? Então e porque não fazer o mesmo em C#? É possível implementar um QuickSort apenas com uma linha de código? Uma primeira tentativa:
public static IEnumerable<int> LinqIntQuickSort(IEnumerable<int> x)
{
return x.Count() <= 1
? x
: LinqIntQuickSort(x.Skip(1).Where(z => z <= x.First()))
.Concat(new List<int> { x.First() })
.Concat(LinqIntQuickSort(x.Skip(1).Where(z => z > x.First())));
}
E não é que funciona? Ok, mas apenas com números. Generalizando obtemos algo do género:
public static IEnumerable<T> LinqGenericQuickSort<T>(IEnumerable<T> x, Func<T, T, int> fnCompare)
{
return x.Count() <= 1
? x
: LinqGenericQuickSort(x.Skip(1)
.Where(z => fnCompare(z, x.First()) <= 0), fnCompare)
.Concat(new List<T> { x.First() })
.Concat(LinqGenericQuickSort(x.Skip(1)
.Where(z => fnCompare(z, x.First()) > 0), fnCompare));
}
Que, para a mesma lista de inteiros, pode ser chamado simplesmente assim:
sortedList = LinqGenericQuickSort(unsortedList, (x, y) => x - y);
Já agora, se quisermos apenas utilizar uma expressão lambda:
Func<IEnumerable<int>, Func<int, int, int>, IEnumerable<int>> fn = null;
fn = (l1, fnCompare) => l1.Count() <= 1
? l1
: fn(l1.Skip(1).Where(z => fnCompare(z, l1.First()) <= 0), fnCompare)
.Concat(new List<int> { l1.First() })
.Concat(fn(l1.Skip(1).Where(z => fnCompare(z, l1.First()) > 0), fnCompare));
sortedList = fn(list, (x, y) => x - y);
Atenção que este exemplo apenas serve para demonstrar potencialidades do Linq e expressões lambda, é muito ineficiente quando comparado com as implementações tradicionais.
