Ejercicios Haskell

21

S OLUCIONES A E JERCICIOS

´
I NTRODUCCI ON

21.1.

A

H ASKELL

Soluci´on al Ejercicio 2.14 (p´ag. 33).– Nuestra funci´on deber´a verificar
∀ n sep n ≥ 0

aEntero [an , an−1 , . . . , a0 ] =

n
i=0 ai

10i

Para n = 0 tenemos trivialmente
aEntero [d ] = d
pero tambi´en deber´a tenerse, para n > 0
≡≡

aEntero [an+1 , an , an−1 , . . . , a0 ]
n+1

ai 10i
≡≡

i=0
n−1

an+1

10n+1

+ an

10n

ai10i

+
i=0

≡≡

n−1

ai 10i

(an+1 10 + an )10n +
≡≡

i=0

aEntero [an+1 10 + an , an−1 , . . . , a0 ]
de donde tenemos la funci´on
aEntero [d ]
=d
aEntero (d : m : r ) = aEntero ( (10 ∗ d + m) : r )
cuya correcci´on es inmediata. Obs´ervese que la funci´on utiliza directamente la cabeza
de la lista como acumulador (ver Cap´ıtulo 16). Podr´ıamos haber obtenido otra versi´on
utilizando unacumulador directamente

650

Soluciones a Ejercicios

aEntero xs

= aEntero xs 0

aEntero [ ]
p =p
aEntero (x : xs) p = aEntero xs (10 ∗ p + x )
que verifica trivialmente la misma ecuaci´on, ya que se tiene (por inducci´on)
∀n

n ≥ 0

aEntero [an , an−1 , . . . , a0 ] p = p 10n +

n
i=0

ai 10i

Veamos ahora la rec´ıproca
aLista 0
= [0]
aLista m
= aLista m [ ]
aLista m xs = if m≤ 0 then
xs
else
aLista(m ‘div ‘ 10) (m ‘mod ‘ 10 : xs)
para la cual se demuestra
∀n

n ≥ 0 , an > 0 , ( ∀ k
n

0 ≤ k ≤ n

0 ≤ ak ≤ 9)

ai 10i )xs = [an , an−1 , . . . , a0 ] ++ xs

aLista (
i=0

por inducci´on sobre n (donde (++) es la concatenaci´on de listas). Para n = 0 es trivial;
el paso inductivo ser´ıa:
n+1

ai 10i ) xs

aLista (
i=0

≡≡ { 2)aLista }
n

ai+1 10i ) (a0 : xs)

aLista (
i=0

≡≡ { hip´otesis deinducci´on, y ya que (∀k 0 ≤ k ≤ n 0 ≤ ak ≤ 9) }
[an+1 , an , . . . , a1 ] ++ (a0 : xs)
≡≡ { propiedad de (++) y (:) }
[an+1 , an , . . . , a1 , a0 ] ++ xs
Soluci´on al Ejercicio 2.28 (p´ag. 46).–
(| >)
:: [Integer → Integer ] → Integer → [Integer ]
[]
|> = [ ]
(f : fs) | > x = f x : (fs | > x )

c ITES-Paraninfo

´ a H ASKELL
21.1 - Introduccion

651

Soluci´on al Ejercicio 2.29 (p´ag. 46).–
esM´ultiploDe
:: Integer → Integer → Bool
a ‘esM´
ultiploDe‘ b = (a ‘mod ‘ b == 0)
esBisiesto :: Integer → Bool
esBisiesto x = x ‘esM´
ultiploDe‘ 4 &&
(not(x ‘esM´
ultiploDe‘ 100) || x ‘esM´
ultiploDe‘ 400)
Soluci´on al Ejercicio 2.31 (p´ag. 46).–
aLaDerechaDe
:: Integer → Integer → Integer
x ‘aLaDerechaDe‘ y = x ∗ 10 + y
Soluci´on al Ejercicio 2.32 (p´ag. 47).–
resto
:: Integer → Integer → Integer
restox y | x < y
= x
| otherwise = resto (x − y) y
Soluci´on al Ejercicio 2.33 (p´ag. 47).–
cociente
:: Integer → Integer → Integer
cociente x y | x < y
= 0
| otherwise = 1 + cociente (x − y) y
Soluci´on al Ejercicio 2.34 (p´ag. 47).–
sumDesdeHasta
:: Integer → Integer → Integer
sumDesdeHasta a b = sumAux (min a b) (max a b)
where sumAux x y | x == y
= x
| otherwise = x + sumAux (x + 1) y
Soluci´on alEjercicio 2.38 (p´ag. 47).– La siguiente es una definici´on directa aunque
poco eficiente (realiza dos llamadas recursivas):
fibonacci
fibonacci 0
fibonacci 1
fibonacci (n + 2)

:: Integer → Integer
=0
=1
= fibonacci n + fibonacci (n + 1)

Soluci´on al Ejercicio 2.41 (p´ag. 48).–
c ITES-Paraninfo

652

Soluciones a Ejercicios
esCapic´
ua
:: Integer → Bool
esCapic´
ua x
| x ≥ 1000 && x ≤ 9999 = d1 == d 4&& d 2 == d 3
| otherwise
= error ”numero
de cifras incorrecto”
´
where
d 1 = x ‘mod ‘ 10
d 2 = (x ‘div ‘ 10) ‘mod ‘ 10
d 3 = (x ‘div ‘ 100) ‘mod ‘ 10
d 4 = (x ‘div ‘ 1000)

Soluci´on al Ejercicio 2.44 (p´ag. 48).– Combinando adecuadamente las soluciones al
Ejercicio 2.32 y al Ejercicio 2.33 se obtiene:
– – trocear x = (cociente x 10, resto x 10)

trocear :: Integer → (Integer , Integer)
trocear x | x < 10 = (0, x )
| otherwise = (1 + c, r ) where (c, r ) = trocear (x − 10)
Obs´ervese que
M AIN> trocear 5
(0, 5) :: (Integer , Integer )
Soluci´on al Ejercicio 2.45 (p´ag. 48).– Para definir concatenar se puede usar la funci´on
trocear del Ejercicio 2.44:
concatenar
:: Integer → Integer → Integer
concatenar x 0 = x
concatenar x y = r ‘aLaDerechaDe‘ (concatenar x c) where (c, r ) =...