Iteración, recursión y punto fijo

En esta relación de ejercicios se muestra cómo se pueden transformar programas iterativos (con bucles while o for) en programas en recursivos. Para cada uno de los bucles, se elige una función y se pide definirla usando el bucle (en Python), buscar una definición recursiva que sea semejante a la anterior, definir el patrón que abstrae el bucle, definirla con el patrón y aplicar el patrón a otras funciones. Finalmente, se estudia cómo definir algunas de las anteriores funciones usando el menor punto fijo.

La relación está elaborado como complemento del tema Funciones de orden superior del curso de Informática de primero del Grado en Matemáticas.

El bucle while con un parámetro

Nota [Parte impar]. Todo número entero n se puede escribir como m*2^k, con m impar. Se dice que m es la parte impar de n. Por ejemplo, la parte impar de 40 es 5 porque 40 = 5*2^3.

Ejercicio 1 [Parte impar con while en Python]. Definir en Python, usando un blucle while, la función parteImpar tal que parteImpar(n) es la parte impar de n.

Solución:

def parteImpar(n): 
    while n % 2 == 0:
        n = n/2
    return n

def parteImpar(n):

while n % 2 == 0:

n = n/2

return n

Ejercicio 2 [Parte impar por recursión]. Definir, por recursión, la función: parteImpar :: Int -> Int
tal que (parteImpar n) es la parte impar de n. Por ejemplo,: parteImpar 40 == 5

Solución:

parteImpar :: Int -> Int
parteImpar n | even n    = parteImpar (n `div` 2)
             | otherwise = n

parteImpar :: Int -> Int

parteImpar n | even n = parteImpar (n `div` 2)

| otherwise = n

Ejercicio 3 [El bucle while1]. Definir la función: while1 :: (a -> Bool) -> (a -> a) -> a -> a
tal que (while1 p f x) es el resultado de aplicar la función f a x mientras cumple la propiedad p. Por ejemplo,: while1 (<1000) (*2) 1 == 1024

Solución:

-- 1ª definición (por recursión):
while1 :: (a -> Bool) -> (a -> a) -> a -> a
while1 p f x | p x       = while1 p f (f x)
             | otherwise = x

-- 2ª definición (con until):
while1b :: (a -> Bool) -> (a -> a) -> a -> a
while1b p f x = until (not . p) f x

-- 3ª definición (con until y composición):
while1c :: (a -> Bool) -> (a -> a) -> a -> a
while1c = until . (not.)

-- 1ª definición (por recursión):

while1 :: (a -> Bool) -> (a -> a) -> a -> a

while1 p f x | p x = while1 p f (f x)

| otherwise = x

-- 2ª definición (con until):

while1b :: (a -> Bool) -> (a -> a) -> a -> a

while1b p f x = until (not . p) f x

-- 3ª definición (con until y composición):

while1c :: (a -> Bool) -> (a -> a) -> a -> a

while1c = until . (not.)

Ejercicio 4 [Parte impar con el bucle while1]. Redefinir, usando while1, la función parteImpar.

Solución:

parteImpar2 :: Int -> Int
parteImpar2 = while1 even (`div` 2)

1 2	parteImpar2 :: Int -> Int parteImpar2 = while1 even (`div` 2)

Nota [La órbita de Collatz]. El sucesor de Collatz de un número n es n/2, si n es par y 3n+1 , en caso contrario. La órbita de un número se obtiene escribiendo los sucesivos sucesores de Collatz hasta llegar a 1. Por ejemplo, la órbita de Collatz de 7 es 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Ejercicio 5 [La órbita de Collatz con while en Python]. Definir en Python, usando while, la función collatz tal que collatz(n) es la órbita de Collatz de n. Por ejemplo,: collatz(7) == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

def collatz(n):
    s = [n]
    while (n != 1):
        if n % 2 == 0:
            n = n//2
        else:
            n = 3*n+1
        s.append(n)
    return s

def collatz(n):

s = [n]

while (n != 1):

