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 cadena de longitud n. La cadena contiene inicialmente caracteres arbitrarios. Lanza Invalid_argument si n < 0 o n > Sys.max_string_length.
  
  
• String.make : int -> char -> string String.make n c retorna una nueva cadena de longitud n, llenao con el caracter c. Lanza Invalid_argument si n < 0 o n > Sys.max_string_length.
  
  
• String.copy : string -> string Retorna una copia de la cadena dada.
  
  
• String.sub : string -> int -> int -> string String.sub s comienzo long retorna una nueva cadena de longitud len, que contiene los caracteres número comienzo a comienzo + long - 1 de la cadena s. Lanza Invalid_argument si comienzo y long no designan una subcadena válida de s; esto es, si start < 0, o len < 0, o start + len > String.length s.
  
  
• String.fill : string -> int -> int -> char -> unit String.fill s comienzo long c modifica la cadena s, remplazando los caracteres número start a start + len - 1 por c. Lanza Invalid_argument si start y len no designan una subcadena válida de s.
  
  
• String.blit : string -> int -> string -> int -> int -> unit String.blit fuente despfuente dest despdest long copia long caracteres de la cadena fuente, comenzando en el caracter número despfuente, a string dest, comenzando en el caracter despdest. Funciona correctamente incluso si fuente y dest son la misma cadena, y si la fuente y el destino se sobrelapan. Lanza Invalid_argument si despfuente y long no designan una subcadena válida de fuente, o si despdest y long no designan una subcadena válida de dest.
  
  
• String.concat : string -> string list -> string String.concat sep sl concatena la lista de cadenas sl, insertando la cadena separadora sep entre unas y otras.
  
  
• String.iter : (char -> unit) -> string -> unit String.iter f s aplica la función f en orden a todos los caracteres de s. Es equivalente a f s.(0); f s.(1); ...; f s.(String.length s - 1); ().
  
  
• String.escaped : string -> string Retorna una copia del argumento, con los caracteres especiales representados por secuencias de escapes, siguiendo las convenciones léxicas de Objective Caml. Si no hay caracteres especiales en el argumento, retorna la cadena original misma, no una copia.
  
  
• String.index : string -> char -> int String.index s c retorna la posición de la ocurrencia más a la izquierda del caracter c en la cadena s. Lanza Not_found si c no ocurre en s.
  
  
• String.rindex : string -> char -> int String.rindex s c retorna la posición de la ocurrencia más a la derecha del caracter c en la cadena s. Lanza Not_found si c no courre en s.
  
  
• String.index_from : string -> int -> char -> int Análoga a String.index, pero comienza buscando en la posición dada como segundo argumento. String.index s c es equivalente a String.index_from s 0 c.
  
  
• String.rindex_from : string -> int -> char -> int Análoga a String.rindex, pero comienza buscando en la posición dada como segundo argumento. String.rindex s c es equivalente a String.rindex_from s (String.length s -1) c.
  
  
• String.contains : string -> char -> bool String.contains s c verifica si el caracter c aparece en la cadena s.
  
  
• String.contains_from : string -> int -> char -> bool String.contains_from s comienzo c verifica si el caracter c aparece en la subcadena de s que comienza en comienzo hasta el inal de s. Lanza Invalid_argument si comienzo no es un índice válido de s.
  
  
• String.rcontains_from : string -> int -> char -> bool String.rcontains_from s fin c verifica si el caracter c aparece en la subcadena de s que comienza al comienzo de s hasta el índice stop. Lanza Invalid_argument si stop no es un índice válido de s.
  
  
• String.uppercase : string -> string Retorna una copia del argumento, con todas las letras minúsculas traducidas a mayúsculas, incluyendo letras acentuadas del conjunto de caracteres ISO Latin-1 (8859-1).
  
  
• String.lowercase : string -> string Retorna una copia del argumento, con todas las letras mayúsculas traducidas a minúsculas, incluyendo letras acentuada del conjunto de caracteres ISO Latin-1 (8859-1).
  
  
• String.capitalize : string -> string Retorna una copia del argumento, con la primera letra en mayúscula.
  
  
• String.uncapitalize : string -> string Retorna una copia del argumento, con la primera letra en minúsculas.
  
  
• String.type t = string Alias para el tipo cadena.
  
  
• String.compare : String.t -> String.t -> int Función de comparación para cadenas, con la misma especificación de Pervasives.compare. Junto con el tipo String.t, esta función compare permite que el módulo String sea pasado como argument a los funtores Set.Make y Map.Make.

• List.length : 'a list -> int Retorna la longtiud (número de elementos) de la lista dada.
  
  
• List.hd : 'a list -> 'a Retorna el primer elemento de la lista dado. Lanaz Failure "hd" si la lista es vacía.
  
  
• List.tl : 'a list -> 'a list Retorna la lista dada sin el primero elemento. Lanza Failure "tl" si la lista es vacía.
  
  
• List.nth : 'a list -> int -> 'a Retorna el n-esimo elemento de la lista dada. El primer elemento (cabeza de la lista) está en la posición 0. Lanza Failure "nth" si la listas es muy corta.
  
  
• List.rev : 'a list -> 'a list Invierte la lista.
  
  
• List.append : 'a list -> 'a list -> 'a list Concatena dos listas. La misma función del operador infijo @. No emplea recursión de cola (longitud del primer argumento). El operador @ tampoco emplea recursión de cola.
  
  
• List.rev_append : 'a list -> 'a list -> 'a list List.rev_append l1 l2 invierte l1 y lo concatena a l2. Esto es equivalente a List.rev l1 @ l2, pero rev_append emplea recursión de cola y es más eficiente.
  
  
• List.concat : 'a list list -> 'a list Concatena una lista de listas. Los elementos del argumento son todos concatenadso (en el mismo orden). No emplea recursión de cola (longitud del argumento + longitud de la sub-lista más larga).
  
  
• List.flatten : 'a list list -> 'a list Lo mismo que concat. No emplea recursión de cola (longitud del argumento + longitud de la sub-lista más larga).

