16 junho, 2012 0 Comentários AUTOR: elemarjr CATEGORIAS: Sem categoria Tags:, ,

Haskell para programadores C# – parte 7 – Higher-order functions

Tempo de leitura: 2 minutos

Olá pessoal. Tudo certo?!

Hoje falaremos sobre Higher-order functions. Elas permitem que alguns patterns de execução sejam implementados de forma mais elegante, como funções.

Como sempre, para facilitar o entendimento, tentarei construir código em C# com funcionalidade semelhante.

Se você está chegando agora, considere ver os outros posts dessa série.

O que são Higher-order functions?!

Higher-order functions são funções que (1) recebem funções em seus argumentos; ou (2) retornam funções.

Considere o seguinte código em C#:

var teenagers = people.Where(person => person.Age >= 13 && person.Age <= 19);
&#91;/sourcecode&#93;
</pre>
</div>

<p>Nesse código, <strong><em>Where </em></strong>é uma Higher-order function pois recebe uma função (expressão lambda) como argumento.</p>

<p>Pegou a idéia!?</p>

<h2>Higher-order functions são um conceito comum em Haskell</h2>

<p>Considere o seguinte código em Haskell:</p>

<p>
  <div style="margin:0;display:inline;float:none;padding:0;" id="scid:C89E2BDB-ADD3-4f7a-9810-1B7EACF446C1:ca3b4e13-5ed8-4f8b-909c-876ca72714c8" class="wlWriterEditableSmartContent"><pre style="white-space:normal;">

add a b = a + b

Como já expliquei em posts anteriores. Esse código equivale a:

add = a -> b -> a + b

Que escrito em C#, seria assim:

Func<int, Func<int, int>> add = a => b => a + b;

Logo, Add é uma Higher-Order Function, pois, como pode perceber, ela retorna uma função.

Um exemplo simples

Considere a seguinte Higher-order function.

Em Haskell:

twice :: (a -> a) -> a -> a
twice f x = f (f x)

Como pode ver, no tipo, trata-se de uma função que: (1) espera uma função como primeiro argumento, (2) espera um segundo argumento qualquer [generic] e (3) retorna o um valor do mesmo tipo que seu segundo argumento. Trata-se de uma Higher-order function.

Em C#:

static T Twice<T>(Func<T, T> f, T x)
{
    return f(f(x));
}

Executando:

image

Mesmo código em C#?

var result1 = Twice(a => a * 2, 5);
var result2 = Twice(a => a + 1, 1);

map/Select

Haskell define funções poderosas utilizando o conceito de High-Order Functions. Muitas dessas funções têm equivalente em LINQ.

Comecemos com a função map . Ela faz parte das funções built-in do Haskell, mas, poderia ser definida assim:

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs&#93;
&#91;/sourcecode&#93;
</pre>
</div>

<p>O equivalente dela, em C#, seria a função <strong><em>Select </em></strong>do Linq.</p>

<p>&#160;<a href="http://elemarjr.files.wordpress.com/2012/06/image25.png"><img style="background-image:none;border-bottom:0;border-left:0;padding-left:0;padding-right:0;display:block;float:none;margin-left:auto;border-top:0;margin-right:auto;border-right:0;padding-top:0;" title="image" border="0" alt="image" src="http://elemarjr.files.wordpress.com/2012/06/image_thumb25.png" width="554" height="121" /></a></p>



<p>Esse exemplo, em C#</p>

<div style="margin:0;display:inline;float:none;padding:0;" id="scid:C89E2BDB-ADD3-4f7a-9810-1B7EACF446C1:bb3182e5-53c5-4da7-b70b-ce4d7f7af113" class="wlWriterEditableSmartContent"><pre style="white-space:normal;">

Enumerable.Range(1, 5).Select(a => a + 1);

Mais alguns exemplos:

image

Comprimento de uma lista?!

Em Haskell:

length' :: [a] -> Int
length' xs = sum (map (_ -> 1) xs)

Em C#:

static int Length<T>(IEnumerable<T> source)
{
    return source.Select(a => 1).Sum();
}

filter/Where

Outra Higher-order function “built-in” em Haskell, extremamente útil, é filter. Veja sua definição:

filter :: (a -> Bool) -> [a] -> a
filter p xs = [x | x <- xs, p x&#93;
&#91;/sourcecode&#93;
</pre>
</div>

<p>O equivalente dela, em C#, seria a função <strong><em>Where </em></strong>do Linq</p>

<p>Veja alguns exemplos de uso:</p>

<p><a href="http://elemarjr.files.wordpress.com/2012/06/image27.png"><img style="background-image:none;border-bottom:0;border-left:0;padding-left:0;padding-right:0;display:block;float:none;margin-left:auto;border-top:0;margin-right:auto;border-right:0;padding-top:0;" title="image" border="0" alt="image" src="http://elemarjr.files.wordpress.com/2012/06/image_thumb27.png" width="559" height="164" /></a></p>

<p>Em C#:</p>

<div style="margin:0;display:inline;float:none;padding:0;" id="scid:C89E2BDB-ADD3-4f7a-9810-1B7EACF446C1:4f996088-38a3-4fac-bab1-691838196040" class="wlWriterEditableSmartContent"><pre style="white-space:normal;">

Enumerable.Range(1, 10).Where(x => x%2 == 0);
Enumerable.Range(1, 10).Where(x => x > 5);
new string("String With Spaces".Where(c => c != ' ').ToArray());

all, any, takeWhile, dropWhile

Mais algumas higher-order functions “built-in” em Haskell:

all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs&#93;

any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs&#93;

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p (x:xs)
	| p x = x : (takeWhile p xs)
	| otherwise = []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p (x:xs)
	| p x = dropWhile p xs
	| otherwise = xs

Exemplos de uso:

image

 

LINQ oferece implementações para todas essas funções. São elas: All , Any, TakeWhile e SkipWhile.

Deixo para você o desafio de tentar reescrever essas funções.

foldr/Aggregate

Outra Higher-order function, extremamente poderosa, definida em Haskell e com equivalente em LINQ é foldr. Eis sua definição:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

Trata-se de uma função complexa, mas com aplicação muito comum.

Repare nesses exemplos inpirados no post anterior:

product' :: Num a => [a] -> a
product' [] = 1
product' (n:ns) = n * product' ns

sum' :: Num a => [a] -> a
sum' [] = 0
sum' (n:ns) = n + sum' ns

and' :: [Bool] -> Bool
and' [] = True
and' (x:xs) = x && and' xs

or' :: [Bool] -> Bool
or' [] = False
or' (x:xs) = x || and' xs

Perceba como há um pattern em todas essas recursões. foldr simplifica a aplicação desse pattern. Usando foldr, podemos reescrever todas essas funções assim:

product' :: Num a => [a] -> a
product'= foldr (*) 1

sum' :: Num a => [a] -> a
sum'= foldr (+) 0

and' :: [Bool] -> Bool
and'= foldr (&&) True

or' :: [Bool] -> Bool
or'= foldr (||) False

Coisa linda, operadores em Haskell serem funções. Não acha?!

O equivalente em LINQ para foldr é a função Aggregate. Veja:

Func<IEnumerable<int>, int> sum = xs => xs.Aggregate(0, (a, b) => a + b);
Func<IEnumerable<int>, int> product = xs => xs.Aggregate(1, (a, b) => a * b);
Func<IEnumerable<bool>, bool> and = xs => xs.Aggregate(true, (a, b) => a && b);
Func<IEnumerable<bool>, bool> or = xs => xs.Aggregate(false, (a, b) => a || b);

Era isso.