if n % 2 == 0:

n = n//2

else:

n = 3*n+1

s.append(n)

return s

Ejercicio 6 [La órbita de Collatz por recursión]. Definir, mediante recursión, la función: collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,: collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

-- 1ª definición (con condicionales):
collatz :: Integer -> [Integer]
collatz n = reverse (aux [n])
    where aux (n:ns) = if n == 1 then n:ns
                       else if even n 
                            then aux (div n 2:n:ns)
                            else aux (3*n+1:n:ns)

-- 2ª definición (con guardas):
collatz2 :: Integer -> [Integer]
collatz2 n = reverse (aux [n])
    where aux (1:ns) = 1:ns
          aux (n:ns) | even n    = aux (div n 2:n:ns)
                     | otherwise = aux (3*n+1:n:ns)

-- 1ª definición (con condicionales):

collatz :: Integer -> [Integer]

collatz n = reverse (aux [n])

where aux (n:ns) = if n == 1 then n:ns

else if even n

then aux (div n 2:n:ns)

else aux (3*n+1:n:ns)

-- 2ª definición (con guardas):

collatz2 :: Integer -> [Integer]

collatz2 n = reverse (aux [n])

where aux (1:ns) = 1:ns

aux (n:ns) | even n = aux (div n 2:n:ns)

| otherwise = aux (3*n+1:n:ns)

Ejercicio 7 [La órbita de Collatz con while1]. Definir, usando while1, la
función: collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,: collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

collatz :: Int -> [Int]
collatz n = reverse (aux [n]) where
    aux = while1 (\(n:ns) -> n /= 1)
                 (\(n:ns) -> if even n 
                             then (n `div` 2):n:ns 
                             else (3*n+1):n:ns)

collatz :: Int -> [Int]

collatz n = reverse (aux [n]) where

aux = while1 (\(n:ns) -> n /= 1)

(\(n:ns) -> if even n

then (n `div` 2):n:ns

else (3*n+1):n:ns)

Ejercicio 8 [El menor punto fijo por recursión]. Definir, por recursión, la función: mpf :: Eq a => (a -> a) -> a -> a
tal que (mpf f x) es el menor punto fijo de f respecto de x. Por ejemplo,: mpf (\x -> if x < 10 then x else (div x 10)) 325 == 3; mpf (\x -> if even x then (div x 2) else x) 24 == 3

Solución:

mpf :: Eq a => (a -> a) -> a -> a
mpf f x | f x == x  = x
        | otherwise = mpf f (f x)

mpf :: Eq a => (a -> a) -> a -> a

mpf f x | f x == x = x

| otherwise = mpf f (f x)

Ejercicio 9 [El menor punto fijo con while1]. Definir, con while1, la función: mpf :: Eq a => (a -> a) -> a -> a
tal que (mpf f x) es el menor punto fijo de f respecto de x. Por ejemplo,: mpf (\x -> if x < 10 then x else (div x 10)) 325 == 3; mpf (\x -> if even x then (div x 2) else x) 24 == 3

Solución:

mpf :: Eq a => (a -> a) -> a -> a
mpf f = while1 (\x -> f x /= x) (\x -> f x)

1 2	mpf :: Eq a => (a -> a) -> a -> a mpf f = while1 (\x -> f x /= x) (\x -> f x)

El bucle while con dos parámetros

Ejercicio 10 [Suma impares con bucle while en Python]. Definir en Python, usando un bucle while, la función sumaImpares tal que sumaImpares(n) es la suma de los n primeros números impares. Por ejemplo,: sumaImpares(3) == 9; sumaImpares(4) == 16

Solución:

def sumaImpares(n): 
    s = 0
    k = 0
    while k < n:
        s = s + 2*k + 1
        k = k + 1
    return s

def sumaImpares(n):

s = 0

k = 0

while k < n:

s = s + 2*k + 1

k = k + 1

return s

Ejercicio 11 [Suma impares por recursión]. Definir en Haskell la función: sumaImpares :: Int -> Int

