Programação Funcional em Haskell

Programação Funcional em Haskell

(Parte 5 de 9)

not True = False not False = True

De forma similar, as funcoes or (disjuncao) e and (conjuncao) tambem podem ser definidas por enumeracao, da seguinte maneira:

or (False, False) = False and (False, False) = False or (False, True) = True e and (False, True) = False or (True, False) = True and (True, False) = False or (True, True) = True and (True, True) = True

As definicoes de funcoes por intencionalidade serao vistas a seguir, em mais detalhes, uma vez que esta e a forma mais usual de apresentacao, dadas as varias formas como elas se apresentam.

Definicao de funcoes por composicao

Nao ed ifıcil entender que as definicoes de funcoes por enumeracao sot em sentido se o domınio eoc ontra-domınio forem finitos e de cardinalidade pequena. A grande maioria das funcoes nao pode ser definida desta forma. Uma alternativa e definir as funcoes pela composicao de outras funcoes ja definidas. Como exemplo, a funcao implica pode ser definida da seguinte forma:

implica (x, y) = or (not x, y)

Neste caso, e necessario saber como as funcoes a serem compostas sao aplicadas. A aplicacao de uma funcao se torna simplesmente um processo de substituicao das funcoes primitivas. Por exemplo, para avaliar a funcao implica (False, True) e necessario apenas fazer a substituicao dos argumentos pelas aplicacoes das funcoes primitivas.

implica (False, True) = or (not False, True) = or (True, True) = True

Este processo e independente do domınio, ou seja, e independente de quando se esta tratando com funcoes sobre numeros, ou funcoes sobre caracteres, ou funcoes sobre arvores, ou qualquer outro tipo. Em outras palavras, se a funcao f for definida por f(x)= h(x,g(x)) entao sabemos que f(u(a)) = h(u(a),g (u(a))) independente das definicoes de g, h, u ou da constante a.

Frequentemente, a definicao de uma funcao nao pode ser expressa pela composicao simples de outras funcoes, sendo necessaria a definicao da funcao para varios casos. Por exemplo, a funcao que retorna o sinal algebrico de uma variavel pode ser definida da seguinte forma:

De forma similar, a diferenca absoluta entre x e y pode ser definida da seguinte forma:

difabs(x,y)=

