Programación con Ocaml

Vladimir Támara Patiño. Carlos F. Rodriguez

2004. Dominio público.

Capítulo 1  Introducción

• LOGRO: Identifica características de Ocaml
• LOGRO: Maneja conceptos de programación funcional pura
• LOGRO: Maneja conceptos de tipos

1.1  Vistazo de programación funcional y Ocaml

• INDICADOR: Puede reducir expresiones que incluyan funciones y aplicación funcional
• INDICADOR: Asocia expresiones a nombres empleando let
• INDICADOR: Define funciones sencillas que emplean tipos básicos
• INDICADOR: Deriva tipo de expresiones sencillas que incluyan tipos básicos
• INDICADOR: Emplea la documentación de Ocaml
• INDICADOR: Emplea el entorno interactivo de Ocaml

1.1.1  Teoría

Vistazo a Ocaml

• ocamlc que genera bytecode utilizable por la máquina Zinc y portable a toda arquitectura donde se ha portado la máquina Zinc (incluyendo x386/OpenBSD, x386/Linux, x386/Windows 95-NT, Mac, Digital, Solaris, IRIX)
• ocamlopt que genera binarios para diversas arquitecturas (incluyendo procesadores i386 con sistemas operativos OpenBSD y Linux).

Programación funcional pura

let asocia nombres con expresiones

Derivación de tipos

1.1.2  Hacía la práctica

Sobre documentación

Sobre instalación

Uso del entorno interactivo

1.1.3  Lecturas recomendadas

1.1.4  Ejercicios para afianzar teoría