que traduzca la definición anterior.

Solución:

-- 1ª definición
sumaImpares :: Int -> Int
sumaImpares n = aux n 0 0 where
    aux n k s = if k < n then 
                    let s1 = s + 2*k + 1
                        k1 = k + 1
                    in aux n k1 s1 
                else s

-- 2ª definición (usando where en lugar de let)
sumaImpares2 :: Int -> Int
sumaImpares2 n = aux n 0 0 where
    aux n k s = if k < n 
                then aux n k1 s1  
                else s
                where s1 = s + 2*k + 1
                      k1 = k + 1

-- 3ª definición (sin let ni where)
sumaImpares3 :: Int -> Int
sumaImpares3 n = aux n 0 0 where
    aux n k s = if k < n 
                then aux n (k + 1) (s + 2*k + 1)
                else s

-- 4ª definición (con guardas)
sumaImpares4 :: Int -> Int
sumaImpares4 n = aux n 0 0 where
    aux n k s | k < n     = aux n (k + 1) (s + 2*k + 1)
              | otherwise = s

-- 1ª definición

sumaImpares :: Int -> Int

sumaImpares n = aux n 0 0 where

aux n k s = if k < n then

let s1 = s + 2*k + 1

k1 = k + 1

in aux n k1 s1

else s

-- 2ª definición (usando where en lugar de let)

sumaImpares2 :: Int -> Int

sumaImpares2 n = aux n 0 0 where

aux n k s = if k < n

then aux n k1 s1

else s

where s1 = s + 2*k + 1

k1 = k + 1

-- 3ª definición (sin let ni where)

sumaImpares3 :: Int -> Int

sumaImpares3 n = aux n 0 0 where

aux n k s = if k < n

then aux n (k + 1) (s + 2*k + 1)

else s

-- 4ª definición (con guardas)

sumaImpares4 :: Int -> Int

sumaImpares4 n = aux n 0 0 where

aux n k s | k < n = aux n (k + 1) (s + 2*k + 1)

| otherwise = s

Ejercicio 12 [El bucle while2] Definir la función: while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b
tal que (while2 p f x y) aplica f a x e y mientras que se cumple la propiedad p y devuelve y cuando no se cumple. Por ejemplo,: (while2 (\x y -> x<3) (\x y -> (x+1,x+y))) 0 0 == 3; (while2 (\x y -> x<4) (\x y -> (x+1,x+y))) 0 0 == 6

El procedimiento de evaluación de (while2 p f x y) es el siguiente

si se verifica (p x y), evalúa (f x y) que dará un par (x1,y1)
si se verifica (p x1 y1), evalúa (f x1 y1) que dará un par (x2,y2)
y así hasta que llegue a un par (xn,yn) tal que no se verifique (p xn yn), en cuyo caso devuelve yn.

Solución:

while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b
while2 p f x y 
    | p x y     = while2 p f x1 y1
    | otherwise = y 
    where (x1,y1) = f x y

while2 :: (a -> b -> Bool) -> (a -> b -> (a,b)) -> a -> b -> b

while2 p f x y

| p x y = while2 p f x1 y1

| otherwise = y

where (x1,y1) = f x y

Ejercicio 13 [Suma impares con while2]. Redefinir, usando while2, la función sumaImpares.

Solución:

sumaImpares :: Int -> Int
sumaImpares n = aux n 0 0 where
    aux n = while2
             (\k s -> k < n)
             (\k s -> (k+1,s+2*k+1))

sumaImpares :: Int -> Int

sumaImpares n = aux n 0 0 where

aux n = while2

(\k s -> k < n)

(\k s -> (k+1,s+2*k+1))

Ejercicio 14 [El algoritmo de Euclides con while en Python]. Definir en Python la función mcd tal que mcd(x,y) es el máximo común divisor de x e y, calculado mediante el algoritmo de Euclides.

Solución:

def mcd(x,y):
    while x != y:
        if x > y: 
            x = x - y 
        else: 
            y = y - x
    return y

