|
|
| Muhammad ibn Musa al-Khwarizmi |
#include <stdio.h>
int main() /* Implementação do algoritmo de Euclides */
{
int m, n, x, y ;
printf(">> ") ;
scanf("%d %d", &m, &n) ;
x = m ;
y = n ;
do {
if( x > y ) x = x - y ;
else if( x < y ) y = y - x ;
} while( x != y ) ;
printf("mdc(%d,%d) = %d\n", m, n, x) ;
return 0 ;
}
Na verdade, uma linguagem não pode deixar de se comprometer com algum conjunto de mecanismos primitivos para processar informação. Ao efetuar essa escolha, a linguagem adere a um paradigma de programação particular.
É surpreendente a grande variedade de paradigma de programação que têm sido inventados: PARADIGMAS.
Quando se programa com uma linguagem imperativa, há uma forma de minorar as desvantagens do estado. O uso de estado local privado é seguro de forma geral. Por exemplo, em Java, recomenda-se o uso de variáveis locais nos métodos, de variáveis de instância privadas nos objetos, e convém evitar todas as outras formas.
let nAdd (x,y) = x+y ;; nAdd: (int * int) -> int let nAdd3 (x,y,z) = x+y+z ;; nAdd3: (int * int * int) -> int nAdd (3,4) = 7 nAdd3 (2,8,1) = 11Tecnicamente, a função nAdd tem apenas um parâmetro, de tipo int*int. Mas claro, através desse único parâmetro conseguimos passar duas unidades de informação.
let cAdd x y = x+y ;; cAdd: int -> int -> int let cAdd x y z = x+y+z ;; cAdd: int -> int -> int -> int cAdd 3 4 = 7 cAdd 2 8 1 = 11Escrever funções curried não tem nada que saber: basta separar os parâmetros por espaços em branco, na cabeça de cada função. Contudo o tipo destas funções afigura-se surpreendente para quem o observa pela primeira vez. Isso é resultado da representação interna das funções em OCaml. Segue-se a explicação...
Por exemplo, a função
let cAdd x y = x+y ;;é internamente convertida em:
let cAdd = fun x -> (fun y -> x+y) ;;Repare na engenhosa a ideia que está por detrás do esquema de tradução.
Vejamos mais alguns exemplos de tradução, lado a lado:
let cAdd x y z = x+y+z ;; let cAdd = fun x -> (fun y -> (fun z -> x+y+z)) ;; let f x = x+1 ;; let f = fun x -> x+1 ;; let nAdd (x,y) = x+y ;; let nAdd = fun (x,y) -> x+y ;;
nAdd (2,3) = (fun (x,y) -> x+y) (2,3) = 2 + 3 = 5 cAdd 2 3 = (fun x -> (fun y -> x+y)) 2 3 = (fun y -> 2+y) 3 = 2 + 3 = 5
let succ = cAdd 1 ;; succ: int -> int
let f x y = x + y ;; (* formato externo preferido *) let f x = (fun y -> x+y) ;; (* formato externo *) let f = (fun x y -> x+y) ;; (* formato externo *) let f = (fun x -> (fun y -> x+y)) ;; (* formato interno *)Todas são convertidas para a mesma forma interna.
Concretamente, numa linguagem funcional as funções podem ...
let compose f g = fun x -> f (g x) ;;
compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b
Também se pode escrever:
let compose f g x = f (g x) ;;Exemplo 2. Função para converter do formato não-curried para o formato curried.
let curry f = fun x -> fun y -> f (x,y) ;;
curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
Também se pode escrever:
let curry f x y = f (x,y) ;;Exercício: Escrever a função inversa uncurry.
Exercício: Que funções são as seguintes e quais os seus tipos:
Um conjunto é uma entidade cuja principal característica é a possibilidade de se poder saber se um valor lhe pertence ou não lhe pertence. Assim vamos representar cada conjunto por uma função booleana. Essa função, quando aplicada a um valor produz true se esse valor pertence ao conjunto e false se não pertence. Trata-se da chamada função característica do conjunto.
Exemplo 4. Estrutura de dados com funções: lista de funções.
let mylist = [(fun x -> x+1); (fun x -> x*x)] ;;
# (fun x -> x+1) = (fun x -> x+1) ;; Exception: Invalid_argument "equal: functional value".
Quando possível, é melhor usar essas funções de ordem superior do que programar o método indutivo diretamente. O código resulta mais legível e compacto.
É isso o que fazem os programadores mais experientes.
A função f define uma relação de um-para-um, pelo que a lista dos resultados tem o mesmo comprimento da lista de entrada.
(* map : ('a -> 'b) -> 'a list -> 'b list *)
let rec map f l =
match l with
| [] -> []
| x::xs -> (f x) :: map f xs
;;
Esta função está disponível na biblioteca do OCaml como List.map.
Exemplo de chamada:
List.map (fun x -> x + 1) [1;2;3]
A função f define uma relação de um-para-n, pelo que a lista dos resultados tem um comprimento sem qualquer relação com comprimento da lista de entrada.
(* flatMap : ('a -> 'b list) -> 'a list -> 'b list *)
let rec flatMap f l =
match l with
| [] -> []
| x::xs -> (f x) @ flatMap f xs
;;
Exemplo de chamada:
flatMap (fun x -> [x + 1; x + 2]) [1;2;3]
Esta função não está diretamente disponível na biblioteca do OCaml, pode ser obtida como a combinação de List.flatten com List.map. Concretamente, a seguinte definição também é válida.
(* flatMap : ('a -> 'b list) -> 'a list -> 'b list *)
let flatMap f l =
List.flatten (List.map f l)
;;
List.exists : ('a -> bool) -> 'a list -> bool (* Testa se pelo menos um dos valores duma lista satisfaz um dado predicado. *)
List.filter : ('a -> bool) -> 'a list -> 'a list (* Seleciona os elementos duma lista que satisfazem um dado predicado. *)
List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list (* Separa os elementos que satisfazem um predicado dos elementos que não o satisfazem *)
let allEven l =
List.for_all (fun x -> x mod 2 = 0) l
;;
Testar se todos os elementos duma lista são menores do que os elementos de outra lista:
let allLess l1 l2 =
List.for_all (fun x ->
List.for_all (fun y -> x < y) l2) l1
;;