Funciones Esenciales en Programación Funcional con Standard ML

Funciones Recursivas

(* Función factorial: calcula el factorial de un número *)

fun factorial n = if n > 0 then n * factorial (n - 1) else 1;

(* Función count: cuenta la cantidad de elementos de una lista *)

fun count (h::t) = count(t) + 1
  | count([]) = 0;

(* Función sum: suma los elementos de una lista *)

fun sum(h::t) = sum(t) + h
  | sum([]) = 0;

(* Función head: obtiene el primer elemento de una lista *)

fun head (nil) = raise Exepc
  | head (x::l) = x;

(* Función tail: obtiene la cola de una lista *)

fun tail (nil) = raise Exepc
  | tail (h::t) = t;

(* Función elt: obtiene el i-ésimo elemento de una lista *)

fun elt (h::t, i) = if i = 1 then h else elt(t, i - 1);

(* Función elt2: otra forma de obtener el i-ésimo elemento de una lista *)

fun elt2 ([], i:int) = raise Exepc
  | elt2 (h::t, 1)  =  h
  | elt2 (l, i:int) = elt2(tail(l), i - 1);

(* Función elt3: otra forma más de obtener el i-ésimo elemento de una lista *)

(* NOTAR QUE: Esta no es una función total por lo que ML nos dará un Warning*)

fun elt3 (h::t, 1)      =  h
  | elt3 (h::t, i:int) = elt3(t, i - 1);

(* Función cat: une dos listas *)

fun cat ([], l)  = l
  | cat (h::t, l) = h::cat(t, l);

(* Función cat2: otra forma de unir dos listas *)

fun cat2 ([], l)  = l
  | cat2 (l, [])  = l
  | cat2 (h::t, l) = h::cat(t, l);

(* Función repetir: repite un carácter n veces en un string *)

(* El símbolo ^ une un char con un string *)

fun repetir 0 s = ""
  | repetir n s = s ^ (repetir (n - 1) s);

Funciones de Orden Superior

(* Lista de funciones de dos argumentos definidas para los ejemplos de la función reduce *)

fun mult (x:int, y:int) = x * y;
fun plus (x:int, y:int) = x + y;
fun minus (x:int, y:int) = x - y;
fun division (x, y) = x / y;

(* Función reduce: reduce una lista con la aplicación de la función f *)

fun reduce(f, [], i)  = i
  | reduce(f, h::t, i) = f(h, reduce(f, t, i));

fun member (x, nil) = false
  | member (x, h::t) = if x = h then true else member(x, t);

fun todos (nil, l) =  true
  | todos (h::t, l) = member(h, l) andalso todos(t, l);

Ejercicios

1. Escriba funciones que tengan los siguientes tipos:
2. val num = fn : int list -> int
3. val or = fn : bool list -> bool
4. val l = fn : 'a -> 'a list list
5. val id = fn : 'a list -> 'a list list

6. fun num [] = 1
     | num (x::y) = x * num(y);

7. fun or [] = false
     | or (x::h) = x orelse (or h);

8. fun l x = [[x]];

9. fun id [] = [[]]
     | id (x::y) = [x::y];

Ejercicios dados en clase

Clase del día 9/5

(* Función pertenece: determina si un elemento está en la lista *)

fun pertenece ( x, [] ) = false
  | pertenece ( x, y::t ) = if ( x = y ) then true else pertenece ( x, t );

(* Función contenido: determina si todo elemento de la primera lista está en la segunda *)

fun contenido ( [], y ) = true
  | contenido ( x::z, y ) = if false = pertenece ( x, y ) then false else contenido ( z, y );

(* Función union: devuelve una lista que tiene los elementos de las dos listas sin repetir *)

fun union ( [], y ) = y
  | union ( x::z, y ) = if true = pertenece ( x, y ) then union( z, y ) else x::union( z, y );

(* Función interseccion: devuelve una lista que tiene los elementos que se encuentran en las dos listas *)

fun interseccion ( [], y ) = []
  | interseccion ( x::z, y ) = if false = pertenece ( x, y ) then interseccion( z, y ) else x::interseccion( z, y );

(* Función diferencia: devuelve una lista que tiene los elementos que se encuentran en la primera y no en la segunda lista *)

fun diferencia ( [], y ) = []
  | diferencia ( x, [] ) = x
  | diferencia ( x::z, y ) = if true = pertenece ( x, y ) then diferencia( z, y ) else x::diferencia( z, y );

Clase del día 23/5

(* Función pair: devuelve una lista de pares donde el elemento es la segunda componente *)

fun pair (a::b, x) = (a, x)::pair(b, x)
  | pair ( nil, x ) = nil;

(* Función combinar: devuelve todos los pares posibles donde la primera componente es un elemento de la primera lista y la segunda componente es un elemento de la segunda lista *)

fun combinar (a::b, c::d) = pair(a::b, c) @ combinar(a::b, d)
  | combinar (z, nil) = nil;

(* Función maxlong: devuelve la longitud máxima de una lista contenida en el parámetro que es una lista de listas *)

fun maxlong (nil) = 0
  | maxlong (a::b) = let
    val a = length(a)
    val b = maxlong (b)
  in
    if a > b then a else b
  end;

(* Función parcial: determina si un elemento es suma parcial de los elementos de la lista *)

fun parcial( nil, 0 ) = true
  | parcial( nil, x ) = false
  | parcial( a::b, x ) = parcial( b, x) orelse parcial( b, x - a );