Description

Pr´actica 3
Nota Importante:

Cuando se solicite la entrega de esta pra´ctica, cada alumno debera´ subir a su repositorio de pra´cticas (del cual se indicara´ su ubicaci´on ma´s adelante) un directorio p3 cuyo contenido debe ser u´nicamente los ficheros ej31.ml, fib.ml, prime.ml y condis.ml.
Sea muy cuidadoso a la hora de crear el directorio y los ficheros, y respete los nombres indicados. En particular, f´ıjese que todos estos nombres so´lo contienen letras en minu´sculas, nu´meros y puntos.
Adema´s, todos los ficheros deben compilar sin errores con las siguientes o´rdenes:
ocamlc -c ej31.ml ocamlc -o fib fib.ml ocamlc -c prime.ml ocamlc -c condis.ml
Ejercicios:

1. Como sabemos, una expresio´n que contenga una definicio´n local, de la forma
let <x> = <eL> in <eG>
puede siempre reescribirse, sin definiciones locales, utilizando la aplicacio´n de funciones, como la expresio´n equivalente
(function <x> -> <eG>) <eL>
Reescriba el siguiente fragmento de co´digo OCaml, de modo que no se empleen definiciones locales:
let e1 = let pi = 2. *. asin 1. in pi *. (pi +. 1.);;
let e2 =
let lg2 = log 2. in let log2 = function x -> log x /. lg2 in log2 (float (1024 * 1024));;
let e3 =
let pi_2 = 4. *. asin 1. in function r -> pi_2 *. r;;
let e4 =
let sqr = function x -> x *. x in let pi = 2. *. asin 1. in function r -> pi *. sqr r;;
De manera similar, una expresio´n de la forma if <b> then <e1> else <e2>
es siempre equivalente a
(function true -> <e1> | false -> <e2>) <b>
Utilizando esta relacio´n, reescriba (y simplifique cuando sea posible) el siguiente fragmento de c´odigo OCaml sin utilizar frases if-then-else:
let abs n = if n >= 0 then n else – n;; let par n = if n mod 2 = 0 then true else false;; let saluda s = if s = “Hola” then print_endline “Hola!” else ();; let f n = if n mod 2 = 0 then “es par” else “es impar”;;
let f n = if n mod 2 = 0 then “mu´ltiplo de 2” else if n mod 3 = 0 then “m´ultiplo de 3” else “impar”;;
Realice todas estas tareas en el fichero de texto ej31.ml.
2. Estudie la siguiente definici´on escrita en OCaml:
let rec fib n =
if n <= 1 then n else fib (n-1) + fib (n-2)
Compile esta definicio´n en el toplevel (compilador interactivo) ocaml y compruebe su funcionamiento.
Utilizando esta funcio´n construya un programa ejecutable fib que muestre por la salida esta´ndar (seguido de un salto de l´ınea) el valor de cada uno de los t´erminos de la serie de Fibonacci, desde 0 hasta el nu´mero que se pase como argumento al invocar el programa.
De este modo, su ejecuci´on podr´ıa verse como se indica a continuacio´n:
$ ./fib 10
0
1
1
2
3
5
8
13
21
34
55
$
En este ejercicio se trata de salirse lo menos posible del paradigma funcional, implementando la repetici´on mediante la aplicacio´n de funciones recursivas. Est´a prohibido, por tanto, el uso de palabras reservadas como while y for.
Guarde el c´odigo fuente del programa en un archivo con nombre fib.ml. Puede compilarlo con la orden ocamlc -o fib fib.ml.
Atencio´n: valores superiores a 40 como argumento de entrada de este programa podr´ıan provocar tiempos de ejecucio´n elevados.
3. Estudie la siguiente definicio´n (no muy eficiente) para la funci´on is prime, que sirve para determinar si un nu´mero positivo es o no primo:
let is_prime n =
let rec check_from i =
i >= n ||
(n mod i <> 0 && check_from (i+1)) in check_from 2;;
En un fichero prime.ml, defina una funci´on next prime: int -> int, tal que (para cualquier n > 1) next prime n sea el primer nu´mero primo mayor que n. As´ı, por ejemplo, tendr´ıamos next prime 11 = 13 y next prime 12 = 13. Defina una funcio´n last prime to: int -> int, tal que (para cualquier n > 1) last prime to n sea el mayor primo menor o igual que n. As´ı, por ejemplo, tendr´ıamos last prime to 11 = 11 y last prime to 12 = 11.
Trate de implementar como una funcio´n is prime2: int -> bool una versio´n ma´s eficiente de la funcio´n is prime. Si lo ha conseguido, deber´ıa notar una mejora clara en tiempo de ejecucio´n si compara, por ejemplo, is prime 1 000 000 007 con is prime2 1 000 000 007.
4. En el lenguaje OCaml, las funciones (&&) : bool -> bool -> bool y
(||) : bool -> bool -> bool implementan la cojuncio´n y la disyuncio´n booleanas.
A diferencia del resto de funciones en OCaml, la aplicacio´n de estas funciones sigue una estrategia lazy (so´lo se evalu´a el “segundo” argumento si es necesario).
Es por ello, que es preferible ver las expresiones de la forma <b1> || <b2> como una abreviatura de la expresi´on if <b1> then true else <b2> (en vez de verlas como aplicacio´n de funciones).
De modo ana´logo, las expresiones de la forma <b1> && <b2> deben ser vistas como una abreviatura de if <b1> then <b2> else false.
Al igual que hizo en el ejercicio 2 de la pra´ctica 1, prediga y compruebe el resultado de compilar y ejecutar las siguientes frases en OCaml, escribiendo todo ello en el fichero de texto condis.ml (es decir, tanto las frases en s´ı mismas, como el resultado de su compilacio´n y ejecucio´n entre comentarios):
false && (2 / 0 > 0);; true && (2 / 0 > 0);; true || (2 / 0 > 0);; false || (2 / 0 > 0);; let con b1 b2 = b1 && b2;; let dis b1 b2 = b1 || b2;; con (1 < 0) (2 / 0 > 0);; (1 < 0) && (2 / 0 > 0);; dis (1 > 0) (2 / 0 > 0);; (1 > 0) || (2 / 0 > 0);;