1. ¿Qué expresión resulta tras aplicar el valor 3 a la siguiente función (haga sólo un paso de reducción)?: fun z -> z+z;;
2. ¿Qué valor resulta tras hacer la reducción completa de la siguiente expresión?: (fun var1 -> (fun var2 -> (var1*var1)+var2)) 2 3;;
3. La función suma puede verse en una notación prefija así: (+) 2 3 que equivale a 2+3. ¿Qué valor se obtiene al reducir por completo la siguiente expresión?: (fun v -> (+) v 3) 5 ;;
4. ¿Qué valor resulta tras reducir por completo la siguiente aplicación?: (fun f -> 1+(f 5)) (fun y -> 2*y);;
5. ¿Qué valor resulta tras reducir por completo la siguiente aplicación?: (fun f x y -> (f x)+(f y)) (fun y -> 2*y) 3 4;;
6. Consulte en la documentación de Ocaml la lista de operadores. ¿En que sección del manual está dicha lista?
7. ¿Cual es el tipo de la siguiente expresión? fun s t -> s t
8. Busque en la documentación del módulo Pervasives una función que permita convertir un entero en flotante. Después defina una función que reciba una variable entera x y retorne el flotante que resulta de sumar x (como flotante) con 0.5.
9. Suponga que ha ingresado en el entorno interactivo la función dif:
   
   let dif=fun f x h-> ((f (x+.h))-.(f x))/.h;;
   
   que calcula la aproximación a la pendiente de la tangente de una función en un punto x (usando como referencia el punto x+.h. Emplee esta función para definir una nueva función con nombre dif02 que haga lo mismo que la anterior pero fijando el valor de h en 0.2.
   
   
10. Use la función dif02 del ejercicio anterior para calcular una aproximación a la derivada de la función x² en x=1. ¿Cuál es el error en la aproximación? (el error entre un par de valores u y v es u - v ).

1.1.5  Ejercicios de programación

1. En un archivo de nombre areas.ml asocie el nombre areatriangulo a una función cuyo tipo sea float -> float -> float y que calcule el área de un triángulo, dada la base (primer parámetro) y la altura (segundo parámetros).
   
   Asocie el nombre alturatriangulo a una función de tipo float -> float -> float -> float que calcule la altura de un triángulo, recibiendo como primer parámetro la base (lado mayor), y como segundo y tercer parámetros la longitud de los otros dos lados. Puede serle de utilidad emplear la función sqrt: float -> float que retorna la raíz de un flotante no negativo.
   
   Finalmente asocie el nombre areatriangulo2 a una función de tipo float -> float -> float -> float que calcule el área de un triángulo recibiendo los mismos parámetros de la función alturatriangulo (sugerimos que emplee la función alturatriangulo).

1

En este ejemplo decimos que la variable x está acotada en la expresión.

2

Esta aplicación en cálculo lambda (l), se llama reducción beta (b).

3

Reducir significa efectuar aplicaciones funcionales reiteradamente hasta obtener una expresión que no puede aplicarse más.

4

fun permite definir una función, function también aunque este último no permite la abreviación mencionada.

Capítulo 2  Características funcionales

• LOGRO: Maneja funciones y expresiones

2.1  Introducción

• INDICADOR: Reconoce los tipos básicos que utiliza Ocaml.
• INDICADOR: Define funciones que emplean tipos agregados como tuplas y listas.
• INDICADOR: Define y emplea funciones recursivas.
• INDICADOR: Define funciones que emplean colecciones de datos como tuplas y listas.

2.1.1  Teoría

Sistema de tipos.

Tipos básicos (atómicos).

# 4;; 
- : int = 4 
# 4+5;; 
- : int = 9 
# (-) 9 5;; 
- : int = 4
# 0x2 + 0X8;;
- : int = 10
# 0b101 + 0o13;;
- : int = 16

• - : int -> int o - que retorna inverso aditivo
• succ: int-> int sucesor
• pred: int-> int predecesor
• (+) : int -> int -> int suma
• (-) : int -> int -> int resta
• (*) : int -> int -> int multiplicación
• (/) : int -> int -> int división entera. Lanza la excepción Divsion_by_zero si el denominador (i.e segundo parámetro) es 0. Si tanto numerador como denominador son positivos retorna el mayor entero menor o igual a la división. Si ambos operandos son negativos da lo mismo que la división entera entre sus valores absolutos, si uno de los operandos es negativo da lo mismo que la división entera entre valores absolutos pero con signo negativo.
  
  
• mod: int -> int -> int residuo de división entera. Si el denominador (segundo parámetro) es 0 lanza la excepción Divsion_by_zero. El comportamiento con negativos se presenta con un ejemplo: 5 mod 2 es 1; -5 mod 2 es -1; 5 mod -2 es 1 y -5 mod -2 es -1. Note que se cumple: x = (x / y) * y + (x mod y), con abs(x mod y) <= abs(y)-1.
• abs: int -> int que retorna valor absoluto.

• land : int -> int -> int conjunción lógica (da 1 sólo si los dos bits son 1).
• lor : int -> int -> int disyunción (da 0 sólo si los dos bits son 0).
• lxor : int -> int -> int o exclusivo (da 1 sólo si los dos bits son diferentes).
• lnot : int -> int negación
• lsl : int -> int -> int corrimiento a la izquierda, el segundo parámetro indica cuantas posiciones debe correrse el primer parámetro. El segundo parámetro debe ser mayor o igual a 0 y menor que 32 en plataformas de 32 bits o que 64 en plataformas de 64 bits (valores fuera de este rango dan resultados no especificados).
• asr : int -> int -> int corrimiento a la derecha, el segundo parámte indica el número de posiciones (la misma convención que lsr.

• 0.3
• 2E1 que equivale a 20.0
• -2.2e-1 que equivale a -0.22

• -. o -. que retorna inverso aditivo (prefijo)
• +. suma (infijo)
• -. resta (infijo)
• *. multiplicación (infijo)
• /. división (infijo)
• ** exponenciación (infijo)

• sqrt: float -> float raíz cuadrada
• exp: float -> float exponenciación
• log: float -> float logaritmo natural
• log10: float -> float logaritmo en base 10
• cos: float -> float coseno
• sin: float -> float seno
• tan: float -> float tangente
• acos: float -> float arcocoseno
• asin: float -> float arcoseno
• atan: float -> float arcotangente (para obtener ángulos precisos, de ser posible, mejor emplear atan2 que se describe más adelante).
• cosh: float -> float coseno hiperbólico
• sinh: float -> float seno hiperbólico
• tanh: float -> float tangente hiperbólica
• ceil: float -> float techo, i.e el menor entero mayor o igual al argumento
• floor: float -> float piso, i.e el mayor entero menor o igual al argumento
• abs_float: float -> float valor absoluto de un flotante
• atan2: float -> float -> float que recibe cateto opuesto (y) y cateto adyacente (x) y retorna el ángulo (teniendo en cuenta signos de x e y).
• mod_float: float -> float -> float resto que queda tras dividir el primer argumento (a) entre el segundo (b). Retorna a -. n *. b donde n es el piso de a /. b.
• frexp : float -> float * int retorna una pareja con la parte significativa (x) y el exponente (n) del argumento. Cuando el argumento es x=0 y n=0. Si el argumento (f) no es cero se cumple: f=x2ⁿ y 0.5£ x £ 1.0.
• ldexp: float -> int -> float recibe dos argumentos x:float y n:int y retorna el flotante x2ⁿ.
• modf: float -> float * float returna una pareja con la parte fraccional y entera del argumento.
• float: int ->float o float_of_int: int -> float retorna el entero que reciben como número de punto flotante.
• truncate: float -> int y int_of_float que trunca la parte decimal del argumento que recibe. El comportamiento es insospechado si al truncar se sale del rango representable con enteros.

• infinity que representa infinito positivo
• neg_infinity que representa infinito negativo
• nan (abrevia Not a Number), representa un valor que no es número
• max_float que corresponde el máximo flotante representable
• min_float que corresponde al menor flotante positivo que no es cero y que no está denormalizado.
• epsilon_float mínimo flotante positivo x tal que 1.0 +. x <> 1.0.

---

\\	barra invertida \
\"	comillas "
\'	apostrofe '
\n	cambio de línea (LF)
\r	retorno de carro (CR)
\t	tabulador horizontal (TAB)
\b	espacio atras (BS)

---

• int_of_char : char -> int
• char_of_int : int -> char

• Char.chr: int -> char dado el código ASCII devuelve el carácter.
  
  # Char.chr 126;;
  - : char = ' '
  # Char.chr 192;;
  - : char = 'Ã'
  # Char.chr 64;;
  - : char = '@'
  
  
• Char.code: char -> int que retorna el códgio ASCII correspondiente a un carácter.
  
  # Char.code 'q';;
  - : int = 113
  # Char.code '1';;
  - : int = 49
• Char.lowercase: char -> char y Char.uppercase: char -> char La primera convierte un carácter a minúsculas y la segunda convierte un carácter a mayúsculas.
  
  
• Char.escaped: char -> string que retorna la cadena que representa el caracter siguiendo convenciones de Ocaml.

  # Char.escaped 'a';;
  - : string = "a"
  # Char.escaped '\010';;
  - : string = "\\n"
  

  
  
  
• Char.compare : t -> t -> int que se comporta como la función compare polimórfica.

• x = y igualdad³
• x <> y x no es igual a y
• x < y x menor que y
• x <= y x menor o igual que y
• x >= y x mayor o igual que y⁴
• x > y x mayor que y

# (fun x y -> x=y) 5 5;; 
- : bool = true  \\
# (fun x y -> x=y) 5 54;;
- : bool = false \\
# (fun x y -> x<>y) 5 54;;
- : bool = true \\
# (fun x y -> x<=y) 5 54;;
- : bool = true \\
# (fun x y -> x<=y) 5 5;; 
- : bool = true 

• not : bool -> bool que es negación (prefijo)
• (&&) : bool -> bool -> bool que es conjunción corta, si el primer argumento evalua a false no evalua el segundo sino que retorna false.
• (||) : bool -> bool -> bool que es disyunción corta, si el primer operador evalua a true retorna true sin evaluar el segundo.

# "Dios es el único que lo sabe todo";;
- : string = "Dios es el único que lo sabe todo"

string_of_bool : bool -> string
bool_of_string : string -> bool
string_of_int : int -> string
int_of_string : string -> int
string_of_float : float -> string
string_of_float : float -> string
float_of_string : string -> float

Tipos agregados.

• fst : 'a * 'b -> 'a que reotrna el primer elemento de una pareja.
• snd : 'a * 'b -> 'b que retorna el segundo elemento de una pareja.

• La lista vacía se representa de la forma [ ] .
• Una lista se puede representar entre paréntesis y los elementos separados con punto y coma (;). Ejemplos: # [1;2;3];;
  - : int list = [1; 2; 3]
  # ["Hola";"mundo";"ocaml"];;
  - : string list = ["Hola"; "mundo"; "ocaml"]
• Utilizando el operador :: se construyen listas especificando cabeza y cola por ejemplo:
  
  # "Hola"::"mundo"::"ocaml"::[ ];;
  - : string list = ["Hola"; "mundo"; "ocaml"] # 1::[2;3;4;5;6];;
  - : int list = [1; 2; 3; 4; 5; 6]

Expresiones y Funciones.

Recursión.

• Caso trivial: es aquel que si se cumple devuelve un resultado que puede ser final o parte de la solución.
• Caso recursivo: es aquel que llama de nuevo a la función recursiva.

2.1.2  Hacía la práctica

2.1.3  Lecturas recomendadas

2.1.4  Ejercicios para afianzar teoría

1. Asocie el nombre cuadrado a una función cuyo tipo sea int -> int y que calcule el cuadrado de un entero dado.
   
   
2. Utilizando la función cuadrado del punto anterior, realice una función que calcule el cubo de un entero dado.
   
   
3. ¿Qué nombre debería recibir la siguiente función?

   let rec nombre = function
       0 -> 1
       | n -> n*(nombre (n-1));;
   

   
   
   
4. ¿Qué diferencia tiene la anterior función a la siguiente ?

   let rec nombre n = 
   if n=0 then 1
   else n*(nombre (n-1));;
   

   
   
   
5. ¿Cómo se llama el mecanismo que permite que una función se comporte como un switch case ? De un ejemplo:
   
   
6. ¿Cuál es el tipo de las siguientes funciones ?
   let suma x y z = x+y+(z (x-y));;
   let rec serie j i n = if i=n then (j i) else (j n)+(serie j i (n-1));;
   
   
   
7. ¿Que condición debe cumplirse para que opere correctamente la siguiente función?

   let rec serie j i n = 
     if i=n then 
       (j i) 
     else 
       (j n)+(serie j i (n-1))
   ;;
   

   
   
   
8. ¿Qué función permite pasar un número ASCII a caracter ?
   
   
9. Asocie el nombre miembro a una función que recibe una lista y un elemento, la función debe determinar si el elemento esta o no en la lista. ¿Cuál es el tipo de la función ?
   
   
10. Asocie el nombre anexar a una función que recibe 2 listas y las une colocando la primera detras de la ultima. La función no debe ser recursiva.

2.1.5  Ejercicios de programación

1. En un archivo de nombre tadlista.ml construya las siguientes funciones:
   • listavacia dice si una lista es vacia o no (true o false).
   • invertir devuelve una lista dada invertida.
   • esta_elemento dice si un elemento esta en una lista dada.
   • num_ocurrencias calcula el número de veces que esta un elemento en una lista dada.
   • lista_ordenada dice si una lista esta ordenada o no.
   • espalindrome dice si una lista es palindrome (se lee igual de derecha a izquierda que de izquierda a derecha).

2.2  Funciones recursivas

• INDICADOR: Emplea el condicional if.
• INDICADOR: Emplea funciones para realizar operaciones básicas de entrada/sálida (e.g print_endline)
• INDICADOR: Emplea correspondencia de patrones (pattern matching).
• INDICADOR: Emplea recursión mutua y definiciones locales.
• INDICADOR: Emplea comentarios que pueden ser usados por Ocamldoc.

2.2.1  Teoría

Condicional if

• print_endline: string -> unit que imprime por salida estándar la cadena que recibe con un salto de línea al final.
• prerr_endline: string -> unit análoga a la anterior pero que imprime por error estándar.
• print_char: char -> unit, print_string: string -> unit, print_int: int -> unit, print_float: float -> unit que imprimen en salida estándar valores de los tipos presentados (sin salto de línea). Así como las funciones análogas para error estándar que comienzan con prerr en lugar de print.
• print_newline: unit -> unit y prerr_newline: unit -> unit que hacen en un salto de línea en salida estándar o error estándar⁷.
• read_line: unit-> string que lee de entrada estándar hasta encontrar un carácter de cambio de línea y lee la cadena leída sin el cambio de línea.
• read_int: unit-> int y read_float: unit -> float que leen una línea de entrada estándar y la convierten a entero y flotante respectivamente. Si la línea leída no puede convertirse al tipo esperado, estas funciones lanzan una excepción (que se explicará como manejar más adelante).

Correspondencia de patrones

Definiciones locales y recursión mutua

2.2.2  Hacía la práctica

Documentación de fuentes con Ocamldoc

• (b texto) para emplear negrillas
• (i texto) para emplear itálicas
• (c texto) para centrar
• [texto] estilo de letra de código fuente
• @author texto para establecer autor (de módulo o función)
• @version texto para establecer versión (de módulo o función)
• @param id texto para describir parámetro id de una función
• @return texto para describir valor retornado por una función
• @see url para referenciar un URL (también puede ser un archivo).

2.2.3  Lecturas recomendadas

• Las funciones de error estándar y salida estándar las encuentra en la documentación del módulo Pervasives de [3].
• Puede consultar sobre los fundamentos de correspondencia de patrones (pattern matching en inglés) en la sección 5 de [4].
• La sintaxis completa de patrones puede consultarla en la sección 6.6 de [3].
• Todas las posibilidades de Ocamldoc se documentan en el capítulo 15 de [3].

2.2.4  Ejercicios para afianzar teoría

1. ¿A que evalúa la expresión if true=false then false else true ?
2. ¿Cual es el tipo de la expresión if x<y then x else y+1 ?
   
   
3. ¿Con qué objetivos concuerda el patrón [1]?
4. Escriba un patrón que concuerde con todas las listas con los elementos "wq" e "il" usando solo los constructores :: y []
5. ¿Cual es el tipo de la siguiente función (presentada en la lectura)? function ((a:int),b) as c -> (a,b+1,c)
6. ¿Que objetivos no cubren los casos de la siguiente función?
   
   function
   | (0,_::_) -> 0
   | (1,[1]) -> 1
   | (2,[x;y]) -> x
   | (n,_) when n<>0 -> 1;;
   
   Note que si en tiempo de ejecución, se intenta evaluar esta función en un objetivo que no concuerde con patrón alguno se producirá una excepción.
7. En la función del ejercicio anterior algunos objetivos son cubiertos por más de un patrón. Tras experimentar o consultar la documentación (sección sobre expresiones, subsección definición de funciones) diga cual es el caso que el algoritmo de correspondencia de patrones escoge cuando los patrones de varios casos cubren un objetivo.
   
   
8. Entre las funciones típicas sobre listas (en programación funcional general) está la función map:
   
   let rec map f = function
   | [] -> []
   | h::t -> (f h)::(map f t)
   ;;
   
   ¿Cual es el tipo de esta función?
9. Con una definición local para una función f que multiplique por dos use la función map para transformar la lista [3;0;1;8] en la lista [6;0;2;16].
10. Otra función típica para lista es la función fold:
    
    let rec fold f v = function
    | [] -> v
    | h::t -> fold f (f v h) t
    ;;
    
    ¿qué valor retorna esta función al evaluar la siguiente aplicación?:
    
    fold (fun n e -> n+1) 0 [8;3;3;1];;

2.2.5  Ejercicios de programación

1. Haga una función reconoce que reciba una cadena con números enteros no negativos con el operador + y espacios entre ellos y que retorne el resultado de evaluar la suma. Si la expresión que recibe no es válida genere excepciones con mensajes de error usando la función (failwith "mensaje").
   
   Pueden servirle las funciones:
   • String.get s i que retorna el i-ésimo carácter de la cadena s (el primer carácter tiene índice 0).
   • String.sub s i l que retorna la subcadena de s de longitud l que comienza en el i-esimo carácter.
   • String.length s que retorna la longitud de la cadena s.
   • int_of_string s que convierte la cadena de dígitos s a entero (si no puede convertirse lanza una excepción).
   
   
   
2. Implemente la función filter p l de tipo ('a -> bool) -> 'a list -> 'a list que filtra la lista l con el predicado p. Por ejemplo al aplicar esta función así
   
   filter (fun n -> n>5) [1;8;3;9;6]
   
   daría
   
   [8;9;6]

2.3  Diversos tipos de funciones

• INDICADOR: Emplea funciones anónimas.
• INDICADOR: Identifica, emplea y construye funciones polimórficas.
• INDICADOR: Emplea funciones de orden superior
• INDICADOR: Maneja el concepto de Curried.
• INDICADOR: Conoce y aplica la transferencia referencial

2.3.1  Teoría

Funciones anónimas.

Funciones polimórficas.

• compare : 'a -> 'a -> int que retorna 0 si x=y, un entero positivo si x>y y un negativo en otro caso.
• min : 'a -> 'a -> 'a que retorna el menor de los dos argumentos.
• max : 'a -> 'a -> 'a que retorna el mayor de los dos argumentos.

Funciones de orden superior.

2.3.2  Curried. Funciones parciales

2.3.3  Transparencia referencial

2.3.4  Hacía la práctica

2.3.5  Lecturas recomendadas

2.3.6  Ejercicios para afianzar teoría

1. ¿A qué evalua la siguiente función? (fun x y -> (if x>y then x else y)) 23 4;;
   
   
2. Escriba la función anónima anexar que recibe dos listas y a la primera lista le una la segunda.
   
   
3. Escriba la función curry que recibe una función que recibe una pareja (x,y) y que retorne la currificación
   
   
4. La función quicksort recibe una lista x y nos devuelve una lista y con los elementos ordenados de x. ... ¿La función quicksort es una función polimórfica? si o no.
   
   
5. La función quicksort recibe una lista x y nos devuelve una lista y con los elementos ordenados de x. ... ¿Cuál es el tipo de la función quicksort ?
   
   
6. ¿Cuál función de orden superior me sirve para obtener de una lista de enteros el número menor ?
   
   
7. Utilizando funciones de orden superior y funciones anónimas, arme una función que obtenga el número de ocurrencias de un elemento en una lista. De como respuesta la función aplicada a encontrar el número de ocurrencias de 'a' en ['1';'2';'a';'b';'c';'a';'c'] (como requerimiento debe utilizar List.length).
   
   
8. ¿Cuál es el tipo de cada una de las funciones List.map y List.map2?
   
   
9. En cuanto a funcionalidad ¿cuál es la diferencia entre List.map y List.map2?
   
   
10. ¿Una función de orden superior puede ser polimórfica?

2.3.7  Ejercicios de programación

1. En un archivo llamado funciones.ml escriba las siguiente funciones
   
   • Función insertar, que, dados una lista no decreciente ys y un elemento y, devuelva una lista no decreciente igual a ys más el elemento y insertado en el lugar correspondiente.
   • Función unico, que, dada una cadena devuelva una cadena que contenga exactamente los elementos que se encuentran solamente una vez en la cadena dada.
     Por ejemplo: unico "Cuales son las letras unicas en esta frase?" debe dar "oicf?" .
   
   
   
2. En un archivo llamado enterog.ml utilizando listas represente enteros positivos grandes y realice las funciones necesarias para sumar, restar y multiplicar enteros grandes, y convertir un entero en un entero grande. Ejemplos
   
   • el número 156 representado en entero grande es [1;5;6]
   • los números 156 y 32 representados comon enteros grandes son [1;5;6] y [3;8]. El resultado de la suma es [1;9;4]
   • al restar [1;5;0;0;0] de [5;5;5;0] se obtiene [9;4;5;0]
   Opcional: Idee una representación para enteros negativos e implemente las mismas funciones con la nueva representación.
   
   
3. Punto adicional: Cambie el archivo enterog.ml ha floatg.ml y edite las funciones, para permitir guardar flotantes grandes de la forma (parteentera, parteflotante) ejemplo el número 15.5 se representa en floatg ([1;5],[5]).

2.4  Tipos definidos por el usuario

• INDICADOR: Define nuevos tipos
• INDICADOR: Emplea nuevos tipos y excepciones
• INDICADOR: Depura y rastrea programas Ocaml

2.4.1  Teoría

Definición de tipos

Tipos variantes

type fpclass =
| FP_normal (* Normal number, none of the below *)
| FP_subnormal (* Number very close to 0.0, has reduced precision *)
| FP_zero (* Number is 0.0 or -0.0 *)
| FP_infinite (* Number is positive or negative infinity *)
| FP_nan (* Not a number: result of an undefined operation *) OJO

---

Figure 2.1: Ejemplo de tipo variante

---

let suma x t= match (x,y) with 
 | Entero(e1),Entero(e2) -> Entero(e1+e2) 
 | Entero(e1),Flotante(f2) -> Flotante((float\_of\_int e1)+f2)
 | Flotante(f1),Entero(e2) -> Flotante(f1+(float\_of\_int e2))
 | Flotante(f1),Flotante(f2) -> Flotante(f1+f2)
;;

Tuplas y registros

type tsexo=M | F;;
type datosper=string*string*int*tsexo;;

type datosper2={nombre:string; apellido:string; edad:int; sexo:tsexo};;

let j={nombre="Andrés"; apellido="Benavidez"; edad=5; sexo=M};;

let nombreCompleto r=r.nombre^" "^r.apellido;;

Tipos recursivos

type lisent= Vacia | Cons of int*lisent;;

let rec longitud=function
 | Vacia -> 0
 | Cons (_,cola) -> 1+(longitud cola)
;;

longitud (Cons(3,Cons(29,Cons(-1,Vacia))));;

Tipos paramétricos

type 'a option = None | Some of 'a

type stringOpt=string option;;

let rec primerMayor10 = function
 | [] -> None
 | h::t -> 
  if (h>10) then
   Some h
  else
   primerMayor10 t
;;

let nomMayor le =
 match (primerMayor10 le) with
 | None -> "No hay elemento mayor que 10"
 | Some e -> "El primer elemento mayor que 10 es "^(string_of_int e)
;;

type 'a arbbin= Vacio | Nodo of 'a * 'a arbbin * 'a arbbin;;

let rec altura=function
 | Vacio -> 0
 | Nodo (r,i,d) -> 1+(max (altura i) (altura d))
;;

Excepciones

exception NoEsta;;

exception ErrorEnPosicion of int*string;;

let rec esperaPrimeraX p=function
| [] -> raise NoEsta
| h::t -> 
 if (p=0 && h="X") then
  true
 else if (p=0) then
  raise (ErrorEnPosicion(p,"En lugar de X está "^h))
 else if (h="X") then
  raise (ErrorEnPosicion(p,"X aparece antes en la pos "
   ^(string_of_int p)))
 else
  esperaPrimeraX (p-1) t
;;

• Match_failure of (string * int * int) Assert_failure of (string * int * int) Invalid_argument of string puede usarse con función invalid_arg: string -> 'a Failure of string puede emplearse con función failwith: string -> 'a Not_found Out_of_memory Stack_overflow Sys_error of string End_of_file Division_by_zero Sys_blocked_io Undefined_recursive_module of (string * int * int)

let laXen5 l =
try
 if (esPrimeraX 5 l) then
  "Primera X en posición 5"
 else
  "Nunca entra a este caso"
with
 | _ -> "No se encontró la primera X en la posición 5"
;;

2.4.2  Hacía la práctica

Depuración con ocamldebug

Rastreo

# #use "taller5-2.ml";;
type exprar =
    Const of int
  | ...
val reconoce_exprar : string -> exprar = <fun>
- : exprar = Suma (Const 1, Const 2)
# #trace reconoce_exprar ;;
reconoce_exprar is now traced.
# reconoce_exprar "((5+3)*2)";;
reconoce_exprar <-- "((5+3)*2)"
reconoce_exprar --> Prod (Suma (Const 5, Const 3), Const 2)
- : exprar = Prod (Suma (Const 5, Const 3), Const 2)

2.4.3  Lecturas recomendadas

2.4.4  Ejercicios para afianzar teoría

1. Defina un tipo variante trivaluada cuyos constructores sean Si, No y NoSabe.
2. Defina un tipo variante intinf que pueda representar todos los enteros soportados por el tipo int con la constructora Ent y las dos constructoras InfP e InfN que representan inf y -inf. Después defina la función sumaii que recibe dos elementos de este tipo y retorna la suma, en el caso de sumar dos infinitos (bien sean positivos o negativos) debe generar la excepción predefinida en Ocaml Invalid_argument, la cual recibe una cadena. una excepción
3. Con el tipo que definió en el punto anterior podría definirse un racional (numerador, denominador) y una función que reduce:

   type racinf=intinf*intinf;;
   
   let redrac r1=match r1 with
   | (Ent n,Ent d) -> if (n mod d=0) then (Ent (n/d), Ent 1) else (Ent n,Ent d)
   | (InfP,Ent d) | (Ent d,InfP) -> if (d>0) then (InfP,Ent 1) else (InfN,Ent 1)
   | (InfN,Ent d) | (Ent d,InfN)-> if (d>0) then (InfN,Ent 1) else (InfP,Ent 1)
   | (InfN,InfP) | (InfP,InfN) -> (InfN,Ent 1)
   | (InfN,InfN) | (InfP,InfP) -> (InfP,Ent 1)
   ;;
   

   Cual es el tipo de redrac ?
   
   
4. Empleando el tipo registro datosper2 introducido en la lectura, escriba una función mayor: datosper2 -> datosper2->bool que retorne true sólo si la edad del primer registro es mayor que la del segundo.
   
   
5. Defina el tipo exprar que represente expresiones aritméticas entre enteros. Una expresión puede ser una constante (constructor Const), el inverso aditivo de una expresión (InvAd), una suma entre dos expresiones (Suma), una resta entre dos expresiones (Resta), un producto (Prod) o una División (Div).
   
   
6. El tipo que definió en el ejemplo anterior puede usarse en una función que evalue una expresión aritmética. Complete la función siguiente y después usela para evaluar la expresión (3+5)*-4 (use InvAd para representar -4):

   let rec evalua = function
    | Const i -> i
    | InvAd e -> -(evalua e)
   ...
   ;;
   

   
   
   
7. Defina un tipo parámetrico narb que permita representar un árbol n-ario. Después de definido debería poderse definir la siguiente función que calcula la cantidad de nodos de un árbol n-ario (consulte la especificación de List.fold_left en la documentación de Ocaml):

   let rec npeso = function
   | Vacio -> 0
   | Nodo (e,l) -> (List.fold_left (fun a s -> a+(npeso s)) 1 l)
   ;;
   

   
   
   
8. El tipo definido en el ejercicio anterior tiene el inconveniente de permitir representar el mismo árbol de diversas formas, por ejemplo: (Nodo ("a",[])) debería ser el mismo (Nodo ("a",[Vacio])) o con tantos subárboles vacios como se desee ((Nodo ("a",[Vacio;Vacio;Vacio;Vacio]))). El tipo paramétrico narb2 definido a continuación soluciona ese inconveniente (aunque introduce otros)

   type 'a nnod=Hoja of 'a | Sub of 'a * (('a nnod) list);;
   type 'a narb2=Vacio2 | Nodo2 of 'a nnod;;
   

   Escriba la función npeso2 que retorne el peso de un arbol de tipo narb2.
   
   
9. Otra posibilidad para el tipo narb es emplear una convención, por ejemplo no permitir que como hijos de un nodo aparezca el árbol Vacio. Defina la excepción VacioComoSubarbol y escriba la función narbBueno: 'a narb -> unit que retorne () cuando el árbol siga la convención o en otro caso que lance la excepción definida (si lo desea y le son de utilidad emplee las funciones List.exists y List.iter).
   
   
10. Escriba la función npeso3: 'a narb -> int empleando las funciones narbBueno y npeso de los ejercicios anteriores. Debe retornar el peso de árboles que sigan la convención y -1 para árboles que no la sigan.

2.4.5  Ejercicios de programación

1. En un archivo taller5-1.ml escriba la función sublistas: 'a list -> 'a list list que reciba una lista y retorne todas las posibles sublistas no vacias de elementos consecutivos, por ejemplo si recibe [1;2;3] debe retornar [[1];[2];[3];[1;2];[2;3];[1;2;3]]
   
   
2. Descargue y descomprima las fuentes del programa repasa disponibles en http://structio.sourceforge.net/repasa. Compilelo y pruebe por lo menos la interfaz plana repasa.
   
   El archivo lrepasa.ml es una librería de funciones con diversos propósitos. Entre otras se define la función
   
   test_equal_answer: heuresp -> string -> string -> bool
   
   que decide si una respuesta es correcta empleando una posible heurística.
   
   Complete el archivo taller5-1.ml extendiendo el tipo heuresp con el constructor HIgnoreSpaces y extienda la función test_equal_answer para que emplee la nueva heurística. Lo que debe hacer es decidir que dos cadenas sean iguales aún cuando haya espacios en blanco redundantes (se consideran espacios en blanco: ' ', '\n', '\t' y '\r'). Por ejemplo con esta heurísitca las cadenas " hoy es miercoles" y "hoy es miercoles" deben ser consideradas iguales (aunque son diferentes a "hoyes miercoles" ).
   
   Opcional: Modifique las fuentes de repasa con su cambio y compile (más rápido con make repasa). Es recomendable que verifique los sitios donde se usan constructores de heuresp por ejemplo desde el interprete de comandos con:
   
   grep "HCase" *ml
   
   y que agregue el nuevo caso. Si amplia la función parse_heur (digamos para que la cadena "ignoraesp" corresponda a HIgnoreSpaces) y el DTD dtds/def.dtd para incluir la nueva cadena como caso del atributo heur del elemento sig, podrá modificar algún banco de definiciones para que emplee su heurística cuando sea usado con las interfaces de repaso repasa o repasatk. Por ejemplo puede modificar uno de los significados de regr/ejsimple.def para agregar el atributo heur="ignoraesp" y después verificar su heurística con:
   
   ./repasa -forma-abierta -D dtds regr/ejsimple.def
   
   
3. Para analizar, interpretar o compilar un programa puede ser conveniente convertir la sintaxis concreta del programa a un árbol de sintaxis abstracta (AST - Abstract Syntax Tree).
   
   En el ejercicio de afianzamiento 5 se pedía definir un tipo para un AST apropiado para expresiones aritméticas, mientras que en el ejercicio 6 se pedía implementar una función para evaluar.
   
   En un archivo taller5-2.ml haga la función reconoce_exprar: string -> exprar que recibe una cadena con una expresión aritmética y retorna el AST correspondiente. Puede suponer que la cadena no tiene errores pero si espacios arbitrarios, que emplea el operador prefijo - (inverso aditivo) y los operadores infijos , +, -, * y /, y posibles subexpresiones entre paréntesis. Asigne la precedencia y asociatividad que usted desee a los operadores infijos.
   
   Sugerencia: Compile el archivo y de requerirlo depure con ocamldebug.
   
   Opcional: Mejore la función que implementó para que detecte errores y lance una exepción, y para que de prioridades y asociatividad a los operadores así:
   • - prefijo
   • * / con asociatividad a la izquierda
   • + - con asociatividad a la izquierda

1

3.2E4 corresponde a 3.2·10⁴

2

Librería básica es el término con el que traducimos `core library.´

3

Esta igualdad polimórfica compara igualdad estructural, puede emplearse con tipos como listas o con tipos definidos por usuario o con estructuras mutables.

4

Las comparaciones funcionan sobre tipos básicos de la manera usual (para booleanos se considera true > false. En estructuras compuestas se extienden de manera natural --aprovechando su definición usual para enteros, caracteres, flotantes, cadenas y booleanos.

5

La implementación actual soporta cadenas de hasta 2²4-5 caracteres en plataformas de 32 bits

6

Estas funciones en Ocaml no son "puras" porque tienen efectos laterales (como imprimir en pantalla). En programación funcional pura las funciones no tienen efectos laterales, es decir al llamar una función todo el resultado de su operación será retornado a la función llamadora.

7

También puede hacerse un salto de línea empleando la secuencia de escape \n en una cadena.

8

En realidad no se necesita el primer | después de function, lo ponemos para facilitar visualizar y eventualmente reordenar o agregar casos.

9

Es posible definir funciones de impresión para ciertos tipos (ver en el manual de referencia load_printer).

Capítulo 3  Característcas imperativas

• LOGRO: Maneja tipos mutables
• LOGRO: Maneja estructuras de control tipicamente imperativas
• LOGRO: Emplea funciones con efectos laterales
• LOGRO: Emplea funciones de diversas librerías de Ocaml

3.1  Características imperativas

• INDICADOR: Emplea funciones con características imperativas.
• INDICADOR: Emplea estructuras de datos modificables.
• INDICADOR: Identifica y construye funciones utilizando vectores.
• INDICADOR: Identifica y construye funciones utilizando cadenas.
• INDICADOR: Identifica y construye funciones utilizando registros con campos mutables.
• INDICADOR: Identifica y construye funciones utilizando referencias.
• INDICADOR: Implementa funciones utilizando canales de entrada-salida.
• INDICADOR: Identifica y construye funciones utilizando estructuras de control como secuencias o ciclos.

3.1.1  Teoría

Estilo imperativo.

• complica el sistema del tipo de la lengua, rechazando ciertos programas que de otra manera serían considerados correctos
• tiene que no perder de vista la representación de la memoria y el orden de los cálculos.

• Estructuras de datos modificables como vectores, cadenas, campos mutables y referencias.
• Operaciones de entrada y salida.
• Estructuras de control como secuencias y ciclos.

Estructuras de datos modificables.

Vectores.

• create que crea un arreglo de un tamaño dado con un valor inicial dado
• length retorna la longitud de un vector
• append que concatena dos vectores.
• copy para copiar un vector a otro.

# let m2=[|0;1;2|];;
val m2 : int array = [|0; 1; 2|]
# m2.(0)==m2.(1);;
- : bool = false

# let t = [\|
[| 1 |];
[| 1; 1 |];
[|1; 2; 1|];
[|1; 3; 3; 1|];
[|1; 4; 6; 4; 1|];
[|1; 5; 10; 10; 5; 1|]
|] ;; 

get : 'a array -> int -> 'a
set : 'a array -> int -> 'a -> unit
make : int -> 'a -> 'a array
init : int -> (int -> 'a) -> 'a array
make_matrix : int -> int -> 'a -> 'a array array
append : 'a array -> 'a array -> 'a array
concat : 'a array list -> 'a array
sub : 'a array -> int -> int -> 'a array
copy : 'a array -> 'a array
fill : 'a array -> int -> int -> 'a -> unit
blit : 'a array -> int -> 'a array -> int -> int -> unit
to_list : 'a array -> 'a list
of_list : 'a list -> 'a array
iter : ('a -> unit) -> 'a array -> unit
map : ('a -> 'b) -> 'a array -> 'b array
iteri : (int -> 'a -> unit) -> 'a array -> unit
mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
fold_right : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
sort : ('a -> 'a -> int) -> 'a array -> unit
stable_sort : ('a -> 'a -> int) -> 'a array -> unit
fast_sort : ('a -> 'a -> int) -> 'a array -> unit

Cadenas

Campos mutables

Referencias

Entrada salida: Canales, lectura escritura

Canales

stdin : in_channel
tdout : out_channel
stderr : out_channel

Lectura y escritura

type open_flag =
| Open_rdonly (* open for reading. *)
| Open_wronly (* open for writing. *)
| Open_append (* open for appending: always write at end of file. *)
| Open_creat (* create the file if it does not exist. *)
| Open_trunc (* empty the file if it already exists. *)
| Open_excl (* fail if the file already exists. *)
| Open_binary (* open in binary mode (no conversion). *)
| Open_text (* open in text mode (may perform conversions). *)
| Open_nonblock (* open in non-blocking mode. *)
open_in_bin : string -> in_channel
open_in_gen : open_flag list -> int -> string -> in_channel
input_char : in_channel -> char
input_line : in_channel -> string
input : in_channel -> string -> int -> int -> int
really_input : in_channel -> string -> int -> int -> unit
input_byte : in_channel -> int
input_binary_int : in_channel -> int
input_value : in_channel -> 'a
seek_in : in_channel -> int -> unit
pos_in : in_channel
in_channel_length : in_channel -> int
close_in : in_channel -> unit
close_in_noerr : in_channel -> unit
set_binary_mode_in : in_channel -> bool -> unit

open_out : string -> out_channel
open_out_bin : string -> out_channel
open_out_gen : open_flag list -> int -> string -> out_channel
flush : out_channel -> unit
flush_all : unit -> unit
output_char : out_channel -> char -> unit
output_string : out_channel -> string -> unit
output : out_channel -> string -> int -> int -> unit
output_byte : out_channel -> int -> unit
output_binary_int : out_channel -> int -> unit
output_value : out_channel -> 'a -> unit
seek_out : out_channel -> int -> unit
pos_out : out_channel -> int
out_channel_length : out_channel -> int
close_out : out_channel -> unit
close_out_noerr : out_channel -> unit
set_binary_mode_out : out_channel -> bool -> unit

• input_line ic lee por el canal de entrada ic todos los caracteres hasta el primer retorno del carro o el fin del archivo, y los devuelve en la forma de una lista de caracteres (excepto el retorno del carro).
• entrada ic s p l procura leer 1 carácter del canal de la entrada ic y los almacena en la lista s iniciando con el carácter p th. El número de los caracteres leídos son retornados.
• output oc s p l escribe en el canal de salida oc parte de la lista s , comenzando en el p-esimo - con longitud l.

Estructuras de control: secuencias, ciclos

Secuencias.

Ciclos

3.1.2  Ejercicios para afianzar teoría

1. La función que me permite conocer la longitud de un vector es
   
   
2. La función que me permite conocer el número de filas de una matriz es
   
   
3. Construya un vector v de enteros, de longitud 5 donde los campos del vector este inicializados con -1.
   
   
4. Cree una función c que reciba un entero x y retorne un nuevo vector de caracteres, con x caracteres, cada uno un espacio.
   
   
5. La función Array.copy recibe como parametro.
   
   
6. Escriba un tipo de dato que utilice dos registros mutables y uno no-mutable. Explique el funcionamiento.
   
   
7. 
   
   Construya una referencia x al valor 5.
   
   
8. Construya una referencia z al valor -5 y calcule el resultado de sumar los valores referenciados por x y por z.
   
   
9. Para abrir un archivo si este no existe que excepción se ejecuta?
   
   
10. Escriba una función que abra un canal de entrada, leyendo del archivo leer.txt .

3.1.3  Ejercicios de programación

1. En un archivo vectores.ml escriba las siguientes funciones para manejo de arreglos de tipo entero:
   • creararreglo : dada la longitud y el entero inicial.
   • invertira : dado un arreglo retorna uno nuevo con los mismos elementos del que recibe pero invertidos.
   • sumararreglo : suma dos arreglos (al estilo entero grande), retorna un nuevo arreglo con la suma.
   • prefijoa : recibe un arreglo x y un arrreglo z y dice si z es prefijo de x.
   • sufijoa : recibe un arreglo x y un arrreglo z y dice si z es sufijo de z.
   
   
   
2. En un archivo cat.ml escriba un programa que reciba por línea de comandos el nombre de un archivo y que lo imprima en sálida estándar. Cree un ejecutable y pruebelo. (Ayuda: Para sacar parámetros recibidos por la línea de comandos puede emplear el vector Sys.argv).
   
   
3. En un archivo archivo2.ml escriba un programa que reciba por línea de comandos el nombre de un archivo, un entero a y un entero b. Debe crear un archivo con el nombre recibido en el que cada línea tiene un entero comenzando en b+1 y terminando en a-1, debe generar una excepción definida por usted en caso de que b sea menor o igual a a.
   
   Ejemplo si el intervalo es de 1 a 7 en el archivo debe quedar los números del 2 al 6 de la siguiente forma:
   2
   3
   4
   5
   6
   
   
4. En las fuentes de repasa revise el tipo repasa_interface que mantiene la información requerida tanto por la interfaz modo texto (archivo repasa.ml) como por la interfaz gráfica (archivo repasatk.ml). En este momento están definidos dos tipos de preguntas choiceQuestion y openQuestion. Analice la implementación de ambas en la interfaz modo texto y después agregue un campoHaga el cambio al registro tanto en defprog.ml como en defprog.mli. para un tercer tipo de pregunta ahorcadoQuestion que presente la pregunta y permita al usuario jugar ahorcado para responderla. Para comenzar a implementarla en la interfaz plana copie el cuerpo de openQuestion_plain en ahorcadoQuestion_plain, y haga los cambios necesarios en defprog.ml para que pueda usarse. Compile y verifique sus modificaciones.
   
   Opcional: Implemente la funcionalidad real de ahorcadoQuestion_plain.

3.2  Librerías

• INDICADOR: Conoce diversas funciones de las librerías de Ocaml

3.2.1  Teoría

Librería estándar de Ocaml

• String.length : string -> int retorna la longitud (número de caracteres) de la cadena dada.
  
  
• String.get : string -> int -> char String.get s n retorna el carácter numero n en la cadena s. El primer caracter es el número 0. El último caracter es el número (String.length s) - 1. Lanza Invalid_argument si n está fuera del rango 0 a (String.length s) - 1. También puede escribir s.[n] en lugar de String.get s n.
  
  
• String.set : string -> int -> char -> unit String.set s n c modificar la cadena s, remplazando el caracter número n por c. Lanza Invalid_argument si n está fuera del rango 0 a (String.length s - 1). También puede escribir s.[n] <- c en lugar de String.set s n c.
  
  
• String.create : int -> string String.create n retorna una nueva cade