• List.iter : ('a -> unit) -> 'a list -> unit List.iter f [a1; ...; an] aplica la función f en orden a a1; ...; an. Es equivalente a begin f a1; f a2; ...; f an; () end.
  
  
• List.map : ('a -> 'b) -> 'a list -> 'b list List.map f [a1; ...; an] aplica la función f a a1, ..., an, y construye la lista [f a1; ...; f an] con los resultados retornados por f. No emplea recursión de cola.
  
  
• List.rev_map : ('a -> 'b) -> 'a list -> 'b list List.rev_map f l da el mismo resultado de List.rev(List.mapf l), pero emplea recursión de cola y es más eficiente.
  
  
• List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a List.fold_left f a [b1; ...; bn] es f (... (f (f a b1) b2) ...) bn.
  
  En el archivo lrepasa.ml del programa repasa, puede verse una función que emplea
  List.fold_left:

  (** [txt2tex s] Translates the string [s] with pure text to plain TeX *)
  let rec txt2tex s =
          (* order is important,  \, $, {, } *)
          let convt=[
                          ("\\","$\\backslash$");
                          ("$","\\$");
                          ("\\$\\backslash\\$","$\\backslash$");
                          ("{","$\\{$");
                          ("}","$\\}$");
                          ("%","\\%");
                          ("_","\\_");
                          ("&","\\&");
                          ("#","\\#");
                          ("^","\\^{\\kern0em}");
                          ("~","\\~{\\kern0em}");
                          ("¿","?`");
                          ("¡","!`");
                  ]
          in
          let s=List.fold_left apply_str_conv s convt in
          let rec transquote state s =
                  if (String.contains s '"') then
                          let i=String.index s '"' in
                          let l=str_to s i in
                          let r=str_from s (i+1) in
                          let c=if state then "``" else "''" in
                          transquote (not state) (l^c^r)
                  else
                          s
          in transquote true s
  ;;
  

  
  
  
• List.fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b List.fold_right f [a1; ...; an] b es f a1 (f a2 (... (f an b) ...)). No emplea recursión de cola.

• List.iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit List.iter2 f [a1; ...; an] [b1; ...; bn] llama en orden f a1 b1; ...; f an bn. Lanza Invalid_argument si las dos listas tiene longitudes diferentes.
  
  
• List.map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list List.map2 f [a1; ...; an] [b1; ...; bn] es [f a1 b1; ...; f an bn]. Lanza Invalid_argument si las dos listas tienen longitudes diferentes. No emplea recursión de cola.
  
  
• List.rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list List.rev_map2 f l da el mismo resultado de List.rev(List.map2f l), pero emplea recursión de cola y es más eficiente.
  
  
• List.fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a List.fold_left2 f a [b1; ...; bn] [c1; ...; cn] es f (... (f (f a b1 c1) b2 c2) ...) bn cn. Lanza Invalid_argument si las dos listas tienen longitudes diferentes.
  
  
• List.fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c List.fold_right2 f [a1; ...; an] [b1; ...; bn] c es f a1 b1 (f a2 b2 (... (f an bn c) ...)). Lanza Invalid_argument si las dos listas tienen longitudes diferentes. No emplea recursión de cola.

• List.for_all : ('a -> bool) -> 'a list -> bool for_all p [a1; ...; an] chequea si todos los elementos de la lista satisfacen el predicado p. Es decir retorna (p a1) && (p a2) && ... && (p an).
  
  
• List.exists : ('a -> bool) -> 'a list -> bool exists p [a1; ...; an] chequea si al menos un elemento de la lista satisface el predicado p. Es decir, retorna (p a1) || (p a2) || ... || (p an).
  
  
• List.for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool Análoga a List.for_all, pero para un predicado de dos argumentos. Lanza Invalid_argument si las dos listas tienen longitudes diferentes.
  
  
• List.exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool Análoga a List.exists, pero para un predicado de dos argumentos. Lanza Invalid_argument si las dos listas tienen longitudes diferentes.
  
  
• List.mem : 'a -> 'a list -> bool mem a l es cierto si y solo si a es igual a un elemento l.
  
  En el archivo lrepasa.ml del programa repasa, puede verse una función que emplea
  List.fold_left:

  (** [add_markup_path path] If it doesn't exists adds the path [path] 
      to the paths where XMLs and DTDs opened by Markup are looked for 
      (with higher priority than exisiting entries *)
  let add_markup_path path =
          if (not (List.mem path (!Markup_reader.default_dirs))) then
                  Markup_reader.default_dirs:=path::(!Markup_reader.default_dirs)
  ;;
  

  
  
  
• List.memq : 'a -> 'a list -> bool Anágloa a List.mem, pero usa igualdad física en lugar de igualdad estructura para comparar elementos de la lista.

• List.find : ('a -> bool) -> 'a list -> 'a find p l retorna el primer elemento de la lista l que satisfaga el predicado p. Lanza Not_found si there is ningún valor de la lista l satisface p.
  
  
• List.filter : ('a -> bool) -> 'a list -> 'a list filter p l retorna todos los elementos de la lista l que satisfacen el predicado p. El orden de los elementos en la lista de entrada se mantiene.
  
  
• List.find_all : ('a -> bool) -> 'a list -> 'a list find_all es otro nombre para List.filter.
  
  
• List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list partition p l retorna un par de listas (l1, l2), done l1 es la lista de todos los elementos de l que satisfacen el predicado p, y l2 es la lista de todos los elementos de l que no satisfacen p. El orden de los elementos de la lista de entrada se preserva.

• List.assoc : 'a -> ('a * 'b) list -> 'b assoc a l retorna el valor asociado con la llave a en la lista de parejas l. Es decir, assoc a [ ...; (a,b); ...] = b si (a,b) es la asociación más a la izquierda de a en la lista l. Lanza Not_found si no hay valor asociado con a en la lista l.
  
  
• List.assq : 'a -> ('a * 'b) list -> 'b Lo mismo que List.assoc, pero emplea igualdad física en lugar de igualdad estructural al comparar las llaves.
  
  
• List.mem_assoc : 'a -> ('a * 'b) list -> bool Lo mismo que List.assoc, pero simplemente retorna true si existe una asociación, y false si no existe asociación alguna para la llave dada.
  
  
• List.mem_assq : 'a -> ('a * 'b) list -> bool Lo mismo que List.mem_assoc, pero empleaa igualdad física en lugar de igualdad estrucutra al comparar llaves.
  
  
• List.remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list remove_assoc a l retorna la lista de parejas l sin la primera pareja con llave a, si hay alguna. No emplea recursión de cola.
  
  
• List.remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list Igual al List.remove_assoc, pero usa igualdad física en lugar de igualdad estructural al comparar llaves. No emplea recursión de cola.

• List.split : ('a * 'b) list -> 'a list * 'b list Transforma una lista de parejas en un par de listas: split [(a1,b1); ...; (an,bn)] es ([a1; ...; an], [b1; ...; bn]). No emplea recursión de cola.
  
  
• List.combine : 'a list -> 'b list -> ('a * 'b) list Transforma un par de listas en una lista de parejas: combine [a1; ...; an] [b1; ...; bn] es [(a1,b1); ...; (an,bn)]. Lanza Invalid_argument si las dos listas tienen longitudes diferentes. No emplea recursión de cola.

• List.sort : ('a -> 'a -> int) -> 'a list -> 'a list Ordena una lista ascendemente de acuerdo a una función de comparación. La función de comparación debe retornar 0 si los argumentos comparados son iguales, un entero positivo si el primero es mayor y un entero negvor si el primer el primero es menor (ver una especificación comnpleta en Array.sort). Por ejemplo Pervasives.compare es una función de comparación apropiada, siempre que no haya valores de tipo flotante NaN entre los datos. La lista resultante está ordenada en orden ascendiente. Se garantiza que List.sort corre en espacio de datos constante (además del tamaño de la lista resultante) y en espacio de pila logarítmico.
  
  La implementación actual emplea Merge Sort.
  
  
• List.stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list Iguala a List.sort, se garantiza que el algoritmo de ordenamiento es estable (i.e los elementos que se comparan como iguales se mantienen en su orden origianal).
  
  La implmentación actual emplea Merge Sort. Corre en espacio de datos constante y espacio de pila logaritmico.
  
  
• List.fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list Igual a List.sort o List.stable_sort, el que resulte más rapido sobre una entrada típica.
  
  
• List.merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list Mezcla dos listas: Supone que l1 y l2 son ordenadas de acuerdo a la función de comparación cmp, merge cmp l1 l2 retornará un lista ordenada que contiene todos los elementos de l1 y l2. Si diversos elementos se comparan como igual, los elementos de l1 estarán antes de los elementos de l2. No emplea recursión de cola (suma de las longitudes de los argumentos).

• type ('a, 'b) Queue.t
  
  El tipo de tablas de hash con llave de tipo 'a y valor de tipo 'b.
  
  
• Hashtbl.create : int -> ('a, 'b) t Hashtbl.create n crea una nueva tabla de hash, vacia, con tamaño inicial n. Para mejores resultaso n debería ser del orden del número de elementos esperados en la tabla. La tabla crece cuando se necesita, de forma que n es sólo una aproximación inicial.
  
  
• Hashtbl.clear : ('a, 'b) t -> unit Deja vacía una tabla de hash.
  
  
• Hashtbl.add : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.add tbl x y agrega una asociación de x en y en la tabla tbl. Las asociaciones previas de x no se eliminadas, sino tan sólo escondidas. Es decir, después de efectuar Hashtbl.removetbl x, la asociacón anterior para x, si hay alguna, se restaurará. (El mismo comporatmiento de listas asociativas.)
  
  
• Hashtbl.copy : ('a, 'b) t -> ('a, 'b) t Retorna una copia de la tabla de hash dada.
  
  
• Hashtbl.find : ('a, 'b) t -> 'a -> 'b Hashtbl.find tbl x retorna la asociación actual de x en tbl, o lanza Not_found si no existe tal asociación.
  
  
• Hashtbl.find_all : ('a, 'b) t -> 'a -> 'b list Hashtbl.find_all tbl x retorna la lista de todos los datos asociados con x en tbl. La asociación actual se retorna primero, y a continuación las asociaciones anteriores, en orden inverso al de introducción en la tabla.
  
  
• Hashtbl.mem : ('a, 'b) t -> 'a -> bool Hashtbl.mem tbl x revisa si x está asociado en tbl.
  
  
• Hashtbl.remove : ('a, 'b) t -> 'a -> unit Hashtbl.remove tbl x elimina la asociación actual de x en tbl, restaurando la asociación previa, si existe. No hace nada si x no está asociada en tbl.
  
  
• Hashtbl.replace : ('a, 'b) t -> 'a -> 'b -> unit Hashtbl.replace tbl x y remplaza la asociación actual de x en tbl con una asociación de x en y. Si x no está asociada en tbl, se agrega una asociación de x en y a tbl. Es funcionalmente equivalente a Hashtbl.remove tbl x seguido de Hashtbl.add tbl x y.
  
  
• Hashtbl.iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit Hashtbl.iter f tbl aplica la función f a todas las asociaciones de la tabla tbl. f recibe como primer argumento la lleva, y el valor asociado como segundo argumento. Cada asoicacion se presenta exactamente una vez a f. El orden en el cual las asociacioens son pasadas a f no está especificado. Sin embargo, si la tabla contiene diversas asociaciones para la misma llave, estás se pasan a f en orden inverso al de introducción, es decir las asociaciones más reciente son pasadas primero.
  
  El siguiente ejemplo ha sido tomado de la librería de repasa (lrepasa.ml):

  (** [hashtbl_first h p] Returns a key of the hashing table [h] that satisfies 
      the predicate [p].
     @return If none exists returns None.  If one exists returns Some k.
  *)
  let rec hashtbl_first h p=
          let found=ref false in
          let elem=ref None in
          let f k d=
                  if (not (!found) && (p k)) then
                  begin
                          found:=true;
                          elem:=Some k
                  end
         in
         Hashtbl.iter f h ;
          !elem
  ;;
  

  
  
  
• Hashtbl.fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c Hashtbl.fold f tbl init computa (f kN dN ... (f k1 d1 init)...), donde k1 ... kN son las llaves de todas las asociaciones en tbl, y d1 ... dN son los valores asociados. Cada asociación se presenta exactamente una vez a f. El orden en el cual las asociacioens son pasadas a f no está especificado. Sin embargo, si la tabla contiene diversas asociaciones para la misma llave, estás se pasan a f en orden inverso al de introducción, es decir las asociaciones más reciente son pasadas primero.

• Hashtbl.hash : 'a -> int Hashtbl.hash x asocia un entero positivo a un valor arbitrario de tipo arbitrario. Se garantiza que si x = y, entonces hash x = hash y. Además, hash siempre termina, incluso en estructuras cíclicas.
  
  
• Hashtbl.hash_param : int -> int -> 'a -> int Hashtbl.hash_param n m x computa un valor de hash para x, con las misas propiedades de hash. Los dos parámetros extra n y m dan un control más preciso sobre el hashing. Se realiza un recorrido a profunidad primero, de derecha a izquierda de la estructura x, deteniendose después de n nodos significativos, o después de m nodos significativos o no. Los nodos significativos son: enteros, números de punto flotante, cadenas, caractres, booleanos y constructores constantes. Valores más grandes de m y n significan que más nodos se tienen en cuenta al computar el valor de hash final, y por tanto es menos probable que ocurran colisiones. Sin embargo, el hashing requiere más tiempo. Los parámetros m y n gobiernan el equilibrio entre precisión y velocidad.

• type 'a Queue.t
  
  El tipo de colas que contienen elementos de tipo 'a.
  
  
• exception Queue.Empty
  
  Lanzada cuando Queue.take o Queue.peek se aplican a colas vacías.
  
  
• Queue.create : unit -> 'a t Retorna una nueva cola, inicialmente vacía.
  
  
• Queue.add : 'a -> 'a t -> unit add x q agrega el elemento x al final de la cola q.
  
  
• Queue.push : 'a -> 'a t -> unit push es sinónimo de add.
  
  
• Queue.take : 'a t -> 'a take q elimina y retorna el primer elemento de la cola q, o lanza Empty si la cola es vacía.
  
  
• Queue.pop : 'a t -> 'a pop es sinónimo de take.
  
  
• Queue.peek : 'a t -> 'a peek q retorna el primer elemento de la cola q, sin eliminarlo de la cola, o lanza Empty si la cola está vacía.
  
  
• Queue.top : 'a t -> 'a top es sinónimo de peek.
  
  
• Queue.clear : 'a t -> unit Descarta todos los elementos de la cola.
  
  
• Queue.copy : 'a t -> 'a t Retorna una copia de la cola dada.
  
  
• Queue.is_empty : 'a t -> bool Retorna true si la cola dada está vacía, false en otro caso.
  
  
• Queue.length : 'a t -> int Retorna el número de elementos en una cola.
  
  
• Queue.iter : ('a -> unit) -> 'a t -> unit iter f q aplica f en sucesión a todos los elementos de q, desde el ingresado menos recientemente hasta el ingresado más recientemente. La cola misma no es modificada.
  
  
• Queue.fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a fold f accu q es equivalente a List.fold_left f accu l, donde l es la lista con los elementos de q. La cola no es modificada.
  
  
• Queue.transfer : 'a t -> 'a t -> unit transfer q1 q2 agrega todos los elementos de q1 al final de la cola q2, después limpia q1. Es equivalente a la secuencia iter (fun x -> add x q2) q1; clear q1, pero se ejecuta en tiempo constante.

• type 'a Stack.t El tipo de pilas que contienen elementos de tipo 'a.
• exception Stack.Empty Lanzada cuando se aplican Stack.pop o Stack.top a pilas vacías.
  
  
• Stack.create : unit -> 'a t Retorna una nueva pila, inicialmente vacía.
  
  
• Stack.push : 'a -> 'a t -> unit push x s agrega el elemento x en el tope de la pila s.
  
  
• Stack.pop : 'a t -> 'a pop s elimina y retorna el elemento del topo de la pila s, o lanza Empty si la pila está vacía.
  
  
• Stack.top : 'a t -> 'a top s rtorna el elemento que está en el tope de la pila s, or lanza Empty si la pila está vacía.
  
  Por ejemplo en las fuentes de la librería Markup (ver [6]), se emplea la siguiente porción de código que tiene la funcionalidad de top:

  method current =
          (* Get the top element of the element stack *)
          (* In O'Caml 3: Stack.top *)
          try
            let x = Stack.pop elstack in
            Stack.push x elstack;
            let el, entid = x in
            el
          with
              Stack.Empty -> assert false
                  (* Not possible, because the VR is always the element at the
                   * bottom of the stack.
                   *)
  

  
  
  
• Stack.clear : 'a t -> unit Descarta todos los elementos de una pila.
  
  
• Stack.copy : 'a t -> 'a t Retorna una copia de la pila dada.
  
  
• Stack.is_empty : 'a t -> bool Retorna true si la pila dada está vacía, false en otro caso.
  
  
• Stack.length : 'a t -> int Retorna el número de elementos de una pila.
  
  
• Stack.iter : ('a -> unit) -> 'a t -> unit iter f s aplica f en sucesión a los elementos s, desde el elemento que está en el tope hasta el del fondo. La pila no es modificada.

• type Buffer.t Tipo abstracto de un buffer.
  
  
• Buffer.create : int -> t create n retorna un buffer nuevo, inicialmente vació. El parámetro n es el tamaño de la cadena interna inicial que mantendrá el contenido del buffer. Tal cadena es relocalizada automáticamente cuando se almacenan más de n caracteres en el buffer, pero vuelve a encogerse a n caracteres cuando se llama reset. Para una mejor desempeño, n deb ser del mismo orden de magnitud que el número de caracteres que se espera almacenar en el buffer (por ejemplo, 80 para un buffer que mantendrá una línea de salida). No ocurrirá nada mal si el buffer crece más alla de este límite. En caso de duda, tome por ejemplo n = 16. Si n no está entre 1 y Sys.max_string_length, será ajustado a ese intervalo.
  
  
• Buffer.contents : t -> string Retorna una copia del contenido del buffer. El buffer mismo no es modificado.
  
  
• Buffer.length : t -> int Retorna el número de caracters que contien el buffer.
  
  
• Buffer.clear : t -> unit Limpia el buffer.
  
  
• Buffer.reset : t -> unit Limpia el buffer, y deslocaliza la cadena interna que mantiene el contenido del buffer, remplazandolo con la cadena interna inicial de longitud n como fue localizada por Buffer.create n. Para buffers de larga vida que pudieran haber crecido mucho, reset permite reclamar más rapidamente el espacio empleado por el buffer.
  
  
• Buffer.add_char : t -> char -> unit add_char b c agrega el caracter c al final del buffer b.
  
  
• Buffer.add_string : t -> string -> unit add_string b s agrega la cadena s al final del buffer b.
  
  
• Buffer.add_substring : t -> string -> int -> int -> unit add_substring b s ofs long toma long caracteres desde la posición ofs de la cadena s y los agrega al final del buffer b.
  
  
• Buffer.add_substitute : t -> (string -> string) -> string -> unit add_substitute b f s agrega la cadena patrón s al final del buffer b substituyendo. El proceso de substitución busca variables en el patron y sustituye cada nombre de variable por su valor, como se obtiene al aplicar la función f al nombre de la variable. En la cadena patrón, el nombre de una variable está precedido de un caracter no escapado $ y es una de las siguientes::
  • una secuencia no vacía de caracteres alfanuméricos o el caracter _,</li>
  • una secuencia arbitraria de caracteres encerrada por un par de paréntesis o llaves.
  • Un caracter $ escapado es un $ precedido por un caracter backslash; representa un $ plano. Lanza Not_found si el caracter que cierra una variable entre parentesis o llaves no se encuentra.
  
  
  
• Buffer.add_buffer : t -> t -> unit add_buffer b1 b2 agrega el contenido actual del buffer b2 al final del buffer b1. b2 no es modificado.
  
  
• Buffer.add_channel : t -> Pervasives.in_channel -> int -> unit add_channel b ic n lee exactamente n caracteres del canal de entrada ic y los almacena al final del buffer b. Lanza End_of_file si el canal tiene menos de n caracteres.
  
  
• Buffer.output_buffer : Pervasives.out_channel -> t -> unit output_buffer oc b escrite el contenido actual del buffer b en el canal de salida oc.

module IdSet=Set.Make(struct
                type t=string*string*string
                let compare (s1,s2,s3) (sa,sb,sc) =
                        if (s1<sa || (s1=sa && s2<sb)
                                || (s1=sa && s2=sb && s3<sc)) then
                                -1
                        else if (s1=sa && s2=sb && s3=sc) then
                                0
                        else
                                1
                end)
;;

• type elt Tipo de los elementos del conjunto.
• type t Tipo de los conjuntos.
• Set.empty : t El conjunto vació.
  
  
• Set.is_empty : t -> bool Chequea si un conjunto es vacío o no.
  
  
• Set.mem : elt -> t -> bool mem x s chequea si x pertenece al conjunto s.
  
  
• Set.add : elt -> t -> t add x s retorna uun conjunto que contiene todos los elementos de s, y a x. Si x ya estaba en s, s es retornado sin cambios.
  
  
• Set.singleton : elt -> t singleton x retorna el conjunto de un elemento que contiene a x.
  
  
• Set.remove : elt -> t -> t remove x s retorna un conjunto que contiene todos los elementos de s, excepto x. Si x no estaga en s, s es retornado sin cambios.
  
  
• Set.union : t -> t -> t Unión de conjuntos.
  
  
• Set.inter : t -> t -> t Intersección de conjuntos.
  
  
• Set.diff : t -> t -> t Diferencia entre conjuntos.
  
  
• Set.compare : t -> t -> int Ordenamiento total entre conjuntos. Puede emplearse como función de comparación para hacer conjuntos de conjuntos.
  
  
• Set.equal : t -> t -> bool equal s1 s2 chequea si los conjuntos s1 y s2 son iguales, es decir, si contienen elementos iguales.
  
  
• Set.subset : t -> t -> bool subset s1 s2 chequea si el conjunto s1 es subconjunt del conjunto s2.
  
  
• Set.iter : (elt -> unit) -> t -> unit iter f s aplica f en sucesión a todos los elementos de s. El orden en el que los elementos de s se presentan a f no está especificado.
  
  
• Set.fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a fold f s a computa (f xN ... (f x2 (f x1 a))...), donde x1 ... xN son los elementos de s. El orden en el que los elementos de s se presentan a f no está especificado.
  
  
• Set.for_all : (elt -> bool) -> t -> bool for_all p s verifica si todos los elementos del conjunto satisfacen el predicado p.
  
  
• Set.exists : (elt -> bool) -> t -> bool exists p s verifica si al menos un elemento del conjunto satisface el predicado p.
  
  
• Set.filter : (elt -> bool) -> t -> t filter p s retorna el conjunto de todos los elementos en s que satisfacen el predicado p.
  
  
• Set.partition : (elt -> bool) -> t -> t * t partition p s retorna un par de conjuntos (s1, s2), donde s1 es el conjunto de todos los elementos de s que satisface el predicado p, y s2 es el conjunto de todos los elementos de s que no satisfacen p.
  
  
• Set.cardinal : t -> int Retorna el número de elementos de un conjunto.
  
  
• Set.elements : t -> elt list Retorna la lista de todos los elementos del conjunto dado. La lista retornada está ordenada ascendemente con respecto al orden Ord.compare, donde Ord es el argumento dado a Set.Make.
  
  
• Set.min_elt : t -> elt Retorna el elemento más pequeño del conjunt dado (con respecto al orden Ord.compare), o lanza Not_found si el conjunto es vacío.
  
  
• Set.max_elt : t -> elt Igual que Set.S.min_elt, pero retorna el mayor elemento del conjunto dado.
  
  
• Set.choose : t -> elt Retorna un elemento del conjunto dado, o lanza Not_found si el conjunto es vacío. El elemento escogido no está especificado, pero elementos iguales serán retornados con conjuntos iguales.

• type key Tipo de las llaves del mapeo.
  
  
• type +'a t Tipo de los mapeos del tipo key al tipo 'a.
  
  
• Map.empty : 'a t El mapeo vacío.
  
  
• Map.add : key -> 'a -> 'a t -> 'a t add x y m retorna un mapeo que contiene las misma asociaciones de m, además de una asociación de x a y. Si x ya estaba asociada en m, su asociación anterior desaparece.
  
  
• Map.find : key -> 'a t -> 'a find x m retorna la asociación actual de x en m, o lanza Not_found si no existe tal asociación.
  
  
• Map.remove : key -> 'a t -> 'a t remove x m retorna un mapeo que contiene las mismas asociaciones de m, excepto porque x no está asociado en el mapeo retornado.
  
  
• Map.mem : key -> 'a t -> bool mem x m retorna true si m contiene una asociación para x, o false en otro caso.
  
  
• Map.iter : (key -> 'a -> unit) -> 'a t -> unit iter f m aplica f a todas las asociaciones en el mapeo m. f recibe la llave como primer argumento, y el valor asociado como segundo argumento. El orden en el cual la asociación se pasa a f no está especificado. Sólo las asociaciones actuales se presenta a f: asociaciones escondidas por asociaciones más recientes no son pasadas a f.
  
  
• Map.map : ('a -> 'b) -> 'a t -> 'b t map f m retorna un mapeo con el mismo dominio de m, done el valor asociado x de cada asociación de m se ha remplazado por el resultado de la aplicación de f a x. El orden en el que los valores asociados se pasan a f no está especificado.
  
  
• Map.mapi : (key -> 'a -> 'b) -> 'a t -> 'b t Lo mismo que Map.S.map, pero la función recibie como argumentos tanto la llave como el valor asociado por cada asociación en el mapeo.
  
  
• Map.fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b fold f m a computa (f kN dN ... (f k1 d1 a)...), donde k1 ... kN son las llaves de todas las asociaciones de m, y d1 ... dN son los datos asociados. El orden en el cual las asociaciones se presenta a f no está especificado.

• Random.init : int -> unit Inicializa el generado, usano el argumento como semilla. La misma semilla siempre producirá la misma secuencia de números.
  
  
• Random.full_init : int array -> unit Lo mismo que Random.init pero recibe más datos como semilla.
  
  
• Random.self_init : unit -> unit Inicializa el generador con una semila más o menos aleatorioa de una manera dependiente del sistema.
  
  
• Random.bits : unit -> int Retorna 30 bits aleatorios en un entero no negativo.
  
  
• Random.int : int -> int Random.int bound retorna un entero aleatorio entre 0 (inclusive) y bound (exclusivo). bound debe ser mayor a 0 y menor que 2³0.
  
  
• Random.int32 : Int32.t -> Int32.t Random.int32 bound retorna un entero aleatorio entre 0 (inclusive) y bound (exclusivo). bound debe ser mayor a 0.
  
  
• Random.nativeint : Nativeint.t -> Nativeint.t Random.nativeint bound retorna un entero aleatorio entre 0 (inclusive) y bound (exclusivo). bound debe ser mayor que 0.
  
  
• Random.int64 : Int64.t -> Int64.t Random.int64 bound retorna un entero aleatorio entre 0 (inclusive) y bound (exclusivo). bound debe ser mayor que 0.
  
  
• Random.float : float -> float Random.float bound retorna un número de punto f lotante entre 0 (inclusive) y bound (exclusivo). Si bound es negativo, el resultado es negativo o cero. Si bound es 0, el resultado es 0.
  
  
• Random.bool : unit -> bool Random.bool () retorna true o false con probabilidad 0.5 cada uno.

• type t= {
   re:float;
   im:float
  
  }
  

  Tipo para números complejos. re es parte real y im la parte imaginaria.
  
  
• Complex.zero : t El número complejo 0.
  
  
• Complex.one : t El número complejo 1.
  
  
• Complex.i : t El número complejo i.
  
  
• Complex.neg : t -> t Negación unaria.
  
  
• Complex.conj : t -> t Conjutado: dado el complejo x + i.y, retorna x - i.y.
  
  
• Complex.add : t -> t -> t Suma
  
  
• Complex.sub : t -> t -> t Resta
  
  
• Complex.mul : t -> t -> t Multiplicación
  
  
• Complex.inv : t -> t Inverso multiplicativo (1/z).
  
  
• Complex.div : t -> t -> t División
  
  
• Complex.sqrt : t -> t Raíz cuadrada. El resultado x + i.y es tal que x > 0 o x = 0 y y >= 0. Esta función tiene una discontinuada sobre el eje real negativo.
  
  
• Complex.norm2 : t -> float Cuadrado de la norma: dado x + i· y, retorna x² + y².
  
  
• Complex.norm : t -> float Norma: dado x + i.y, retorna sqrt(x² + y²).
  
  
• Complex.arg : t -> float Argumento. El argumento de un número complejo es el ángulo en el plano complejo entre el eje real positivo y una línea que pasa por cero y el número. Este ágnulo varía de -pi a pi. Esta función tiene una discontinuidad sobre el eje real negativo.
  
  
• Complex.polar : float -> float -> t polar norm arg retorna el complejo que tiene norma norm y argumento arg.
  
  
• Complex.exp : t -> t Exponenciación. exp z retorna e elevado a la z potencia.
  
  
• Complex.log : t -> t Logaritmo natural en base e.
  
  
• Complex.pow : t -> t -> t Función potencia. pow z1 z2 retorna z1 elevado a la z2.

• Int32.zero : int32 El entero 0 de 32 bits.
  
  
• Int32.one : int32 El entero 1 de 32 bits.
  
  
• Int32.minus_one : int32 El entero -1 de 32 bits
  
  
• Int32.neg : int32 -> int32 Negación unaria.
  
  
• Int32.add : int32 -> int32 -> int32 Suma.
  
  
• Int32.sub : int32 -> int32 -> int32 Resta.
  
  
• Int32.mul : int32 -> int32 -> int32 Multiplicación.
  
  
• Int32.div : int32 -> int32 -> int32 Divsión entera. Lanza Division_by_zero si el segundo argumento es cero. Esta división redondea el coociente de su argumento a cero, como se especifica para Pervasives..
  
  
• Int32.rem : int32 -> int32 -> int32 Residuo entero. Si y no es cero, el resultado de Int32.rem x y satisface las siguientes propiedades: Int32.zero <= Int32.rem x y < Int32.abs y y x = Int32.add (Int32.mul (Int32.div x y) y) (Int32.rem x y). Si y = 0, Int32.rem x y lanza Division_by_zero.
  
  
• Int32.succ : int32 -> int32 Sucesor. Int32.succ x es lo mismo que Int32.add x Int32.one.
  
  
• Int32.pred : int32 -> int32 Predecesor. Int32.pred x es lo mismo que Int32.sub x Int32.one.
  
  
• Int32.abs : int32 -> int32 Retorna el valor absoluto de su argumento.
  
  
• Int32.max_int : int32 El entero de 32 bits más grande que puede representarse, 2³¹-1.
  
  
• Int32.min_int : int32 El menor entero de 32 bits que puede representarse, -2³¹.
  
  
• Int32.logand : int32 -> int32 -> int32 Cojunción lógica a nivel de bits.
  
  
• Int32.logor : int32 -> int32 -> int32 Disyunción lógica a nivel de bits.
  
  
• Int32.logxor : int32 -> int32 -> int32 O exclusivo a nivel de bits.
  
  
• Int32.lognot : int32 -> int32 Negación lógica a nivel de bits.
  
  
• Int32.shift_left : int32 -> int -> int32 Int32.shift_left x y corre x a la izquerda y bits. El resultado no está especificado si y < 0 o y >= 32.
  
  
• Int32.shift_right : int32 -> int -> int32 Int32.shift_right x y corre x a la derecho y bits. Este es un corrimiento aritmético: el bit de signo de x es replicado e insertado en los bits desocupados. El resultado no está especificado si y < 0 o y >= 32.
  
  
• Int32.shift_right_logical : int32 -> int -> int32 Int32.shift_right_logical x y corre x hacia la derecha, y bits. Este es un corrimiento lógico: se insertan ceros en los bits desocupados, independiente del signo de x. El resultado no está especificado si y < 0 o y >= 32.
  
  
• Int32.of_int : int -> int32 Convierte el entero dado (tipo int) a un entero de 32-bits (tipo int32).
  
  
• Int32.to_int : int32 -> int Convierte el entero de 32-bits dado (tipo int32) a un entero (tipo int). En plataformas de 32-bits, los enteros de 32-bits son tomados módulo 2³1, i.e. el bit del orden más alto se pierde durante la conversión. En plataformas de 64 bits la conversión es exacta.
  
  
• Int32.of_float : float -> int32 Convierte el número de punto flotanto a un entero de 32 bits, descartando la parte decimal (trunca hacía 0). El resultado de la conversión es indefinido si después de truncar, el número está fuera del rango [Int32.min_int, Int32.max_int].
  
  
• Int32.to_float : int32 -> float Convierte el entero de 32 bits a un número de punto flotante.
  
  
• Int32.of_string : string -> int32 Convierte la cadena dada a un entero de 32 bits. La cadena se lee en decimal (por defecto) o en hexadecimal o en octal o en binario si la cadena comienza con 0x, 0o o 0b respectivamente. Lanza Failure "int_of_string" si la cadena dada no es una representación válida de un entero.
  
  
• Int32.to_string : int32 -> string Retorna la representación como cadena del argumento, es un decimal con signo.
  
  
• type t = int32
  
  Un álias para el tipo de enteros de 32 bits.
  
  
• Int32.compare : t -> t -> int La función de comparación para enteros de 32 bits, con la misma especificación de Pervasives.compare. Junto con el tipo t, esta función compare permite que el módulo Int32 sea pasado como argumento a los functores Set.Make y Map.Make.

• Int64.of_int32 : int32 -> int64 Convierte el entero de 32 bits dado a un entero de 64.
  
  
• Int64.to_int32 : int64 -> int32 Convierte el entero de 64 bits dato a un entero de 32 bits. El entero de 64 bits se toma módulo 2³2, i.e. los 32 bits superiores se pierden durante la conversión.
  
  
• Int64.of_nativeint : nativeint -> int64 Convierte el entero nativo dado (tipo nativeint) a un entero de 64-bits (tipo int64).
  
  
• Int64.to_nativeint : int64 -> nativeint Convierte el entero de 64 bits datos a un entero nativo. En plataformas de 32 bits, el entero de 64 bits es tomado módulo 2³2. En plataformas de 64 bits la conversión es exacta.

• NativeInt.size : int El tamaño en bits de un entero nativo. Es igual a 32 en plataformas de 32 bits y a 64 en plataformas de 64 bits.
  
  
• NativeInt.of_int32 : int32 -> nativeint Convert the given 32-bit integer (type int32) to a native integer.
  
  
• NativeInt.to_int32 : nativeint -> int32 Convert the given native integer to a 32-bit integer (type int32). On 64-bit platforms, the 64-bit native integer es taken modulo 2<sup class="superscript">32</sup>, i.e. the top 32 bits are lost. On 32-bit platforms, the conversion es exact.

3.2.2  Hacía la práctica

3.2.3  Lecturas recomendadas

3.2.4  Ejercicios de programación

1. Escriba el módulo sust.ml en el que defina una función sust:string -> (string*string) -> Buffer.t, que aplique a una cadena todas las sustituciones que puedan hacerse de una cadena patron por un objetivo y que retorne la cadena resultante en un buffer (ver el módulo Buffer de esta guía). Por ejemplo sust "la vida, Vida" ("ida","erdad") debe retornar un buffer con contenido "la verdad, Verdad" . Escriba también la interfaz sust.mli que sólo debe hacer pública la función sust. Ayuda: puede basarse en la función rep_str del módulo lrepasa.ml de repasa.
2. Usando el módulo Sust del punto anterior escriba el programa proto-sed.ml que después de compilado, pueda ejecutarse con dos parámetros:
   1. Una sustitución por realizar con la sintaxis s/patron/sustitucion/g.
   2. El nombre de un archivo tipo texto.
   El programa debe presentar por salida estandar el contenido del archivo texto tras aplicar la sustitución a todas las ocurrencias del patrón por la sustitución. Por ejemplo si existe un archivo carta.txt, desde la línea de comandos debe poderse ejecutar: $ proto-sed s/ida/erdad/g carta.txt
3. En un archivo usoset.ml copie la función ord_words del archivo defprog.ml de repasa así como otras porciones que esta función requiera (por ejemplo el tipo infoword) y las funciones fpol_random, fpol_e, fpol_w y fpol_p. Escriba una función pide_datos que pida al usuario varias 4-tuplas de datos (tantas como el usuario desee), cada una consta de 3 cadenas y un número flotante, la misma función debe agregar la información dada por el usuario a una tabla de Hashing que pueda ser usada por ord_word, después debe llamar la función ord_word usando fpol_random como primer parámetro, 1.0 como segundo parámetro, la tabla de hashing como tercer parámetro y una referencia a una lista vacía como cuarto parámetro, después debe presentar la lista de 4-tuplas que recibe de la función. Experimente cambiando la función que recibe como primer parámetro (por ejemplo por fpol_e) y con base en sus experimentos determine para que se usa la función ord_word en repasa.
   
   
4. Opcional: En que caso se usa la función fpol_pgm con la interfaz plan de repasa? Haga un ejemplo de política que la use.

1

Este ejemplo es tomado del archivo defprog.ml de repasa (ver [7])

Capítulo 4  Solución a los ejercicios

Respuestas a ejercicios de 1.1.4

1. 3+3
2. 7
3. 8
4. 11
5. 14
6. 6.7.4
7. string->string->string
8. fun x->(float_of_int x)+.0.5
9. let dif02=fun f x->dif f x 0.3;;
10. 0.3

Respuestas a ejercicios de programacion de 1.1.5

1. areas.ml

Respuestas a ejercicios de 2.1.4

1. let cuadrado = fun x -> x*x;;
2. let cubo = fun x -> x*(cuadrado x);;
3. factorial
4. No hay diferencia
5. pattern matching
6. suma: int -> int -> (int -> int) -> int
   serie: (int -> int) -> int -> int -> int
7. n>=i
8. Char.chr
9. 'a list -> 'a -> bool
10. .

Respuestas a ejercicios de programacion de 2.1.5

1. let listavacia l= (l=[]);;
   let rec invertir = function 
   | [] -> []
   | h::t -> (invertir t)@[h]
   ;;
   let rec esta_elemento x = function
   | [] -> false
   | h::t -> x=h || (esta_elemento x t)
   ;;
   let rec num_ocurrencias x = function
   | [] -> 0
   | h::t -> (if h=x then 1 else 0)+(num_ocurrencias x t)
   ;;
   let rec espalindrome l= ((invertir l)=l);;
   

Respuestas a ejercicios de 2.2.4

1. true
2. int
3. [1]
4. "wq"::"io"::[]
5. int*int->int*int*(int*int)
6. (0,[])
7. el primero cuyo patrón concuerde
8. ('a -> 'b) -> 'a list -> 'b list
9. let f x=2*x in map f [3;0;1;8];;
10. 4

Respuestas a ejercicios de programacion de 2.2.5

1. -.
2. let rec filter p = function | [] -> [] | h::t -> (if p h then [h] else [])@(filter p t) ;;

Respuestas a ejercicios de 2.3.6

1. 23
2. .
3. .
4. .
5. .
6. .

7.  # List.length (List.filter (fun x -> x='a') ['1';'2';'a';'b';'c';'a';'c']);;
   - : int = 2
   

8. List.map: ('a -> 'b) -> 'a list -> 'b list\\
   List.map2: ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
   

9. .
10. .

Respuestas a ejercicios de programacion de 2.3.7

1. .
2. .
3. .

Respuestas a ejercicios de 2.4.4

1. type trivaluada = Si | No | NoSabe;;

2. type intinf=Ent of int | InfP | InfN;;
   let sumaii e1 e2= match (e1,e2) with
   | Ent i1, Ent i2 -> Ent (i1+i2)
   | Ent _, InfP -> InfP
   | InfP, Ent _ -> InfP
   | InfN, Ent _ -> InfN
   | Ent _, InfN -> InfN
   | _,_ -> raise (Invalid_argument "No puede sumar InfP con InfN");;
   

3. racinf -> racinf o intinf * intinf -> intinf * intinf

4. let mayor p1 p2 = p1.edad > p2.edad;;
   

5. type exprar = Const of int | InvAd of exprar | Suma of exprar * exprar | 
    Resta of exprar * exprar | Prod of exprar * exprar |
    Div of exprar * exprar;;
   

6. let rec evalua = function
    | Const i -> i
    | InvAd e -> -(evalua e)
    | Suma (e1,e2) -> (evalua e1)+(evalua e2)
    | Resta (e1,e2) -> (evalua e1)-(evalua e2)
    | Prod (e1,e2) -> (evalua e1)*(evalua e2)
    | Div (e1,e2) -> (evalua e1)/(evalua e2)
   ;;
   evalua (Prod (Suma (Const 3,Const 5),InvAd (Const 4)));;
   

7. type 'a narb=Vacio | Nodo of 'a*(('a narb) list);;
   

8. let rec npeso2 = 
    let rec npeso_nnod=function
    | Hoja _ -> 1
    | Sub (_,l) -> (List.fold_left (fun a s -> a+(npeso_nnod s)) 1 l)
    in
    function
    | Vacio2 -> 0
    | Nodo2 n -> npeso_nnod n
   ;;
   

9. exception VacioComoSubarbol;;
   let rec narbBueno=function
   | Vacio -> ()
   | Nodo (_,l) -> 
    if (List.exists (fun n -> n=Vacio) l) then
     raise VacioComoSubarbol
    else
     List.iter narbBueno l
   ;;
   

10. let npeso3 a=try
     narbBueno a;
     npeso a
    with
     VacioComoSubarbol -> -1
    ;;
    

Respuestas a ejercicios de programacion de 2.4.5

1. let sublistas l=
           let rec sublistas_aux = function
           | [] -> ([],[])
           | h::t -> let (ht,rt)=sublistas_aux t in
             ([h]::(List.map (fun l -> h::l) ht)),ht@rt
           in
           let (l1,l2)=sublistas_aux l in
           l1@l2
   ;;
   

2. (** Types of heuristics to test answers *)
   type heuresp=HCaseSensitive | HCaseInsensitive | HIgnoreSpaces;;
   
   (** [test_equal_answer heur w ans]  tests if the answer [ans] is equal to
           the word [w] by using the heuristics [heur].  *)
   let rec test_equal_answer heur w ans = match heur with
           | HCaseInsensitive ->
                   (String.lowercase w)=(String.lowercase ans)
           | HCaseSensitive ->
                   w=ans
           | HIgnoreSpaces ->
                   trim w = trim ans
   ;;
   

   Esta nueva definición debe moverse para que quede después de la definición de la función trim (aún mejor ponerla antes de la función parse_heur). parse_heur podría ser:

Respuestas a ejercicios de 3.1.2

1. Array.length
2. Array.length
3. let v = Array.create 5 (-1).
4. let c x = Array.create x ' ';;
5. el vector que se desea copiar
6. abierto
7. let x = ref 5;;
8. # (!x)+(!z);; - : int = 0
9. Sys_error.open.out.
10. open_in "leer.txt";;.

Respuestas a ejercicios de programacion de 3.1.3

1. .
2. .
3. .
4. .

Respuestas a ejercicios de programacion de 3.2.4

1. let sust s (x,y)=
    let res=Buffer.create (String.length s) in
           let rec aux nl nx =
                   if (nx>0 && nx=(String.length x)) then
     begin
      Buffer.add_string res y;
                           aux (nl+nx) 0 ;
     end
                   else if (nl>=(String.length s)) then
                           ()
                   else if (nl+nx>=(String.length s)) then
                           Buffer.add_string res (str_from s nl)
                   else
                   begin
                           let cs=String.get s (nl+nx) in
                           let cx=String.get x nx in
                           if (cs=cx) then
                                   aux nl (nx+1)
                           else
      begin
       Buffer.add_string res (String.sub s nl 1);
                                   aux (nl+1) 0 ;
      end;
                   end
           in aux 0 0 ;
    res
   ;;
   

   
   
   

Bibliografía

[1]

Emmanuel Chailloux, Pascal Manoury, and Bruno Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book/html/index.html, 2002.

[2]

John Harrison. Introduction to functional programming. http://www.cl.cam.ac.uk/Teaching/Lectures/funprog-jrh-1996/index.html, 1996.

[3]

Xavier Leroy. The objective caml system release 3.07. http://caml.inria.fr/ocaml/htmlman/, 2003.

[4]

Vladimir Támara Patiño. Manta 3: Formal description. http://manta.sourceforge.net/doc/formal3/, 1999.

[5]

Basile Starynkevitch. Ocamljitrun. http://cristal.inria.fr/ starynke/ocamljit.html, 2004.

[6]

Gerd Stolpmann. Markup - a library to parse and validate xml in ocaml. http://ocaml-programming.de/markup/, 2004.

[7]

Vladimir Támara. repasa - herramientas y formatos para crear y repasar contenidos. http://structio.sourceforge.net/repasa, 2004.

Index

This document was translated from L^AT_EX by H^EV^EA.