def mcd(x,y):

while x != y:

if x > y:

x = x - y

else:

y = y - x

return y

Ejercicio 15 [El algoritmo de Euclides por recursión]. Definir la función: mcd :: Int -> Int -> Int

tal que mcd(x,y) es el máximo común divisor de x e y, calculado mediante el algoritmo de Euclides.

Solución:

mcd :: Int -> Int -> Int
mcd x y | x /= y    = if x > y 
                      then mcd (x-y) y
                      else mcd x (y-x)
        | otherwise = y

mcd :: Int -> Int -> Int

mcd x y | x /= y = if x > y

then mcd (x-y) y

else mcd x (y-x)

| otherwise = y

Ejercicio 16 [El algoritmo de Euclides con while2]. Redefinir, usando while2, la función mcd.

Solución:

mcd2 :: Int -> Int -> Int
mcd2 = while2 
       (\ x y -> x /= y) 
       (\ x y -> if x > y 
                 then (x-y,y) 
                 else (x,y-x))

mcd2 :: Int -> Int -> Int

mcd2 = while2

(\ x y -> x /= y)

(\ x y -> if x > y

then (x-y,y)

else (x,y-x))

Ejercicio 17 [El factorial con while en Python]. Definir en Python, usando while, la función fact tal que fact(n) es el factorial de n. Por ejemplo,: fact(4) == 24

Solución:

def factorial(n):
    f = 1
    while n != 0:
        f = f*n
        n = n-1
    return f

def factorial(n):

f = 1

while n != 0:

f = f*n

n = n-1

return f

Ejercicio 18 [El factorial por recursión]. Definir, por recursión, la función: fact :: Integer -> Integer
tal que (fact n) es el factorial de n. Por ejemplo,: fact 4 == 24


Solución:


		
		
			
			
Haskell
			
			-- 1ª definición (con acumulador):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux 0 f = f
          aux n f = aux (n-1) (n*f)

-- 2ª definición (sin acumulador):
factorial2 :: Integer -> Integer
factorial2 0 = 1
factorial2 n = n * factorial2 (n-1)
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
				
						-- 1ª definición (con acumulador):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux 0 f = f
          aux n f = aux (n-1) (n*f)
 
-- 2ª definición (sin acumulador):
factorial2 :: Integer -> Integer
factorial2 0 = 1
factorial2 n = n * factorial2 (n-1)
					
				
			
		


Ejercicio 19 [El factorial con while2]. Redefinir, con while2, la función fact.
Solución:


		
		
			
			
Haskell
			
			-- 1ª definición (con auxiliar):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux = while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))

-- 2ª definición (sin auxiliar):
factorial2 :: Integer -> Integer
factorial2 n = (while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))) n 1
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
				
						-- 1ª definición (con auxiliar):
factorial :: Integer -> Integer
factorial n = aux n 1
    where aux = while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))
 
-- 2ª definición (sin auxiliar):
factorial2 :: Integer -> Integer
factorial2 n = (while2 (\n f -> n /= 0)
                       (\n f -> (n-1,f*n))) n 1
					
				
			
		


El bucle while con tres parámetros

Ejercicio 20 [Fibonacci con while en Python]. Definir la función fib tal que fib(n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

[fib(n) for n in range(10)]  ==  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]


Solución:


		
		
			
			
Python
			
			# 1ª definición
def fib(n):
    x = 0
    y = 1
    while (n != 0):
        x, y = (y,x+y)
        n = n-1
    return x

# 2ª definición
def fib2(n):
    if n == 0:
        return 0
    else: 
        x = 0
        y = 1
        while (n > 1):
            x, y = (y,x+y)
            n = n-1
        return y
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
				
						# 1ª definición
def fib(n):
    x = 0
    y = 1
    while (n != 0):
        x, y = (y,x+y)
        n = n-1
    return x
 
