Ficha OCaml 2. Do familiar para o novo.

Nível básico

Ex. Digit Sum.

Considere o seguinte programa C que calcula a soma dos dígitos de uma dado número.

xxxxxxxxxx
21
1
// Um programa C que calcula a soma dos dígitos de um dado inteiro 
2
# include<stdio.h> 
3
int getSum(int n) 
4
{ 
5
  int sum = 0; 
6
  while (n) 
7
  { 
8
    sum +=  n % 10; 
9
    n /= 10; 
10
  } 
11
  return sum; 
12
} 
13
 
14
int main() 
15
{ 
16
 int n;
17
 printf("number? ");
18
 scanf("%d",&n); 
19
 printf("\n digit sum= %d \n", getSum(n)); 
20
 return 0; 
21
} 

Proponha duas versões OCaml da função getSum:

1. Uma versão iterativa, fiel a versão C, get_sum_iter : int -> int.

   Assim, get_sum_iter 3415 = 13

2. Uma versão recursiva get_sum_rec : int -> int.

   Assim, get_sum_rec 3415 = 13

Ex. Triângulo de Floyd.

O triângulo de Floyd é uma matriz triangular de números naturais. O seu nome se refere ao Robert Floyd.

É definido pelo preenchimento das linhas do triângulo com números consecutivos, começando com 1 no canto superior esquerdo. Assim o triângulo de Floyd com 5 linhas é:

xxxxxxxxxx
5
1
1
2
2  3
3
4  5  6
4
7  8  9  10
5
11 12 13 14 15

Um programa C que calcula este triângulo com um dado número de linhas é:

xxxxxxxxxx
25
1
#include<stdio.h>
2
#include<stdlib.h>
3
​
4
void print_triangle(int n)
5
{
6
  int value=1,i=0,line=0;
7
  for (line=1;line<=n;line++)
8
    {
9
      for(i=0;i<line;i++)
10
       printf("%4d",value++); 
11
      printf("\n");
12
    }
13
}
14
​
15
int main(int argv,char ** argc) {
16
  if (argv!= 2)
17
   {
18
     int n;
19
     printf("número de linhas? ");
20
     scanf(" %d",&n);
21
   }
22
  else print_triangle(atoi(argc[1]));
23
​
24
return 0;
25
}

Escreva a função OCaml print_triangle : int -> unit que realize esta mesma tarefa. Assim:

xxxxxxxxxx
7
1
print_triangle 5 = () 
2
(*no stdin*)
3
1
4
2  3
5
4  5  6
6
7  8  9  10
7
11 12 13 14 15

Nível Médio

Ex. Procura de número.

Charles Babbage propôs um desafio de aritmética simples mas que pensava poder ser resolvido mais comodamente com máquinas se estas existissem, em particular se ele tivesse os meios de as construir.

Qual é o menor inteiro positivo cujo quadrado termina nos dígitos 269.696?

(Babbage, carta para Lord Bowden, 1837)

Ele achou que a resposta poderia ser 99.736, cujo quadrado é 9.947.269.696; mas ele não tinha certeza.

Obviamente ele resolveu o problema com papel e caneta, mas é tao mais prático, de facto usar um programa de computador.

xxxxxxxxxx
20
1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <limits.h>
4
 
5
int main() {
6
    int current = 0,    
7
        square;
8
 
9
    while (((square=current*current) % 1000000 != 269696) && (square<INT_MAX)) {
10
        current++;
11
    }
12
 
13
    if (square > INT_MAX)
14
        printf("Condition not satisfied before INT_MAX reached.");
15
    else           
16
        printf ("The smallest number whose square ends in 269696 is %d\n", current);
17
 
18
    return 0 ;
19
}
20
 

Esta é uma solução em C (retirada do excelente site rosetta code, apesar deste exemplo aqui...).

Infelizmente este código tem alguns problemas escondidos.

1. Liste estas situações e proponha um programa C isento destes problemas.
2. Traduza o programa C corrigido para OCaml na forma de uma função babbage : unit -> int que de um argumento unit (o argumento vazio) calcula o inteiro pretendido pelo Charles Babbage .
3. Não haverá melhor algoritmo? Se responder positivamente, proponha uma nova e otimizada versão OCaml. Esperamos a função seguinte: babbage_opt : unit -> int.
4. Mas então, qual é este menor valor?

Ex. Troca de variável, com poupança.

Há uma forma simples de trocar o valor de duas variáveis numéricas, digamos x e y sem usar uma variável auxiliar.

x
1
#include <stdio.h> 
2
​
3
int main() 
4
{ 
5
    int x,y; 
6
    
7
    printf("two numbers: ");
8
    scanf(" %d %d", &x, &y);
9
    
10
    printf("Before Swapping: x = %d, y = %d\n", x, y); 
11
    
12
    x = x + y; 
13
    y = x - y;  
14
    x = x - y;  
15
  
16
    printf("After Swapping: x = %d, y = %d\n", x, y); 
17
  
18
    return 0; 
19
} 
20
​

Este pequeno programa C implementa esta ideia simples. Mas, sem devidos cuidados, é uma prenda envenenada.

1. Proponha uma versão OCaml na forma da função swap : int -> int -> unit cujo esqueleto se mostra aqui e que lhe pedimos por completar:

   xxxxxxxxxx
   5
   1
   let swap a b =
   2
    let x,y = ref a , ref b in
   3
    let ()  = Printf.printf "Before Swapping: x = %d, y = %d\n" !x !y in
   4
    (*Por completar*)
   5
    let ()  = Printf.printf "After Swapping: x = %d, y = %d\n" !x !y 
   

    

