domingo, 9 de marzo de 2014

Ejercicios de Haskell (II)

Os dejo unos ejercicios más completos de Haskell.

Un método para calcular el máximo común divisor (mcd) de dos números naturales (no nulos simultáneamente) consiste en obtener las descomposiciones en factores primos de ambos y multiplicar los factores comunes de la forma con menor exponente. Por ejemplo: factPrimos 48 -> [2,2,2,2,3] por lo que el mcd de 48 y 60 es 2*2*3.
a) Escribe una función recursiva mezc' que tome las listas de factores primos ordenadas ascendentemente y devuelva una lista ordenada con los factores comunes repetidos según la menor potencia. Por ejemplo:
mezc' [2,2,2,2,3] [2,2,3,5] -> [2,2,3]
b) Usando la función mezc', define una función mcd' que calcule el mcd de dos naturales no nulos simultáneamente.
c) Recuerda que gcd es la función predefinida para calcular el mcd. Comprueba tu función con QuickCheck mediante la siguiente propiedad:
p_mcd' x y = x>0 && y>0 ==> mcd' x y == gcd x y
Modifica la precondición para comprobar la corrección con naturales no nulos simultáneamente.
mezc' :: [Integer] -> [Integer] -> [Integer]
mezc' [] _ = []
mezc' _ [] =  []
mezc' (x:xs)(y:ys)
  | x < y       = mezc' xs (y:ys)
  | x > y       = mezc'(x:xs) ys
  | x == y      = [x] ++ mezc' xs ys

mcd' :: Integer -> Integer-> Integer
mcd' 0 0 = 0
mcd' x y = product(mezc' (factPrimos x) (factPrimos y))

p_mcd' x y = x>0 && y>0 ==> mcd' x y == gcd x y

En Haskell una cadena de caracteres (String) es una lista de tipo [Char]. En este ejercicio vamos a estudiar cómo el procesamiento de cadenas de caracteres resulta muy útil en Biología.
Un problema común en la Biología moderna es entender la estructura de las moléculas de ADN y el papel de las estructuras específicas para determinar la función de una molécula. Una secuencia de ADN es comúnmente representada como una secuencia de los cuatro nucleótidos - adenina (A), citosina (C), guanina (G) y timina (T) - por lo que una molécula puede ser representada con una cadena de caracteres con los correspondientes nucleótidos, como "AAACAACTTCGTAAGTATA".
Una forma de entender la función de una cadena de ADN es ver si contiene subcadenas que coincidan con una colección de secuencias de ADN ya conocidas - es decir, secuencias cuya función y estructura ya se conoce - con la idea de que estructuras similares tienden a implicar funciones similares. Organismos simples como las bacterias pueden tener millones de nucleótidos en sus secuencias del ADN y los cromosomas humanos se cree que constan del orden de 246 millones de bases, por lo que es necesario desarrollar programas de ordenador muy eficientes para procesar estas cadenas.
a) Define una función recursiva esPrefijoDe que tome dos listas como argumentos, y compruebe si la primera es un prefijo de la segunda, es decir, si la segunda comienza exactamente por la primera. Por ejemplo:
"ATG" `esPrefijoDe` "ATGACATGCACAAGTATGCAT" -> True
"ATC" `esPrefijoDe` "ATGACATGCACAAGTATGCAT" -> False
Nota: la función isPrefixOf de la biblioteca List realiza esto mismo.
b) Define una función recursiva búsquedas :: String -> String -> [Int] que tome como parámetros dos listas. La primera será la cadena a buscar y la segunda la cadena donde buscar. La función debe devolver una lista de enteros con todas las posiciones donde aparezca la cadena buscada. Por convenio, consideraremos que las posiciones de las letras en una cadena empiezan a numerarse por cero. Por ejemplo:
búsquedas "ATG" "ATGACATGCACAAGTATGCAT" -> [0,5,15]
ya que la cadena "ATG" aparece justo al principio (posición 0), aparece a continuación 5 posiciones después y por último aparece en la posición 15 (las apariciones de la cadena buscada se indican en subrayado).
Ayuda: usa la función esPrefijoDe para definir la función búsquedas.
c) Define una función distancia que dadas dos cadenas compare los caracteres en las mismas posiciones de las dos cadenas y devuelva cuantos son diferentes. Por ejemplo:
distancia "ATGAG" "ACGAA" -> 2
ya que la caracteres en las posiciones 1 (T y C) y 4 (G y A) difieren en ambas cadenas. Si una cadena es más corta que otra, considera que todos los caracteres extra de la más larga son diferencias. Por ejemplo:
distancia "ATG" "ACGAA" -> 3
ya que ambas cadenas difieren en los caracteres en las posiciones 1, 3 y 4.
esPrefijoDe :: String -> String -> Bool
esPrefijoDe [] _ = True
esPrefijoDe _ [] = False
esPrefijoDe (x:xs) (y:ys)
  | length (x:xs) > length (y:ys) = False
  | x == y      = esPrefijoDe xs ys
  | otherwise   = False

