Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Leer más…

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

cambios :: [Int] -> [(Int,Int)]
nRaicesPositivas :: [Int] -> [Int]

tales que

• (cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

cambios [1,3,0,-5,1,-7]  ==  [(3,-5),(-5,1),(1,-7)]

• (nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

nRaicesPositivas [1,3,0,-5,1,-7]  ==  [3,1]

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Leer más…

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

taxicab  :: [Integer]
taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

take 5 taxicab   ==  [1729,4104,13832,20683,32832]
take 2 taxicab2  ==  [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Leer más…

Los números naturales pueden definirse de forma alternativa empleando los números de Church. Podemos representar un número natural n como una función que toma una función f como parámetro y devuelve n veces f.

Definimos por tanto los números naturales como

Type Nat = forall a. (a -> a) -> a -> a

De esta forma, para representar el número uno, repetir una vez una función es lo mismo que solamente aplicarla.

uno :: Nat
uno f x = f x

De manera similar, dos debe aplicar f dos veces a su argumento.

dos :: Nat
dos f x = f (f x)

Definir cero equivale por tanto a devolver el argumento sin modificar.

cero :: Nat
cero f x = x

Definir las funciones

cero    :: Nat
uno     :: Nat
dos     :: Nat
tres    :: Nat
nat2Int :: Nat -> Int
succ    :: Nat -> Nat
suma    :: Nat -> Nat -> Nat
mult    :: Nat -> Nat -> Nat
exp     :: Nat -> Nat -> Nat

tales que

• cero, uno y dos son definiciones alternativas a las ya dadas y tres es el número natural 3 con esta representación.
• (nat2Int n) es el número entero correspondiente al número natuaral n. Por ejemplo,

nat2Int cero == 0
nat2Int uno  == 1
nat2Int dos  == 2
nat2Int tres == 3

• (succ n) es el sucesor del número n. Por ejemplo,

nat2Int (succ dos)   ==  3
nat2Int (succ tres)  ==  4

• (suma n m) es la suma de n y m. Por ejemplo,

nat2Int (suma dos tres)         ==  5
nat2Int (suma dos (succ tres))  ==  6

• (mult n m) es el producto de n y m. Por ejemplo,

nat2Int (mult dos tres)         ==  6
nat2Int (mult dos (succ tres))  ==  8

• (exp n m) es la potencia m-ésima de n. Por ejemplo,

nat2Int (exp dos tres)   ==  8
nat2Int (exp tres dos)   ==  9
nat2Int (exp tres cero)  ==  1
nat2Int (exp cero tres)  ==  0

Comprobar con QuickCheck las siguientes propiedades. Para ello importar la librería Test.QuickCheck.Function y seguir el siguiente ejemplo:

prop_Succ1 :: Fun Int Int -> Int -> Bool
prop_Succ1 (Fun _ f) x = succ cero f x == uno f x

succ uno                   = dos
succ dos                   = tres
suma cero uno              = uno
suma dos tres              = suma tres dos
suma (suma dos dos) tres   = suma uno (suma tres tres)
mult uno uno               = uno
mult cero (suma tres tres) = cero
mult dos tres              = suma tres tres
exp dos dos                = suma dos dos
exp tres dos               = suma (mult dos (mult dos dos)) uno
exp tres cero              = uno

Nota 1: Añadir al inicio del archivo del ejercicio los pragmas

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TemplateHaskell #-}

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Leer más…

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 3
5 = 1 + 3 + 1
5 = 3 + 1 + 1
5 = 1 + 4
5 = 4 + 1

Definir las funciones

descomposiciones  :: Integer -> [[Integer]]
nDescomposiciones :: Integer -> Integer

tales que

• (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

λ> descomposiciones1 4
[[4],[3,1],[1,3],[1,1,1,1]]
λ> descomposiciones1 5
[[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]
λ> descomposiciones1 6
[[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],
[1,1,1,3],[1,1,1,1,1,1]]

• (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,

nDescomposiciones 5                       ==  6
nDescomposiciones 10                      ==  64
nDescomposiciones 20                      ==  7921
nDescomposiciones 30                      ==  974169
length (show (nDescomposiciones (10^5)))  ==  20899

Nota: Se puede usar programación dinámica.

Leer más…

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

solucionesTresJarras :: Problema -> [[Estado]]
tresJarras :: Problema -> Maybe [Estado]

tales que

• (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

λ> mapM_ print (solucionesTresJarras (4,2,1))
[(4,0,0),(2,2,0)]
[(4,0,0),(3,0,1),(1,2,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]
λ> mapM_ print (solucionesTresJarras (8,6,2))
[(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
λ> length (solucionesTresJarras (8,5,3))
16
λ> head (solucionesTresJarras (8,5,3))
[(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> length (solucionesTresJarras (8,6,5))
0

• (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> tresJarras (4,2,1)
Just [(4,0,0),(2,2,0)]
λ> tresJarras (8,6,2)
Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
λ> tresJarras (8,5,3)
Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> tresJarras (8,6,5)
Nothing

Leer más…

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

1 ----- 2
| \     |
|  3    |
| /     |
4 ----- 5

se puede representar por la matriz de adyacencia

|0 1 1 1 0|
|1 0 0 0 1|
|1 0 0 1 0|
|1 0 1 0 1|
|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

matrizAlista :: Matrix Int -> [(Int,[Int])]
listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

• (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por

ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
[1,0,0,0,1],
[1,0,0,1,0],
[1,0,1,0,1],
[0,1,0,1,0]]

se tiene que

λ> matrizAlista ejMatriz
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

• (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,

λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
( 0 1 1 1 0 )
( 1 0 0 0 1 )
( 1 0 0 1 0 )
( 1 0 1 0 1 )
( 0 1 0 1 0 )
λ> matrizAlista it
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Leer más…

La sucesión de polinomios de Fibonacci se define por

p(0) = 0
p(1) = 1
p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

p(2) = x
p(3) = x^2 + 1
p(4) = x^3 + 2*x
p(5) = x^4 + 3*x^2 + 1

Definir la lista

sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

λ> take 7 sucPolFib
[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
λ> sum (map grado (take 3000 sucPolFib2))
4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, ...

Nota. Limitar la búsqueda a ejemplos pequeños usando

quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Leer más…

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

• (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

• (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Leer más…