I1M2017: Ejercicios de definiciones por recursión (1)

En la segunda parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se han comentado las soluciones de los tres primeros ejercicios de la 4ª relación sobre definiciones por recursión.

Los ejercicios y su solución se muestran a continuación

-- I1M 2017-18: Rel_4_sol.hs (11 de octubre de 2017)
-- Definiciones por recursión 
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- En esta relación se presentan ejercicios con definiciones por
-- recursión correspondientes al tema 6 cuyas transparencias se 
-- encuentran en  
--    http://www.cs.us.es/~jalonso/cursos/i1m-17/temas/tema-6.html
 
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir por recursión la función
--    potencia :: Integer -> Integer -> Integer
-- tal que (potencia x n) es x elevado al número natural n. Por ejemplo,  
--    potencia 2 3  ==  8
-- ---------------------------------------------------------------------

potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia m n = m * potencia m (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Comprobar con QuickCheck que la función potencia es
-- equivalente a la predefinida (^).
-- ---------------------------------------------------------------------

-- La propiedad es
prop_potencia :: Integer -> Integer -> Property
prop_potencia x n = 
  n >= 0 ==> potencia x n == x^n

-- La comprobación es
--    ghci> quickCheck prop_potencia
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Dados dos números naturales, a y b, es posible
-- calcular su máximo común divisor mediante el Algoritmo de
-- Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
--    mcd(a,b) = a,                   si b = 0
--             = mcd (b, a módulo b), si b > 0
-- 
-- Definir la función 
--    mcd :: Integer -> Integer -> Integer
-- tal que (mcd a b) es el máximo común divisor de a y b calculado
-- mediante el algoritmo de Euclides. Por ejemplo,
--    mcd 30 45  ==  15
-- ---------------------------------------------------------------------

mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (a `mod` b)

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir y comprobar la propiedad prop_mcd según la
-- cual el máximo común divisor de dos números a y b (ambos mayores que
-- 0) es siempre mayor o igual que 1 y además es menor o igual que el
-- menor de los números a  y b. 
-- ---------------------------------------------------------------------

-- La propiedad es
prop_mcd :: Integer -> Integer -> Property
prop_mcd a b =
  a > 0 && b > 0 ==> m >= 1 && m <= min a b 
  where m = mcd a b

-- La comprobación es
--    ghci> quickCheck prop_mcd
--    OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Teniendo en cuenta que buscamos el máximo común
-- divisor de a y b, sería razonable pensar que el máximo común divisor
-- siempre sería igual o menor que la mitad del máximo de a y b. Definir
-- esta propiedad y comprobarla.  
-- ---------------------------------------------------------------------

-- La propiedad es
prop_mcd_div :: Integer -> Integer -> Property
prop_mcd_div a b =
  a > 0 && b > 0 ==> mcd a b <= max a b `div` 2

-- Al verificarla, se obtiene
--    ghci> quickCheck prop_mcd_div
--    Falsifiable, after 0 tests:
--    3
--    3
-- que la refuta. Pero si la modificamos añadiendo la hipótesis que los números
-- son distintos,
prop_mcd_div' :: Integer -> Integer -> Property
prop_mcd_div' a b =
  a > 0 && b > 0 && a /= b ==> mcd a b <= max a b `div` 2

-- entonces al comprobarla
--    ghci> quickCheck prop_mcd_div'
--    OK, passed 100 tests.
-- obtenemos que se verifica.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1, Definir por recursión la función
--    pertenece :: Eq a => a -> [a] -> Bool
-- tal que (pertenece x xs) se verifica si x pertenece a la lista xs. Por
-- ejemplo, 
--    pertenece 3 [2,3,5]  ==  True
--    pertenece 4 [2,3,5]  ==  False
-- ---------------------------------------------------------------------

pertenece :: Eq a => a -> [a] -> Bool
pertenece _ []     = False
pertenece x (y:ys) = x == y || pertenece x ys

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente
-- a elem. 
-- ---------------------------------------------------------------------

-- La propiedad es
prop_pertenece :: Eq a => a -> [a] -> Bool
prop_pertenece x xs = pertenece x xs == elem x xs

-- La comprobación es
--    ghci> quickCheck prop_pertenece
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

-- I1M 2017-18: Rel_4_sol.hs (11 de octubre de 2017)

-- Definiciones por recursión

-- Departamento de Ciencias de la Computación e I.A.

-- Universidad de Sevilla

-- =====================================================================

-- ---------------------------------------------------------------------

-- Introducción --

-- ---------------------------------------------------------------------

-- En esta relación se presentan ejercicios con definiciones por

-- recursión correspondientes al tema 6 cuyas transparencias se

-- encuentran en

-- http://www.cs.us.es/~jalonso/cursos/i1m-17/temas/tema-6.html

-- ---------------------------------------------------------------------

-- Importación de librerías auxiliares --

-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Ejercicio 1.1. Definir por recursión la función

-- potencia :: Integer -> Integer -> Integer

-- tal que (potencia x n) es x elevado al número natural n. Por ejemplo,

-- potencia 2 3 == 8

-- ---------------------------------------------------------------------

potencia :: Integer -> Integer -> Integer

potencia _ 0 = 1

potencia m n = m * potencia m (n-1)

-- ---------------------------------------------------------------------

-- Ejercicio 1.2. Comprobar con QuickCheck que la función potencia es

-- equivalente a la predefinida (^).

-- ---------------------------------------------------------------------

-- La propiedad es

prop_potencia :: Integer -> Integer -> Property

prop_potencia x n =

n >= 0 ==> potencia x n == x^n

-- La comprobación es

-- ghci> quickCheck prop_potencia

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 2.1. Dados dos números naturales, a y b, es posible

-- calcular su máximo común divisor mediante el Algoritmo de

-- Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

-- mcd(a,b) = a, si b = 0

-- = mcd (b, a módulo b), si b > 0

-- Definir la función

-- mcd :: Integer -> Integer -> Integer

-- tal que (mcd a b) es el máximo común divisor de a y b calculado

-- mediante el algoritmo de Euclides. Por ejemplo,

-- mcd 30 45 == 15

-- ---------------------------------------------------------------------

mcd :: Integer -> Integer -> Integer

mcd a 0 = a

mcd a b = mcd b (a `mod` b)

-- ---------------------------------------------------------------------

-- Ejercicio 2.2. Definir y comprobar la propiedad prop_mcd según la

-- cual el máximo común divisor de dos números a y b (ambos mayores que

-- 0) es siempre mayor o igual que 1 y además es menor o igual que el

-- menor de los números a y b.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_mcd :: Integer -> Integer -> Property

prop_mcd a b =

a > 0 && b > 0 ==> m >= 1 && m <= min a b

where m = mcd a b

-- La comprobación es

-- ghci> quickCheck prop_mcd

-- OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Ejercicio 2.3. Teniendo en cuenta que buscamos el máximo común

-- divisor de a y b, sería razonable pensar que el máximo común divisor

-- siempre sería igual o menor que la mitad del máximo de a y b. Definir

-- esta propiedad y comprobarla.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_mcd_div :: Integer -> Integer -> Property

prop_mcd_div a b =

a > 0 && b > 0 ==> mcd a b <= max a b `div` 2

-- Al verificarla, se obtiene

-- ghci> quickCheck prop_mcd_div

-- Falsifiable, after 0 tests:

-- 3

-- que la refuta. Pero si la modificamos añadiendo la hipótesis que los números

-- son distintos,

prop_mcd_div' :: Integer -> Integer -> Property

prop_mcd_div' a b =

a > 0 && b > 0 && a /= b ==> mcd a b <= max a b `div` 2

-- entonces al comprobarla

-- ghci> quickCheck prop_mcd_div'

-- OK, passed 100 tests.

-- obtenemos que se verifica.

-- ---------------------------------------------------------------------

-- Ejercicio 3.1, Definir por recursión la función

-- pertenece :: Eq a => a -> [a] -> Bool

-- tal que (pertenece x xs) se verifica si x pertenece a la lista xs. Por

-- ejemplo,

-- pertenece 3 [2,3,5] == True

-- pertenece 4 [2,3,5] == False

-- ---------------------------------------------------------------------

pertenece :: Eq a => a -> [a] -> Bool

pertenece _ [] = False

pertenece x (y:ys) = x == y || pertenece x ys

-- ---------------------------------------------------------------------

-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente

-- a elem.

-- ---------------------------------------------------------------------

-- La propiedad es

prop_pertenece :: Eq a => a -> [a] -> Bool

prop_pertenece x xs = pertenece x xs == elem x xs

-- La comprobación es

-- ghci> quickCheck prop_pertenece

-- +++ OK, passed 100 tests.

Se puede imprimir o compartir con