{ x − y, se x>y y − x, se x ≤ y

Definicao de funcoes por recursao

Algumas situacoes existem em que e necessario definir uma funcao em termos de um numero infinito de composicoes. Por exemplo, a multiplicacao de numeros naturais (×) pode ser definida por infinitas aplicacoes da funcao de adicao (+). Senao vejamos:

Como nao ep ossıvel escrever um numero infinito de casos, este metodo de definicao de funcoes soe usual se existir alguma “regularidade” ou algum “princıpio de unificacao” entre os casos, que permita gerar os casos nao definidos, a partir dos casos ja definidos. Se existir tal princıpio de unificacao, ele deve ser estabelecido, sendo este o proposito das “definicoes recursivas”, onde um objeto e definido em termos de si proprio. Por exemplo, uma definicao recursiva da multiplicacao anterior pode ser:

1. Avalie a expressao 3 × 5, usando a definicao recursiva da multiplicacao mostrada nesta secao.

2. Defina, recursivamente, em termos da multiplicacao definida nesta secao, a funcao potencia, onde uma base e elevada a um expoente inteiro nao negativo.

3. Defina, recursivamente, a exponenciacao de numeros nao negativos elevados a uma potencia inteira. Sugestao: use a definicao condicional e a resposta do exercıcio anterior.

4. Defina, recursivamente, a adicao de inteiros nao negativos, em termos das funcoes sucessor e predecessor.

5. Defina, recursivamente, a adicao de inteiros quaisquer.

6. Defina, recursivamente, a divisao por inteiros nao negativos, em termos das funcoes subtracao e menor que.

Definicao explıcita de variaveis

Vamos considerar agora as definicoes explıcitas de funcoes, analisando inicialmente, as definicoes explıcitas de variaveis. Uma definicao de uma variavel e xplıcita se ela aparece no lado esquerdo da equacao e nao aparece no lado direito. Por exemplo, a equacao define explicitamente a variavel y. As definicoes explıcitas tem a vantagem de que elas podem ser interpretadas como regras de reescritas que nos informam como substituir uma classe de expressoes por outra. Por exemplo, a definicao anterior de y, implica na regra de reescrita y ⇒ 2ax que nos diz como eliminar a variavel y em qualquer formula, onde y ocorra. Por exemplo, para eliminar y da expressao 3y2 +5y + 1 aplica-se a regra de reescrita acima, para se obter

An ocao de definicao explıcita de variaveis pode ser extendida aos conjuntos de equacoes simultaneas. Um conjunto de variaveis e definido explicitamente por um conjunto de equacoes, se

• as operacoes forem individualmente explıcitas e

• elas puderem ser ordenadas, de forma que nenhuma delas use em seu lado direito uma variavel ja definida anteriormente na lista.

Por exemplo, o conjunto de equacoes

define explicitamente y, x e a.A s equacoes precedentes podem ser convertidas as seguintes regras de reescrita:

Estas regras podem ser aplicadas na seguinte ordem: a primeira delas pode ser aplicada ate que nao exista mais y, em seguida a segunda e aplicada ate que nao exista mais x e, finalmente, a terceira e aplicada ate que nao exista mais a. Desta forma teremos a seguinte sequencia de reducoes:

Definicao implıcita de variaveis

Dizemos que uma variavel e definida implicitamente se ela for definida por uma equacao onde ela aparece nos dois lados da equacao. Por exemplo, define implicitamente a como 3. Para encontrar o valor de a e necessario resolver a equacao usando regras da algebra. O processo de solucao pode ser visto como uma forma de converter uma definicao implıcita em uma definicao explıcita, mais usual, uma vez que uma definicao implıcita nao pode ser convertida diretamente em uma regra de reescrita. Assim, a equacao nao nos informa explicitamente o que deve ser substituıdo por a na expressao 2ax, por exemplo. Alem disso, as regras de reescrita que resultam de definicoes explıcitas sempre terminam, ou seja, a aplicacao repetida das regras de reescritas elimina todas as ocorrencias da variavel definida.

Por outro lado, ep ossıvel escrever definicoes implıcitas que nao terminam, ou seja, nada definem. Considere, como exemplo, a definicao implıcita

Apesar de sabermos, claramente, que esta equacao nao tem solucao, este fato pode nao ser tao obvio, em casos mais complexos. Se, ingenuamente, interpretarmos esta equacao como a regra de reescrita

2a ⇒ 2(a +1 ) ⇒ 2((a +1 )+ 1) ⇒

a ⇒ a+1 entao chegaremos a um nao determinismo na seguinte sequencia de reducoes:

As variaveis tambem podem ser definidas implicitamente por conjuntos de equacoes simultaneas. Por exemplo, as equacoes

definem implicitamente a =3 e d = −2. Podemos tambem ter definicoes implıcitas em que as variaveis nao aparecem nos dois lados da mesma equacao. Por exemplo, as equacoes

em que, nem a nem x aparece nos dois lados de uma mesma equacao, definem implicitamente a e x. Neste caso, nao existe qualquer forma de ordenacao destas equacoes de maneira que as ultimas equacoes nao facam uso de variaveis ja definidas nas equacoes anteriores. A forma implıcita pode ser observada pela transformacao das duas equacoes em uma so, ou seja,

Em resumo, uma definicao explıcita nos informa o que uma determinada “coisa” e, enquanto uma definicao implıcita estabelece algumas propriedades que esta “coisa” deve apresentar, exigindo que apenas esta “coisa” tenha estas propriedades. A determinacao do que esta coisa e exige um processo de solucao.

Definicoes explıcitas e implıcitas de funcoes

Apos termos analisado as definicoes explıcitas e implıcitas das variaveis, vamos agora considerar como estas definicoes sao aplicadas ao caso das funcoes. Por exemplo, as duas equacoes, a seguir, definem implicitamente a funcao implica.

and [p, implica (p, q)] = and (p, q) and [not p, implica (p, q)] = or [not p, and (not p, q)]

Estas equacoes nao podem ser usadas explicitamente para avaliar uma expressao como implica (True, False). Usandoaalgebra booleana, estas equacoes podem ser resolvidas para se chegar a seguinte definicao explıcita:

implica (p, q) = or (not p, q) 24

A definicao explıcita permite que implica (True, False) seja avaliada usando substituicao.

Uma vantagem da programacao funcional eq ue, como a algebra elementar, ela simplifica a transformacao de uma definicao implıcita em uma definicao explıcita. Isto tem uma importancia muito forte porque as especificacoes formais de sistemas de softwares, frequentemente, tem a forma de definicoes implıcitas, enquanto as definicoes explıcitas sao, normalmente, faceis de serem transformadas em programas. Assim, a programacao funcional proveu ma forma de se passar das especificacoes formais para programas satisfazendo estas especificacoes.

Exercıcios.

1. Mostre que a definicao explıcita da funcao implica (anterior) satisfaz a sua definicao implıcita.

2. Mostre que a definicao explıcita da funcao implica ea unica solucao para a sua definicao implıcita, ou seja, nenhuma outra funcao booleana satisfaz estas duas equacoes, apesar de que devem existir outras formas de expressar esta mesma funcao. Sugestao: usar Tabelaverdade.

(Parte 5 de 9)

Comentários