# 2ª definición
def fib2(n):
    if n == 0:
        return 0
    else: 
        x = 0
        y = 1
        while (n > 1):
            x, y = (y,x+y)
            n = n-1
        return y
					
				
			
		



Ejercicio 21 [Fibonacci por recursión]. Definir, por recursión, la función

fib :: Int -> Int

tal que (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

[fib n | n <- [0..9]]  ==  [0,1,1,2,3,5,8,13,21,34]


Solución:


		
		
			
			
Haskell
			
			-- 1ª definición (semejante a la iterativa con while)
fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux 0 x y = y
    aux n x y = aux (n-1) y (x+y)

-- 2ª definición:
fib2 :: Int -> Int
fib2 n = aux n 0 1 where
     aux 0 x y = x
     aux n x y = aux (n-1) y (x+y)
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
				
						-- 1ª definición (semejante a la iterativa con while)
fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux 0 x y = y
    aux n x y = aux (n-1) y (x+y)
 
-- 2ª definición:
fib2 :: Int -> Int
fib2 n = aux n 0 1 where
     aux 0 x y = x
     aux n x y = aux (n-1) y (x+y)

Ejercicio 22 [El bucle while3]. Definir la función

Solución:

while3 :: (a -> b -> c -> Bool)
       -> (a -> b -> c -> (a,b,c))
       -> a -> b -> c -> c
while3 p f x y z 
    | p x y z   = while3 p f x1 y1 z1
    | otherwise = z 
    where (x1,y1,z1) = f x y z

while3 :: (a -> b -> c -> Bool)

-> (a -> b -> c -> (a,b,c))

-> a -> b -> c -> c

while3 p f x y z

| p x y z = while3 p f x1 y1 z1

| otherwise = z

where (x1,y1,z1) = f x y z

Ejercicio 23 [Fibonacci con while3]. Redefinir, con while3, la función fib.

Solución:

fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux = while3 (\n x y -> n /= 0)
                 (\n x y -> (n-1,y,x+y))

fib :: Int -> Int

fib 0 = 0

fib n = aux (n-1) 0 1 where

aux = while3 (\n x y -> n /= 0)

(\n x y -> (n-1,y,x+y))

El bucle for con un parámetro

Ejercicio 24 [El factorial con for en Python]. Definir en Python, usando for, la función fact tal que fact(n) es el factorial de n. Por ejemplo,: fact(4) == 24

Solución:

def factorial(n):
    f = 1
    for k in range(1,n+1):
        f = k*f
    return f

def factorial(n):

f = 1

for k in range(1,n+1):

f = k*f

return f

Ejercicio 25 [El bucle for]. Definir la función: for :: [a] -> (a -> b -> b) -> b -> b
tal que (for xs f y) es el resultado de iterar f sobre los elementos de xs a partir de y; es decir, si xs es [x(1),...,x(n)] entonces (for xs f y) es (f x(n) (f x(n-2) (... (f x(2) (f x(1) y))))). Por ejemplo,: (for [1..4] (\x s -> x+s)) 0 == 10; (for [1..4] (\x s -> x*s)) 1 == 24

Solución:

-- 1ª definición (por recursión):
for :: [a] -> (a -> b -> b) -> b -> b
for []     f y = y
for (x:xs) f y = for xs f (f x y)

-- 2ª definición (por plegado):
forP :: [a] -> (a -> b -> b) -> b -> b
forP xs f y = foldr f y xs

-- 1ª definición (por recursión):

for :: [a] -> (a -> b -> b) -> b -> b

for [] f y = y

for (x:xs) f y = for xs f (f x y)

-- 2ª definición (por plegado):

forP :: [a] -> (a -> b -> b) -> b -> b

forP xs f y = foldr f y xs

Ejercicio 26 [El factorial con for]. Reefinir, usando for, la función fact.

Solución:

fact :: Integer -> Integer
fact n = for [1..n] (\ k f -> k*f) 1

1 2	fact :: Integer -> Integer fact n = for [1..n] (\ k f -> k*f) 1

El bucle for con dos parámetros

Ejercicio 27 [Fibonacci con for en Python]. Definir en Python, usando for, la función fib tal que fib(n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,: [fib(n) for n in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Solución:

# 1ª definición
def fib(n):
    x = 0
    y = 1
    for k in range(n):
        x, y = (y,x+y)
    return x

# 2ª definición
def fib2(n):
    if n == 0:
        return 0
    else:
        x = 0
        y = 1
        for k in range(1,n):
            x, y = (y,x+y)
        return y

# 1ª definición

def fib(n):

x = 0

y = 1

for k in range(n):

x, y = (y,x+y)

return x

# 2ª definición

def fib2(n):

if n == 0:

return 0

else:

x = 0

y = 1

for k in range(1,n):

x, y = (y,x+y)

return y

Ejercicio 28 [El bucle for2]. Definir el bucle for con 2 parámetros. Por ejemplo.: for2 [1..9] (\x y z -> (x+y,y:z)) 0 [] == [36,28,21,15,10,6,3,1,0]; for2 [1..7] (\x y z -> (x*y,y:z)) 1 [] == [720,120,24,6,2,1,1]

Solución:

for2 :: [a] -> (a -> b -> c -> (b,c)) -> b -> c -> c
for2 []     f _ z = z
for2 (x:xs) f y z = for2 xs f y1 z1
    where (y1,z1) = f x y z

for2 :: [a] -> (a -> b -> c -> (b,c)) -> b -> c -> c

for2 [] f _ z = z

for2 (x:xs) f y z = for2 xs f y1 z1

where (y1,z1) = f x y z

Ejercicio 29 [Fibonacci con for2]. Redefinir, con for2, la función fib.

Solución:

fib :: Int -> Int
fib 0 = 0
fib n = aux (n-1) 0 1 where
    aux n = for2 [1..n] (\k x y -> (y,x+y))

fib :: Int -> Int

fib 0 = 0

fib n = aux (n-1) 0 1 where

aux n = for2 [1..n] (\k x y -> (y,x+y))

Recursión y puntos fijos

Nota. En esta sección se proponen ejercicios para eliminar la recursión mediante puntos fijos; en concreto, usando la función fix tal que (fix f) es el menor punto fijo de f. La función fix está definida en la librería Data.Function como

fix :: (a -> a) -> a
fix f = f (fix f)

1 2	fix :: (a -> a) -> a fix f = f (fix f)

Ejercicio 30 [Factorial mediante fix]. Definir, usando fix, la función: fact :: Integer -> Integer
tal que (fact n) es el factorial de n. Por ejemplo,: [fact n | n <- [0..6]] == [1,1,2,6,24,120,720]

Solución:

import Data.Function (fix)

-- 1ª definición (con auxiliar)
fact :: Integer -> Integer
fact = fix aux

aux :: (Integer -> Integer) -> Integer -> Integer
aux f n = if n == 0 then 1 else n * f (n-1)

-- Cálculo de (fact 3)
--    fact 3 =
--    = (fix aux) 3
--    = aux (fix aux) 3
--    = 3 * ((fix aux) 2)
--    = 3 * (aux (fix aux) 2)
--    = 3 * (2 * ((fix aux) 1))
--    = 3 * (2 * ((fix aux) 1))
--    = 3 * (2 * (aux (fix aux) 1))
--    = 3 * (2 * (1 * ((fix aux) 0)))
--    = 3 * (2 * (1 * 1))
--    = 6

-- 2ª definición (sin auxiliar)
fact2 :: Integer -> Integer
fact2 = fix (\f n -> if n == 0 then 1 else n * f (n-1))

-- Nota. Puesto que fact es punto fijo de aux, se tiene
--    fact = aux fact
--         = (\f n -> if n == 0 then 1 else n * f (n-1)) fact
--         = \n -> if n == 0 then 1 else n * fact (n-1)

import Data.Function (fix)

-- 1ª definición (con auxiliar)

fact :: Integer -> Integer

fact = fix aux

aux :: (Integer -> Integer) -> Integer -> Integer

aux f n = if n == 0 then 1 else n * f (n-1)

-- Cálculo de (fact 3)

-- fact 3 =

-- = (fix aux) 3

-- = aux (fix aux) 3

-- = 3 * ((fix aux) 2)

-- = 3 * (aux (fix aux) 2)

-- = 3 * (2 * ((fix aux) 1))

-- = 3 * (2 * (aux (fix aux) 1))

-- = 3 * (2 * (1 * ((fix aux) 0)))

-- = 3 * (2 * (1 * 1))

-- = 6

-- 2ª definición (sin auxiliar)

fact2 :: Integer -> Integer

fact2 = fix (\f n -> if n == 0 then 1 else n * f (n-1))

-- Nota. Puesto que fact es punto fijo de aux, se tiene

-- fact = aux fact

-- = (\f n -> if n == 0 then 1 else n * f (n-1)) fact

-- = \n -> if n == 0 then 1 else n * fact (n-1)

Ejercicio 31 [Fibonacci mediante fix]. Definir, usando fix, la función: fib :: Int -> Int
tal que (fib n) es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,: [fib n | n <- [0..9]] == [0,1,1,2,3,5,8,13,21,34]

Solución:

import Data.Function (fix)

-- 1ª definición (con auxiliares)
fib :: Int -> Int
fib = fibAux 0 1 where
    fibAux      = fix aux 
    aux f x y n = if n == 0 then x else f y (x+y) (n-1)

-- Cálculo de (fib 6)
--    fib 6
--    = fibAux 0 1 6
--    = (fix aux) 0 1 6
--    = aux (fix aux) 0 1 6
--    = (fix aux) 1 1 5
--    = aux (fix aux) 1 1 5
--    = (fix aux) 1 2 4
--    = aux (fix aux) 1 2 4
--    = (fix aux) 2 3 3
--    = aux (fix aux) 2 3 3
--    = (fix aux) 3 5 2
--    = aux (fix aux) 3 5 2
--    = (fix aux) 5 8 1
--    = aux (fix aux) 8 13 0
--    = 8

-- 2ª definición (sin auxiliares):
fib2 :: Int -> Int
fib2 = (fix (\f x y n -> if n == 0 then x else f y (x+y) (n-1))) 0 1

-- Nota. Puesto que fibAux es punto fijo de aux, se tiene
--    fibAux = aux fibAux
--           = (\f x y n -> if n == 0 then x else f y (x+y) (n-1)) fibAux 
--           = \x y n -> if n == 0 then x else fibAux y (x+y) (n-1)

import Data.Function (fix)

-- 1ª definición (con auxiliares)

fib :: Int -> Int

fib = fibAux 0 1 where

fibAux = fix aux

aux f x y n = if n == 0 then x else f y (x+y) (n-1)

-- Cálculo de (fib 6)

-- fib 6

-- = fibAux 0 1 6

-- = (fix aux) 0 1 6

-- = aux (fix aux) 0 1 6

-- = (fix aux) 1 1 5

-- = aux (fix aux) 1 1 5

-- = (fix aux) 1 2 4

-- = aux (fix aux) 1 2 4

-- = (fix aux) 2 3 3

-- = aux (fix aux) 2 3 3

-- = (fix aux) 3 5 2

-- = aux (fix aux) 3 5 2

-- = (fix aux) 5 8 1

-- = aux (fix aux) 8 13 0

-- = 8

-- 2ª definición (sin auxiliares):

fib2 :: Int -> Int

fib2 = (fix (\f x y n -> if n == 0 then x else f y (x+y) (n-1))) 0 1

-- Nota. Puesto que fibAux es punto fijo de aux, se tiene

-- fibAux = aux fibAux

-- = (\f x y n -> if n == 0 then x else f y (x+y) (n-1)) fibAux

-- = \x y n -> if n == 0 then x else fibAux y (x+y) (n-1)

Ejercicio 32 [La órbita de Collatz mediante fix]. Definir, usando fix, la función: collatz :: Integer -> [Integer]
tal que (collatz n) es la órbita de Collatz de n. Por ejemplo,: collatz 7 == [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

Solución:

import Data.Function (fix)

-- 1ª definición (con auxiliares):
collatz :: Integer -> [Integer]
collatz n = reverse (collatzAux [n]) where
    collatzAux   = fix aux
    aux f (n:ns) = if n == 1 
                   then n:ns
                   else if even n 
                        then f (div n 2:n:ns)
                        else f (3*n+1:n:ns)

-- 2ª definición (sin auxiliares):
collatz2 :: Integer -> [Integer]
collatz2 n = 
   reverse ((fix (\f (n:ns) -> if n == 1 
                               then n:ns
                               else if even n 
                                    then f (div n 2:n:ns)
                                    else f (3*n+1:n:ns)))
            [n])

-- Nota: Puesto que collatzAux es un punto fijo de aux, se tiene
--    collatzAux = aux collatzAux
--               = (\f (n:ns) -> if n == 1 
--                               then n:ns
--                               else if even n 
--                                    then f (div n 2:n:ns)
--                                    else f (3*n+1:n:ns)) collatzAux
--               = \(n:ns) -> if n == 1 
--                            then n:ns
--                            else if even n 
--                                 then collatzAux (div n 2:n:ns)
--                                 else collatzAux (3*n+1:n:ns)

import Data.Function (fix)

-- 1ª definición (con auxiliares):

collatz :: Integer -> [Integer]

collatz n = reverse (collatzAux [n]) where

collatzAux = fix aux

aux f (n:ns) = if n == 1

then n:ns

else if even n

then f (div n 2:n:ns)

else f (3*n+1:n:ns)

-- 2ª definición (sin auxiliares):

collatz2 :: Integer -> [Integer]

collatz2 n =

reverse ((fix (\f (n:ns) -> if n == 1

then n:ns

else if even n

then f (div n 2:n:ns)

else f (3*n+1:n:ns)))

[n])

-- Nota: Puesto que collatzAux es un punto fijo de aux, se tiene

-- collatzAux = aux collatzAux

-- = (\f (n:ns) -> if n == 1

-- then n:ns

-- else if even n

-- then f (div n 2:n:ns)

-- else f (3*n+1:n:ns)) collatzAux

-- = \(n:ns) -> if n == 1

-- then n:ns

-- else if even n

-- then collatzAux (div n 2:n:ns)

-- else collatzAux (3*n+1:n:ns)

Ejercicio 33 [Suma impares mediante fix]. Definir, usando fix, la función: sumaImpares :: Int -> Int
tal que (sumaImpares n) es la suma de los primeros n números impares. Por ejemplo,: sumaImpares 3 == 9; sumaImpares 4 == 16

Solución:

import Data.Function (fix)

sumaImpares :: Int -> Int
sumaImpares n = sumaImparesAux n 0 0 where
    sumaImparesAux = fix aux
    aux f n k s | k < n     = f n (k + 1) (s + 2*k + 1)
                | otherwise = s

import Data.Function (fix)

sumaImpares :: Int -> Int

sumaImpares n = sumaImparesAux n 0 0 where

sumaImparesAux = fix aux

aux f n k s | k < n = f n (k + 1) (s + 2*k + 1)

| otherwise = s

Referencias

A.V. Aho y J.D. Ullman. Iteration, induction, and recursion. Capítulo 2 de Foundations of Computer Science.
H. Lee An introduction to fixpoint in Haskell.
J. van Eijck. Functional imperative style. Capítulo 2 de Purely functional algorithm specification.
Wikibooks. Haskell/Fix and recursion.
Wikipedia. For loop
Wikipedia. While loop.

El bucle while con un parámetro

El bucle while con dos parámetros

El bucle while con tres parámetros

El bucle for con un parámetro

El bucle for con dos parámetros

Recursión y puntos fijos

Referencias

Se puede imprimir o compartir con