2. Liste os potenciais problemas que este programa tem (tanto na versão C como na versão OCaml).

3. Proponha uma versão OCaml sem a parte envenenada, ou seja a função nice_swap : int -> int -> unit. Caso seja necessário poderá lançar a exceção Failure "nice_swap"

    

Uma alternativa ao método proposto é usar o operador bitwise XOR para trocar para números. O operador XOR bit a bit avalia cada bit do resultado como 1 se os bits correspondentes dos dois operandos forem diferentes, caso contrário, avalia 0.

Sejam x e y dois valores inteiros, seja a = x XOR y. Agora a XOR y será avaliado como x e a XOR x será avaliado como y.

Uma solução em C pode ser:

xxxxxxxxxx
20
1
#include <stdio.h>
2
​
3
int main()
4
{
5
    int xnum1, num2;
6
​
7
    printf("two numbers: ");
8
    scanf(" %d %d", &x, &y);
9
​
10
    printf("Before Swapping: x = %d, y = %d\n", x, y); 
11
​
12
    x ^= y;
13
    y ^= x;
14
    x ^= y;
15
    
16
    printf("After Swapping: x = %d, y = %d\n", x, y);
17
    
18
    return 0;
19
}
20
​

4. Qual é o operador bitwise XOR em OCaml?
5. Proponha uma versão OCaml na forma da função bitwise_swap : int -> int -> unit.
6. Poderá esta solução também padecer do problema da solução original anterior?

Ex. Função de Rolling Hash para string.

Uma função de hash de uma string tem por objeto a conversão de uma string para um número inteiro que será intitulado como hash dessa string. Idealmente esta associação é única. Mas na prática duas strings podem ter o mesmo hash (fenômeno designado de colisão).

Uma boa função de hash é aquela em que a probabilidade em ter o mesmo hash para duas strings diferentes é residual ou é aquela para a qual é muito difícil saber que outra string tem uma colisão com uma dada string. Este tema será abordado com mais detalhe mais adiante nesta matéria e no curso.

Um caso particular de função de hash são as funções designadas de rolling hash. São funções auxiliares importantes em alguns algoritmos de processamento de texto. Por exemplo o algoritmo de procura de string em textos grandes conhecido por algoritmo Rabin-Karp para a procura em string usa uma função de rolling hash como função auxiliar.

Uma das funções Rollin Hash mais simples calcula uma hash para uma string $s=s_0 s_1 s_2 ... s_k$ da seguinte forma:

os valores $P$ e $M$ devem ser escolhidos cuidadosamente e onde os $s_i$ são os valores numéricos associados a cada letra considerada. Para o fim deste exercício, trabalharemos com strings constituídas exclusivamente por letras minúsculas, assim escolhemos $P=31$ e $M=1000000009\ (i.e. 10^9+9)$ e o valor de 'a' é $1$, o valor de 'b' é $2$, etc.

Por exemplo $RollingHash("hello")= (8 + 5 \times P + 12 \times P^2 + 12 \times P^3 + 15 \times P^4)\ mod\ M.$

xxxxxxxxxx
16
1
long long rollingHash(char *str,int length)
2
{
3
    // P and M
4
    int p = 31;
5
    int m = 1e9 + 9;
6
    long long power_of_p = 1;
7
    long long hash_val = 0;
8
 
9
    // Loop to calculate the hash value by iterating over the elements of the string
10
    for (int i = 0; i < length; i++) {
11
        hash_val = (hash_val  + (str[i] - 'a' + 1) * power_of_p) % m;
12
        power_of_p  = (power_of_p * p) % m;
13
    }
14
    return hash_val;
15
}
16
​

1. Numa primeira versão, não tomaremos conta do tamanho dos inteiros manipulados, ou seja, vamos trabalhar com valores de tipo int na esperança que estes sejam suficientes. Proponha uma versão OCaml desta função rollingHash : string -> int (o tamanho de uma string pode ser calculado da própria string em OCaml, não é preciso fornecê-lo explicitamente).

   Assim rolling_hash "hello" = 14222002.

2. Pretendemos agora garantir este mesmo cálculo mas com base numa função recursiva

   Assuma as definições seguintes:

xxxxxxxxxx
8
1
let p = 31                
2
let m = 1_000_000_000 + 9 
3
let code  c = Char.code c - Char.code 'a' + 1
4
​
5
let rec rolling_hash_rec s i hval powerp =
6
 (*Por completar *) 
7
  
8
let rolling_hash s = rolling_hash_rec s 0 0 1

Complete a definição da função rolling_hash_rec.

xxxxxxxxxx
3
1
utop # rolling_hash "euqueroestarlaquandotutiveresdeolharparatrassemprequeroouvirsquiloqueguardasteparadizernofim";;
2
​
3
- : int = 130515272

3. Proponha agora uma redefinição da função rolling_hash (qualquer uma das duas acima referida) que recorra à aritmética de precisão arbitrária (módulo zarith). A função esperada é: rollingHash_wide : string -> Z.t

xxxxxxxxxx
4
1
utop # #require "zarith.top";;
2
utop # rolling_hash_wide "temmilanosumahistoriadeviveranavegarhamilanosdememoriasacontaraicidadeabeiramarazul"
3
;;
4
- : Z.t = 728940700