búsquedas :: String -> String -> [Int]
búsquedas xs ys = busquedas xs ys 0 

busquedas :: String -> String -> Int -> [Int]
busquedas xs [] n = []
busquedas xs (y:ys) n
  |esPrefijoDe xs (y:ys) = [n] ++ busquedas xs ys (n+1)
  | otherwise = busquedas xs ys (n+1)

distancia :: String -> String -> Int
distancia [] (y:ys) = length (y:ys)
distancia (x:xs) [] = length (x:xs)
distancia [] [] = 0
distancia (x:xs) (y:ys) 
  | x /= y      = 1 + distancia xs ys
  | otherwise = distancia xs ys

Sea f una función de reales en reales continua en el intervalo cerrado [a,b], que además toma valores con signos opuestos en los extremos de dicho intervalo (es decir, los signos de f(a) y f(b) son distintos). Bajo dichas suposiciones es seguro que f tiene una raíz en dicho intervalo. Este resultado se conoce como el teorema de Bolzano.
El método de bipartición usa la técnica divide y vencerás para encontrar una aproximación a dicha raíz. Los parámetros del método son f, a, b y epsilon. Para ello:

  • Sea c el punto medio del intervalo determinado por a y b.
  • Si la amplitud del intervalo [a,b] es menor o igual que epsilon, se devuelve el punto c como aproximación de la raíz.
  • Si f(c)≅ 0, entonces se devuelve el punto c como aproximación de la raíz.
  • Si hay un cambio de signo en los extremos del intervalo [a,c], se repite todo el proceso con dicho intervalo.
  • En otro caso, el cambio de signo estará en el intervalo [c,b], por lo que se repite el proceso con este intervalo.

Define una función bipartición que tome como parámetros f, a, b y epsilon y devuelva una aproximación a una raíz de f en el intervalo [a,b] calculada con el método de bipartición.
bipartición :: (Double -> Double)-> Double -> Double -> Double -> Double
bipartición f a b ep 
  | b - a <= ep = c
  | f (c) ~= 0 = c -- necesario usar el operador ~=,definido entradas anteriores 
  | (f a) * (f c) < 0 = bipartición f a c ep
  | otherwise = bipartición f c b ep
    where 
      c = (a+b)/2

5 comentarios:

  1. En la función esPrefijoDe te falta el caso de que el 2º argumento sea la lista vacía y en la 2ª guarda (x==y) no pongas True&&esPrefijoDe xs ys porque True es el elemento neutro de (&&), solo tienes que poner esPrefijo de xs ys.

    ResponderEliminar
  2. Las líneas 5 y 7 de la función esPrefijoDe sobran, no hacen falta guardas, habría que poner que esPrefijoDe (x:xs) (y:ys) = x==y && esPrefijoDe xs ys
    Atentamente M.I.A.

    ResponderEliminar
    Respuestas
    1. Y también funciona, pero con la línea 5 lo que hacemos es ahorrarnos el buscar el prefijo. Supongamos una llamada:
      esPrefijoDe HolaQueTalSoyAdri HolaQueTalSoyA
      Con ésa línea nos ahorramos el computar toda la cadena y, en informática, éso es lo que importa, no? ;)

      Saludos;)

      Eliminar
  3. hola, quería saber si me podías ayudar con este ejercicio que no entiendo por favor..
    Defina una función letras, y todas las funciones auxiliares que necesite, tal que dada una lista de cadenas, devuelva la lista de letras presentes en todas las cadenas.Ejemplo:
    Main > letras ["paradigmas","programacion","parcial"]
    ['p','a','r','i']

    ResponderEliminar