Ir al contenido principal

Existencia de elementos del árbol que verifican una propiedad

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, el árbol

        5
       / \
      /   \
     3     2
    / \
   1   4

se representa por

   N 5 (N 3 (H 1) (H 4)) (H 2)

Definir la función

   algunoArbol :: Arbol t -> (t -> Bool) -> Bool

tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,

   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True
   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  False

Leer más…

Árboles con igual estructura

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

        5              8             5           5
       / \            / \           / \         / \
      /   \          /   \         /   \       /   \
     9     7        9     3       9     2     4     7
    / \   / \      / \   / \     / \               / \
   1   4 6   8    1   4 6   2   1   4             6   2

se pueden representar por

   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))
   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

Definir la función

   igualEstructura :: Arbol -> Arbol -> Bool

tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,

   igualEstructura ej3arbol1 ej3arbol2 == True
   igualEstructura ej3arbol1 ej3arbol3 == False
   igualEstructura ej3arbol1 ej3arbol4 == False

Leer más…

Árboles con bordes iguales

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en las hojas se pueden definir por

   data Arbol a = H a
                | N (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

   árbol1          árbol2       árbol3     árbol4
      o              o           o           o
     / \            / \         / \         / \
    1   o          o   3       o   3       o   1
       / \        / \         / \         / \
      2   3      1   2       1   4       2   3

se representan por

   arbol1, arbol2, arbol3, arbol4 :: Arbol Int
   arbol1 = N (H 1) (N (H 2) (H 3))
   arbol2 = N (N (H 1) (H 2)) (H 3)
   arbol3 = N (N (H 1) (H 4)) (H 3)
   arbol4 = N (N (H 2) (H 3)) (H 1)

Definir la función

   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,

   igualBorde arbol1 arbol2  ==  True
   igualBorde arbol1 arbol3  ==  False
   igualBorde arbol1 arbol4  ==  False

Leer más…

Árboles balanceados

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.

Definir la función

   balanceado :: Arbol a -> Bool

tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,

   λ> balanceado (N 5 H (N 3 H H))
   True
   λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))
   False

Leer más…

Rama izquierda de un árbol binario.

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol1 a) (Arbol1 a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir la función

   ramaIzquierda :: Arbol a -> [a]

tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,

   λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H))
   [2,5,3]

<!-- TEASER_END -->~~~
# Soluciones

A continuación se muestran las [soluciones en Haskell](#haskell) y las [soluciones en Python](#python).

<a name="haskell"></a>
## Soluciones en Haskell

~~~haskell
data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

ramaIzquierda :: Arbol a -> [a]
ramaIzquierda H         = []
ramaIzquierda (N x i _) = x : ramaIzquierda i

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    pass

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def ramaIzquierda(a: Arbol[A]) -> list[A]:
    match a:
        case H():
            return []
        case N(x, i, _):
            return [x] + ramaIzquierda(i)
    assert False

Suma de un árbol

Tipos definidos y tipos de datos algebraicos

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol1 a) (Arbol1 a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir por recursión la función

   sumaArbol :: Num a => Arbol1 a -> a

tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,

   sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21

Leer más…

El tipo de los árboles binarios con valores en los nodos

Tipos definidos y tipos de datos algebraicos

1. El tipo de los árboles binarios con valores en los nodos en Haskell

El árbol, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

2. El tipo de los árboles binarios con valores en los nodos en Python

El árbol binario, con valores en los nodos,

           9
          / \
         /   \
        /     \
       8       6
      / \     / \
     3   2   4   5
    /\  /\  /\   /\
   ·  ··  ··  · ·  ·

se puede representar por

   N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))

usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.

from dataclasses import dataclass


@dataclass
class Arbol:
    pass

@dataclass
class H(Arbol):
    pass

@dataclass
class N(Arbol):
    x: int
    i: Arbol
    d: Arbol

Árbol de profundidad n con nodos iguales

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir las funciones

   repeatArbol    :: a -> Arbol a
   replicateArbol :: Int -> a -> Arbol a

tales que

  • repeatArbol x es es árbol con infinitos nodos x. Por ejemplo,
     takeArbol 0 (repeatArbol 3) == H 3
     takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
     takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
  • replicate n x es el árbol de profundidad n cuyos nodos son x. Por ejemplo,
     replicateArbol 0 5  ==  H 5
     replicateArbol 1 5  ==  N 5 (H 5) (H 5)
     replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))

Leer más…

Subárbol de profundidad dada

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

La función take está definida por

   take :: Int -> [a] -> [a]
   take 0            = []
   take (n+1) []     = []
   take (n+1) (x:xs) = x : take n xs

Definir la función

   takeArbol ::  Int -> Arbol a -> Arbol a

tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,

   takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
   takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
   takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
   takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)

Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.

Leer más…

Imagen especular de un árbol binario

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   espejo :: Arbol a -> Arbol a

tal que espejo x es la imagen especular del árbol x. Por ejemplo,

   espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))

Comprobar con QuickCheck las siguientes propiedades, para todo árbol x,

   espejo (espejo x) = x
   reverse (preorden (espejo x)) = postorden x
   postorden (espejo x) = reverse (preorden x)

Leer más…

Recorrido de árboles binarios

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir las funciones

   preorden  :: Arbol a -> [a]
   postorden :: Arbol a -> [a]

tales que

  • preorden es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo,
     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
  • postorden x es la lista correspondiente al recorrido postorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación el subárbol derecho y, finalmente, la raíz del árbol. Por ejemplo,
     postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]

Comprobar con QuickCheck que la longitud de la lista obtenida recorriendo un árbol en cualquiera de los sentidos es igual al número de nodos del árbol más el número de hojas.

Leer más…

Profundidad de un árbol binario

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   profundidad :: Arbol a -> Int

tal que profundidad x es la profundidad del árbol x. Por ejemplo,

   profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2
   profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3
   profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2

Comprobar con QuickCheck que para todo árbol biario x, se tiene que

   nNodos x <= 2^(profundidad x) - 1

Leer más…

Número de hojas de un árbol binario

Tipos definidos y tipos de datos algebraicos

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

El tipo de los árboles binarios se puede definir por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)

Definir las funciones

   nHojas :: Arbol a -> Int
   nNodos :: Arbol a -> Int

tales que

  • (nHojas x) es el número de hojas del árbol x. Por ejemplo,
     nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3
  • (nNodos x) es el número de nodos del árbol x. Por ejemplo,
     nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2

Comprobar con QuickCheck que en todo árbol binario el número de sus hojas es igual al número de sus nodos más uno.

Leer más…

El tipo de los árboles binarios

Tipos definidos y tipos de datos algebraicos

1. El tipo de los árboles binarios en Haskell

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

usando el tipo de los árboles binarios definido como se muestra a continuación.

import Test.QuickCheck

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

-- Generador de árboles binarios
-- =============================

-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    N 0 (H 0) (H 0)
--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)
--    N 3 (H 1) (H 2)
--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))
--    H 7
--    N (-8) (H (-8)) (H 9)
--    H 2
--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))
--    H (-3)
--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)
--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario 0 = H <$> arbitrary
arbolArbitrario n =
  oneof [H <$> arbitrary,
         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]

-- Arbol es subclase de Arbitrary
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario

2. El tipo de los árboles binarios en Python

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   N(9, N(3, H(2), H(4)), H(7))

usando la definición de los árboles binarios que se muestra a continuación.

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

def nHojas(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 1
        case N(_, i, d):
            return nHojas(i) + nHojas(d)
    assert False

def nNodos(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 0
        case N(_, i, d):
            return 1 + nNodos(i) + nNodos(d)
    assert False

# Generador de árboles
# ====================

# (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
#    >>> arbolArbitrario(4)
#    N(x=2, i=H(x=1), d=H(x=9))
#    >>> arbolArbitrario(4)
#    H(x=10)
#    >>> arbolArbitrario(4)
#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))
def arbolArbitrario(n: int) -> Arbol[int]:
    if n <= 1:
        return H(randint(0, 10))
    m = n // 2
    return choice([H(randint(0, 10)),
                   N(randint(0, 10),
                     arbolArbitrario(m),
                     arbolArbitrario(m))])

El tipo de las expresiones aritméticas - Valor de una expresión

Tipos definidos y tipos de datos algebraicos

Usando el tipo de las expresiones aritméticas, definir la función

   valor :: Expr -> Int

tal que valor e es el valor de la expresión e (donde el valor de SiCero e e1 e2 es el valor de e1 si el valor de e es cero y el es el valor de e2, en caso contrario). Por ejemplo,

   valor (Op (Suma (Lit 3) (Lit 5)))      ==  -8
   valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4
   valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5

Leer más…

El tipo de las expresiones aritméticas

Tipos definidos y tipos de datos algebraicos

1. El tipo de las expresiones aritméticas en Haskell

El tipo de las expresiones aritméticas formadas por

  • literales (p.e. Lit 7),
  • sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
  • opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
  • expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

se define como se muestra a continuación.

data Expr = Lit Int
          | Suma Expr Expr
          | Op Expr
          | SiCero Expr Expr Expr
  deriving (Eq, Show)

2. El tipo de las expresiones aritméticas en Python

El tipo de las expresiones aritméticas formadas por

  • literales (p.e. Lit 7),
  • sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
  • opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
  • expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

se define como se muestra a continuación.

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class Lit(Expr):
    x: int

@dataclass
class Suma(Expr):
    x: Expr
    y: Expr

@dataclass
class Op(Expr):
    x: Expr

@dataclass
class SiCero(Expr):
    x: Expr
    y: Expr
    z: Expr

Árbol con las hojas en la profundidad dada

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   creaArbol :: Int -> Arbol ()

tal que creaArbol n es el árbol cuyas hoyas están en la profundidad n. Por ejemplo,

   λ> creaArbol 2
   Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ()))

Leer más…

Árboles con la misma forma

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mismaForma :: Arbol a -> Arbol b -> Bool

tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,

   λ> arbol1 = Hoja 5
   λ> arbol2 = Hoja 3
   λ> mismaForma arbol1 arbol2
   True
   λ> arbol3 = Nodo (Hoja 6) (Hoja 7)
   λ> mismaForma arbol1 arbol3
   False
   λ> arbol4 = Nodo (Hoja 9) (Hoja 5)
   λ> mismaForma arbol3 arbol4
   True

Leer más…

Aplicación de una función a un árbol

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mapArbol :: (a -> b) -> Arbol a -> Arbol b

tal que mapArbol f t es el árbolo obtenido aplicando la función f a los elementos del árbol t. Por ejemplo,

   λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))
   Nodo (Hoja 3) (Hoja 5)

Leer más…

Altura de un árbol binario

Tipos definidos y tipos de datos algebraicos

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)

Definir la función

   altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

Leer más…

El tipo de los árboles binarios con valores en las hojas.

Tipos definidos y tipos de datos algebraicos

1. El tipo de los árboles binarios con valores en las hojas en Haskell

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)

2. El tipo de los árboles binarios con valores en las hojas en Python

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo(Nodo(Hoja(1), Hoja(4)),
                  Nodo(Hoja(6), Hoja(9)))

usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class Hoja(Arbol[A]):
    x: A

@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]

El tipo de las fórmulas proposicionales - Reconocedor de tautologías

Tipos definidos y tipos de datos algebraicos

Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,

  • (A ∧ B) → A es una tautología
  • A → (A ∧ B) no es una tautología

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   esTautologia :: FProp -> Bool

tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,

   λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
   True
   λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   False

Leer más…

El tipo de las fórmulas proposicionales - Interpretaciones de una fórmula

Tipos definidos y tipos de datos algebraicos

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   interpretaciones :: FProp -> [Interpretacion]

tal que interpretaciones p es la lista de las interpretaciones de la fórmula p. Por ejemplo,

   λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   [[('A',False),('B',False)],
    [('A',False),('B',True)],
    [('A',True),('B',False)],
    [('A',True),('B',True)]]

Leer más…

El tipo de las fórmulas proposicionales - Valor de una fórmula

Tipos definidos y tipos de datos algebraicos

Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por

   [('A', True), ('B', False)]

El tipo de las intepretaciones de puede definir por

   type Interpretacion = [(Char, Bool)]

El valor de una fórmula en una interpretación se calcula usando las funciones de verdad de las conectivas que se muestran a continuación

   |---+----|   |---+---+-------+-------|
   | p | ¬p |   | p | q | p ∧ q | p → q |
   |---+----|   |---+---+-------+-------|
   | T | F  |   | T | T | T     | T     |
   | F | T  |   | T | F | F     | F     |
   |---+----|   | F | T | F     | T     |
                | F | F | F     | T     |
                |---+---+-------+-------|

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   valor :: Interpretacion -> FProp -> Bool

tal que valor i p es el valor de la fórmula p en la interpretación i. Por ejemplo,

   λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
   λ> valor [('A',False),('B',False)] p
   True
   λ> valor [('A',True),('B',False)] p
   False

Leer más…

El tipo de las fórmulas proposicionales - Variables de una fórmula

Tipos definidos y tipos de datos algebraicos

Usando el tipo de las fórmulas proposicionales definido en el ejercicio anterior, definir la función

   variables :: FProp -> [Char]

tal que variables p es la lista de las variables de la fórmula p. Por ejemplo,

   λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
   "AB"
   λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
   "AAB"

Leer más…

El tipo de las fórmulas proposicionales

Tipos definidos y tipos de datos algebraicos

1. El tipo de las fórmulas proposicionales en Haskell

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

usando el tipo de las fórmulas proposicionales definido por

data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show

1. El tipo de las fórmulas proposicionales en Python

La fórmula A → ⊥ ∧ ¬B se representa por

   Impl(Var('A'), Conj(Const(False), Neg (Var('B'))))

usando el tipo de las fórmulas proposicionales definido por

from dataclasses import dataclass

@dataclass
class FProp:
    pass

@dataclass
class Const(FProp):
    x: bool

@dataclass
class Var(FProp):
    x: str

@dataclass
class Neg(FProp):
    x: FProp

@dataclass
class Conj(FProp):
    x: FProp
    y: FProp

@dataclass
class Impl(FProp):
    x: FProp
    y: FProp

El tipo de los árboles binarios

Tipos definidos y tipos de datos algebraicos

El árbol binario

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
                  5
                  (Nodo (Hoja 6) 7 (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol = Hoja Int
              | Nodo Arbol Int Arbol

Definir las funciones

   ocurre :: Int -> Arbol -> Bool
   aplana :: Arbol -> [Int]

tales que

  • ocurre m a se verifica si m ocurre en el árbol a. Por ejemplo,
     ocurre 4  ejArbol  ==  True
     ocurre 10 ejArbol  ==  False
  • aplana a es la lista obtenida aplanando el árbol a. Por ejemplo,
     aplana ejArbol  ==  [1,3,4,5,6,7,9]

Leer más…

El tipo de las listas

Tipos definidos y tipos de datos algebraicos

El tipo de las listas, con elementos de tipo a, se puede definir por

   data Lista a = Nil | Cons a (Lista a)

Por ejemplo, la lista [4,2,5] se representa por Cons 4 (Cons 2 (Cons 5 Nil)).

Definir la función

   longitud :: Lista a -> Int

tal que longitud xs es la longitud de la lista xs. Por ejemplo,

   longitud (Cons 4 (Cons 2 (Cons 5 Nil)))  ==  3

Leer más…

El tipo de los números naturales

Tipos definidos y tipos de datos algebraicos

El tipo de los números raturales se puede definir por

   data Nat = Cero | Suc Nat
     deriving (Show, Eq)

de forma que Suc (Suc (Suc Cero)) representa el número 3.

Definir las siguientes funciones

   nat2int :: Nat -> Int
   int2nat :: Int -> Nat
   suma    :: Nat -> Nat -> Nat

tales que

  • nat2int n es el número entero correspondiente al número natural n. Por ejemplo,
     nat2int (Suc (Suc (Suc Cero)))  ==  3
  • int2nat n es el número natural correspondiente al número entero n. Por ejemplo,
     int2nat 3  ==  Suc (Suc (Suc Cero))
  • suma m n es la suma de los número naturales m y n. Por ejemplo,
     λ> suma (Suc (Suc Cero)) (Suc Cero)
     Suc (Suc (Suc Cero))
     λ> nat2int (suma (Suc (Suc Cero)) (Suc Cero))
     3
     λ> nat2int (suma (int2nat 2) (int2nat 1))
     3

Leer más…

El tipo de figuras geométricas

Tipos definidos y tipos de datos algebraicos

Se consideran las figuras geométricas formadas por circulos (definidos por su radio) y rectángulos (definidos por su base y su altura). El tipo de las figura geométricas se define por

   data Figura = Circulo Float | Rect Float Float

Definir las funciones

   area     :: Figura -> Float
   cuadrado :: Float -> Figura

tales que

  • area f es el área de la figura f. Por ejemplo,
     area (Circulo 1)   ==  3.1415927
     area (Circulo 2)   ==  12.566371
     area (Rect 2 5)    ==  10.0
  • cuadrado n es el cuadrado de lado n. Por ejemplo,
     area (cuadrado 3)  ==  9.0

Leer más…

Movimientos en el plano

Tipos definidos y tipos de datos algebraicos

Se consideran el tipo de las posiciones del plano definido por

   type Posicion = (Int,Int)

y el tipo de las direcciones definido por

   data Direccion = Izquierda | Derecha | Arriba | Abajo
     deriving Show

Definir las siguientes funciones

   opuesta     :: Direccion -> Direccion
   movimiento  :: Posicion -> Direccion -> Posicion
   movimientos :: Posicion -> [Direccion] -> Posicion

tales que

  • opuesta d es la dirección opuesta de d. Por ejemplo,
     opuesta Izquierda == Derecha
  • movimiento p d es la posición reultante de moverse, desde la posición p, un paso en la dirección d. Por ejemplo,
     movimiento (2,5) Arriba          == (2,6)
     movimiento (2,5) (opuesta Abajo) == (2,6)
  • movimientos p ds es la posición obtenida aplicando la lista de movimientos según las direcciones de ds a la posición p. Por ejemplo,
     movimientos (2,5)  [Arriba, Izquierda] == (1,6)

Leer más…

Máximo de una lista

Funciones de orden superior

Definir la función

   maximo :: Ord a => [a] -> a

tal que maximo xs es el máximo de la lista xs. Por ejemplo,

   maximo [3,7,2,5]                  ==  7
   maximo ["todo","es","falso"]      ==  "todo"
   maximo ["menos","alguna","cosa"]  ==  "menos"

Leer más…

Aplica según propiedad

Funciones de orden superior

Definir la función

   filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b]

tal que filtraAplica f p xs es la lista obtenida aplicándole a los elementos de xs que cumplen el predicado p la función f. Por ejemplo,

   filtraAplica (4+) (<3) [1..7]  ==  [5,6]

Leer más…

Concatenación de una lista de listas

Funciones de orden superior

Definir, por recursión, la función

   conc :: [[a]] -> [a]

tal que conc xss es la concenación de las listas de xss. Por ejemplo,

   conc [[1,3],[2,4,6],[1,9]]  ==  [1,3,2,4,6,1,9]

Comprobar con QuickCheck que la longitud de conc xss es la suma de las longitudes de los elementos de xss.

Leer más…

Agrupación de elementos por posición

Funciones de orden superior

Definir la función

   agrupa :: Eq a => [[a]] -> [[a]]

tal que agrupa xsses la lista de las listas obtenidas agrupando los primeros elementos, los segundos, ... Por ejemplo,

   agrupa [[1..6],[7..9],[10..20]]  ==  [[1,7,10],[2,8,11],[3,9,12]]

Comprobar con QuickChek que la longitud de todos los elementos de agrupa xs es igual a la longitud de xs.

Leer más…

Elementos consecutivos relacionados

Funciones de orden superior

Definir la función

   relacionados :: (a -> a -> Bool) -> [a] -> Bool

tal que relacionados r xs se verifica si para todo par (x,y) de elementos consecutivos de xs se cumple la relación r. Por ejemplo,

   relacionados (<) [2,3,7,9] == True
   relacionados (<) [2,3,1,9] == False

Leer más…

Reconocimiento de subcadenas

Definiciones por recursión

Definir, por recursión, la función

   esSubcadena :: String -> String -> Bool

tal que esSubcadena xs ys se verifica si xs es una subcadena de ys. Por ejemplo,

   esSubcadena "casa" "escasamente"   ==  True
   esSubcadena "cante" "escasamente"  ==  False
   esSubcadena "" ""                  ==  True

Leer más…

Mayúsculas iniciales

Definiciones por recursión

Se consideran las siguientes reglas de mayúsculas iniciales para los títulos:

  • la primera palabra comienza en mayúscula y
  • todas las palabras que tienen 4 letras como mínimo empiezan con mayúsculas

Definir la función

   titulo :: [String] -> [String]

tal que titulo ps es la lista de las palabras de ps con las reglas de mayúsculas iniciales de los títulos. Por ejemplo,

   λ> titulo ["eL","arTE","DE","La","proGraMacion"]
   ["El","Arte","de","la","Programacion"]

Leer más…

Números de Lychrel

Definiciones por recursión

Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel: + 56, ya que en un paso se obtiene un capicúa: 56+65=121. + 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363 + 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111 + 89, ya que en 24 pasos se obtiene un capicúa. En esta serie de ejercicios vamos a buscar el primer número de Lychrel.

Leer más…

El algoritmo de Luhn

Definiciones por recursión

El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores numéricos como los números de algunas tarjetas de crédito; por ejemplo, las de tipo Visa o Master Card.

El algoritmo que vamos a estudiar es el algoritmo de Luhn consistente en aplicar los siguientes pasos a los dígitos del número de la tarjeta.

  1. Se invierten los dígitos del número; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].
  2. Se duplican los dígitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].
  3. Se suman los dígitos de cada número; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.
  4. Si el último dígito de la suma es 0, el número es válido; y no lo es, en caso contrario.

A los números válidos, se les llama números de Luhn.

Definir las siguientes funciones:

   digitosInv    :: Integer -> [Integer]
   doblePosImpar :: [Integer] -> [Integer]
   sumaDigitos   :: [Integer] -> Integer
   ultimoDigito  :: Integer -> Integer
   luhn          :: Integer -> Bool

tales que

  • digitosInv n es la lista de los dígitos del número n, en orden inverso. Por ejemplo,
     digitosInv 320274  ==  [4,7,2,0,2,3]
  • doblePosImpar ns es la lista obtenida doblando los elementos de ns en las posiciones impares (empezando a contar en cero y dejando igual a los que están en posiciones pares. Por ejemplo,
     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]
     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]
  • sumaDigitos ns es la suma de los dígitos de ns. Por ejemplo,
     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =
                             = 19
  • ultimoDigito n es el último dígito de n. Por ejemplo,
     ultimoDigito 123 == 3
     ultimoDigito   0 == 0
  • luhn n se verifica si n es un número de Luhn. Por ejemplo,
     luhn 5594589764218858  ==  True
     luhn 1234567898765432  ==  False

Leer más…

Subconjuntos de un conjunto

Definiciones por recursión

Definir la función

   subconjuntos :: [a] -> [[a]]

tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,

   λ> subconjuntos [2,3,4]
   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
   λ> subconjuntos [1,2,3,4]
   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]

Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.

Leer más…

Producto cartesiano de dos conjuntos

Definiciones por recursión

Definir la función

   producto :: [a] -> [b] -> [(a,b)]

tal que producto xs ys es el producto cartesiano de xs e ys. Por ejemplo,

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.

Leer más…

Algoritmo de Euclides del mcd

Definiciones por recursión

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 45 30  ==  15

Comprobar con QuickCheck que 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.

Leer más…

Base de dato de actividades

Definiciones por comprensión

Las bases de datos sobre actividades de personas pueden representarse mediante listas de elementos de la forma (a,b,c,d), donde a es el nombre de la persona, b su actividad, c su fecha de nacimiento y d la de su fallecimiento. Un ejemplo es la siguiente que usaremos a lo largo de este ejercicio,

   personas :: [(String,String,Int,Int)]
   personas = [("Cervantes","Literatura",1547,1616),
               ("Velazquez","Pintura",1599,1660),
               ("Picasso","Pintura",1881,1973),
               ("Beethoven","Musica",1770,1823),
               ("Poincare","Ciencia",1854,1912),
               ("Quevedo","Literatura",1580,1654),
               ("Goya","Pintura",1746,1828),
               ("Einstein","Ciencia",1879,1955),
               ("Mozart","Musica",1756,1791),
               ("Botticelli","Pintura",1445,1510),
               ("Borromini","Arquitectura",1599,1667),
               ("Bach","Musica",1685,1750)]

Definir las funciones

   nombres   :: [(String,String,Int,Int)] -> [String]
   musicos   :: [(String,String,Int,Int)] -> [String]
   seleccion :: [(String,String,Int,Int)] -> String -> [String]
   musicos'  :: [(String,String,Int,Int)] -> [String]
   vivas     :: [(String,String,Int,Int)] -> Int -> [String]

tales que

  • nombres bd es la lista de los nombres de las personas de la base de datos bd. Por ejemplo,
     λ> nombres personas
     ["Cervantes","Velazquez","Picasso","Beethoven","Poincare",
      "Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",
      "Bach"]
  • musicos bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,
     musicos personas  ==  ["Beethoven","Mozart","Bach"]
  • seleccion bd m es la lista de los nombres de las personas de la base de datos bd cuya actividad es m. Por ejemplo,
     λ> seleccion personas "Pintura"
     ["Velazquez","Picasso","Goya","Botticelli"]
     λ> seleccion personas "Musica"
     ["Beethoven","Mozart","Bach"]
  • musicos' bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,
     musicos' personas  ==  ["Beethoven","Mozart","Bach"]
  • vivas bd a es la lista de los nombres de las personas de la base de datos bd que estaban vivas en el año a. Por ejemplo,
     λ> vivas personas 1600
     ["Cervantes","Velazquez","Quevedo","Borromini"]

Leer más…

Representación densa de polinomios

Definiciones por comprensión

Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio \(6x^4-5x^2+4x-7\) se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].

Definir la función

   densa :: [Int] -> [(Int,Int)]

tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,

   densa [6,0,-5,4,-7]  ==  [(4,6),(2,-5),(1,4),(0,-7)]
   densa [6,0,0,3,0,4]  ==  [(5,6),(2,3),(0,4)]
   densa [0]            ==  [(0,0)]

Leer más…

Suma elementos consecutivos

Definiciones por comprensión

Definir la función

   sumaConsecutivos :: [Integer] -> [Integer]

tal que sumaConsecutivos xs es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,

   sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
   sumaConsecutivos [3]        ==  []
   last (sumaConsecutivos [1..10^8])  ==  199999999

Leer más…

Producto escalar

Definiciones por comprensión

El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.

Definir la función

   productoEscalar :: [Integer] -> [Integer] -> Integer

tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,

   productoEscalar [1,2,3] [4,5,6]  ==  32

Leer más…

Ternas pitagóricas con suma dada

Definiciones por comprensión

Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

   ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

   ternasPitagoricas 12     == [(3,4,5)]
   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Leer más…

Ternas pitagórica

Definiciones por comprensión

Una terna (x,y,z) de enteros positivos es pitagórica si x² + y² = z² y x < y < z.

Definir la función

   pitagoricas :: Int -> [(Int,Int,Int)]

tal que pitagoricas n es la lista de todas las ternas pitagóricas cuyas componentes están entre 1 y n. Por ejemplo,

   pitagoricas 10  ==  [(3,4,5),(6,8,10)]
   pitagoricas 15  ==  [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]

Leer más…

Cálculo del número π mediante la fórmula de Leibniz

Definiciones por comprensión

El número π puede calcularse con la fórmula de Leibniz

   π/4 = 1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1) + ...

Definir las funciones

   calculaPi :: Int -> Double
   errorPi   :: Double -> Int

tales que

  • calculaPi n es la aproximación del número π calculada mediante la expresión
     4*(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1))

Por ejemplo,

     calculaPi 3    ==  2.8952380952380956
     calculaPi 300  ==  3.1449149035588526
  • errorPi x es el menor número de términos de la serie necesarios para obtener pi con un error menor que x. Por ejemplo,
     errorPi 0.1    ==    9
     errorPi 0.01   ==   99
     errorPi 0.001  ==  999

Leer más…

Aproximación al límite de sen(x)/x cuando x tiende a cero

Definiciones por comprensión

El limite de sen(x)/x, cuando x tiende a cero, se puede calcular como el límite de la sucesión sen(1/n)/(1/n), cuando n tiende a infinito.

Definir las funciones

   aproxLimSeno :: Int -> [Double]
   errorLimSeno :: Double -> Int

tales que

  • aproxLimSeno n es la lista de los n primeros términos de la sucesión sen(1/m)/(1/m). Por ejemplo,
     aproxLimSeno 1 == [0.8414709848078965]
     aproxLimSeno 2 == [0.8414709848078965,0.958851077208406]
  • errorLimSeno x es el menor número de términos de la sucesión sen(1/m)/(1/m) necesarios para obtener su límite con un error menor que x. Por ejemplo,
     errorLimSeno 0.1     ==   2
     errorLimSeno 0.01    ==   5
     errorLimSeno 0.001   ==  13
     errorLimSeno 0.0001  ==  41

Leer más…

Aproximación del número e

Definiciones por comprensión

El número e se define como el límite de la sucesión [latex]\left(1+\dfrac{1}{n}\right)^n[/latex].

Definir las funciones

   aproxE      :: Int -> [Double]
   errorAproxE :: Double -> Int

tales que

  • aproxE k es la lista de los k primeros términos de la sucesión. Por ejemplo,
     aproxE 4 == [2.0,2.25,2.37037037037037,2.44140625]
     last (aproxE (7*10^7))  ==  2.7182818287372563
  • errorE x es el menor número de términos de la sucesión necesarios para obtener su límite con un error menor que x. Por ejemplo,
     errorAproxE 0.1    ==  13
     errorAproxE 0.01   ==  135
     errorAproxE 0.001  ==  1359

Leer más…

Puntos en el círculo

Definiciones por comprensión

En el círculo de radio 2 hay 6 puntos cuyas coordenadas son puntos naturales:

   (0,0),(0,1),(0,2),(1,0),(1,1),(2,0)

y en de radio 3 hay 11:

   (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0)

Definir la función

   circulo :: Int -> Int

tal que circulo n es el la cantidad de pares de números naturales (x,y) que se encuentran en el círculo de radio n. Por ejemplo,

   circulo 1    ==  3
   circulo 2    ==  6
   circulo 3    ==  11
   circulo 4    ==  17
   circulo 100  ==  7955

Leer más…

Suma de múltiplos de 3 ó 5

Definiciones por comprensión

Definir la función

   euler1 :: Integer -> Integer

tal que euler1 n es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

   euler1 10      == 23
   euler1 (10^2)  == 2318
   euler1 (10^3)  == 233168
   euler1 (10^4)  == 23331668
   euler1 (10^5)  == 2333316668
   euler1 (10^10) == 23333333331666666668
   euler1 (10^20) == 2333333333333333333316666666666666666668
   euler1 (10^30) == 233333333333333333333333333333166666666666666666666666666668

Nota: Este ejercicio está basado en el problema 1 del Proyecto Euler

Leer más…

Números abundantes menores o iguales que n

Definiciones por comprensión

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numerosAbundantesMenores :: Integer -> [Integer]

tal que numerosAbundantesMenores n es la lista de números abundantes menores o iguales que n. Por ejemplo,

   numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
   numerosAbundantesMenores 48  ==  [12,18,20,24,30,36,40,42,48]
   length (numerosAbundantesMenores (10^6)) ==  247545

Leer más…

Números abundantes

Definiciones por comprensión

Un número natural n se denomina abundante si es menor que la suma de sus divisores propios. Por ejemplo, 12 es abundante ya que la suma de sus divisores propios es 16 (= 1 + 2 + 3 + 4 + 6), pero 5 y 28 no lo son.

Definir la función

   numeroAbundante :: Int -> Bool

tal que numeroAbundante n se verifica si n es un número abundante. Por ejemplo,

   numeroAbundante 5  == False
   numeroAbundante 12 == True
   numeroAbundante 28 == False
   numeroAbundante 30 == True
   numeroAbundante 100000000  ==  True
   numeroAbundante 100000001  ==  False

Leer más…

Números perfectos

Definiciones por comprensión

Un números entero positivo es perfecto es igual a la suma de sus divisores, excluyendo el propio número. Por ejemplo, 6 es un número perfecto porque sus divisores propios son 1, 2 y 3; y 6 = 1 + 2 + 3.

Definir la función

   perfectos :: Integer -> [Integer]

tal que perfectos n es la lista de todos los números perfectos menores o iguales que n. Por ejemplo,

   perfectos 500     ==  [6,28,496]
   perfectos (10^5)  ==  [6,28,496,8128]

Leer más…

Suma de divisores

Definiciones por comprensión

Definir la función

   sumaDivisores :: Integer -> Integer

tal que sumaDivisores x es la suma de los divisores de x. Por ejemplo,

   sumaDivisores 12                 ==  28
   sumaDivisores 25                 ==  31
   sumaDivisores (product [1..25])  ==  93383273455325195473152000
   length (show (sumaDivisores (product [1..30000])))  ==  121289
   maximum (map sumaDivisores [1..2*10^6])             ==  8851392

Leer más…

Triángulo aritmético

Definiciones por comprensión

Los triángulos aritméticos se forman como sigue

    1
    2  3
    4  5  6
    7  8  9 10
   11 12 13 14 15
   16 17 18 19 20 21

Definir las funciones

   linea     :: Integer -> [Integer]
   triangulo :: Integer -> [[Integer]]

tales que

  • linea n es la línea n-ésima de los triángulos aritméticos. Por ejemplo,
     linea 4  ==  [7,8,9,10]
     linea 5  ==  [11,12,13,14,15]
     head (linea (10^20)) == 4999999999999999999950000000000000000001
  • triangulo n es el triángulo aritmético de altura n. Por ejemplo,
     triangulo 3  ==  [[1],[2,3],[4,5,6]]
     triangulo 4  ==  [[1],[2,3],[4,5,6],[7,8,9,10]]

Leer más…

Números libres de cuadrados

Definiciones por comprensión

Un número es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

tal que libreDeCuadrados x se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70  ==  True
   libreDeCuadrados 40  ==  False
   libreDeCuadrados (product (take 30000 primes))  ==  True

Leer más…

Divisores primos

Definiciones por comprensión

Definir la función

   divisoresPrimos :: Integer -> [Integer]

tal que divisoresPrimos x es la lista de los divisores primos de x. Por ejemplo,

   divisoresPrimos 40 == [2,5]
   divisoresPrimos 70 == [2,5,7]
   length (divisoresPrimos (product [1..20000])) == 2262

Leer más…

Divisores de un número

Definiciones por comprensión

Definir la función

   divisores :: Integer -> [Integer]

tal que divisores n es la lista de los divisores de n. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

Leer más…

Unión conjuntista de listas

Definiciones por comprensión

Definir la función

   union :: Ord a => [a] -> [a] -> [a]

tal que union xs ys es la unión de las listas, sin elementos repetidos, xs e ys. Por ejemplo,

   union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]

Comprobar con QuickCheck que la unión es conmutativa.

Leer más…

Igualdad de conjuntos

Definiciones por comprensión

Definir la función

   iguales :: Ord a => [a] -> [a] -> Bool

tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. Por ejemplo,

   iguales [3,2,3] [2,3]    ==  True
   iguales [3,2,3] [2,3,2]  ==  True
   iguales [3,2,3] [2,3,4]  ==  False
   iguales [2,3] [4,5]      ==  False

Leer más…

Números racionales

Definiciones elementales de funciones

Los números racionales pueden representarse mediante pares de números enteros. Por ejemplo, el número 2/5 puede representarse mediante el par (2,5).

Definir las funciones

   formaReducida    :: (Int,Int) -> (Int,Int)
   sumaRacional     :: (Int,Int) -> (Int,Int) -> (Int,Int)
   productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)
   igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool

tales que

  • formaReducida x es la forma reducida del número racional x. Por ejemplo,
     formaReducida (4,10)  ==  (2,5)
     formaReducida (0,5)   ==  (0,1)
  • sumaRacional x y es la suma de los números racionales x e y, expresada en forma reducida. Por ejemplo,
     sumaRacional (2,3) (5,6)  ==  (3,2)
     sumaRacional (3,5) (-3,5) ==  (0,1)
  • productoRacional x y es el producto de los números racionales x e y, expresada en forma reducida. Por ejemplo,
     productoRacional (2,3) (5,6)  ==  (5,9)
  • igualdadRacional x y se verifica si los números racionales x e y son iguales. Por ejemplo,
     igualdadRacional (6,9) (10,15)  ==  True
     igualdadRacional (6,9) (11,15)  ==  False
     igualdadRacional (0,2) (0,-5)   ==  True

Comprobar con QuickCheck la propiedad distributiva del producto racional respecto de la suma.

Leer más…

Intersección de intervalos cerrados

Definiciones elementales de funciones

Los intervalos cerrados se pueden representar mediante una lista de dos números (el primero es el extremo inferior del intervalo y el segundo el superior).

Definir la función

   interseccion :: Ord a => [a] -> [a] -> [a]

tal que (interseccion i1 i2) es la intersección de los intervalos i1 e i2. Por ejemplo,

   interseccion [] [3,5]     ==  []
   interseccion [3,5] []     ==  []
   interseccion [2,4] [6,9]  ==  []
   interseccion [2,6] [6,9]  ==  [6,6]
   interseccion [2,6] [0,9]  ==  [2,6]
   interseccion [2,6] [0,4]  ==  [2,4]
   interseccion [4,6] [0,4]  ==  [4,4]
   interseccion [5,6] [0,4]  ==  []

Comprobar con QuickCheck que la intersección de intervalos es conmutativa.

Leer más…

Fórmula de Herón para el área de un triángulo

Definiciones elementales de funciones

La fórmula de Herón, descubierta por Herón de Alejandría, dice que el área de un triángulo cuyo lados miden a, b y c es la raíz cuadrada de s(s-a)(s-b)(s-c) donde s es el semiperímetro

   s = (a+b+c)/2

Definir la función

   area :: Double -> Double -> Double -> Double

tal que (area a b c) es el área del triángulo de lados a, b y c. Por ejemplo,

   area 3 4 5  ==  6.0

Leer más…

Raíces de la ecuación de segundo grado

Definiciones elementales de funciones

Definir la función

   raices :: Double -> Double -> Double -> [Double]

tal que (raices a b c) es la lista de las raíces reales de la ecuación [latex]ax^2 + bx + c = 0[/latex]. Por ejemplo,

   raices 1 3 2    ==  [-1.0,-2.0]
   raices 1 (-2) 1 ==  [1.0,1.0]
   raices 1 0 1    ==  []

Comprobar con QuickCheck que la suma de las raíces de la ecuación [latex]ax^2 + bx + c = 0[/latex] (con [latex]a[/latex] no nulo) es [latex]\dfrac{-b}{a}[/latex] y su producto es [latex]\dfrac{c}{a}[/latex].

Leer más…

Permutación cíclica

Definiciones elementales de funciones

Definir la función

   ciclo :: [a] -> [a]

tal que (ciclo xs) es la lista obtenida permutando cíclicamente los elementos de la lista xs, pasando el último elemento al principio de la lista. Por ejemplo,

   ciclo [2,5,7,9]  == [9,2,5,7]
   ciclo []         == []
   ciclo [2]        == [2]

Comprobar que la longitud es un invariante de la función ciclo; es decir, la longitud de (ciclo xs) es la misma que la de xs.

Leer más…

Distancia entre dos puntos

Definiciones elementales de funciones

Definir la función

   distancia :: (Double,Double) -> (Double,Double) -> Double

tal que (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por ejemplo,

   distancia (1,2) (4,6)  ==  5.0

Comprobar con QuickCheck que se verifica la propiedad triangular de la distancia; es decir, dados tres puntos p1, p2 y p3, la distancia de p1 a p3 es menor o igual que la suma de la distancia de p1 a p2 y la de p2 a p3.

Leer más…

Mayor rectángulo

Definiciones elementales de funciones

Las dimensiones de los rectángulos puede representarse por pares; por ejemplo, (5,3) representa a un rectángulo de base 5 y altura 3.

Definir la función

   mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)

tal que (mayorRectangulo r1 r2) es el rectángulo de mayor área entre r1 y r2. Por ejemplo,

   mayorRectangulo (4,6) (3,7)  ==  (4,6)
   mayorRectangulo (4,6) (3,8)  ==  (4,6)
   mayorRectangulo (4,6) (3,9)  ==  (3,9)

Leer más…

Disyunción excluyente

Definiciones elementales de funciones

La disyunción excluyente de dos fórmulas se verifica si una es verdadera y la otra es falsa. Su tabla de verdad es

   x     | y     | xor x y
   ------+-------+---------
   True  | True  | False
   True  | False | True
   False | True  | True
   False | False | False

Definir la función

   xor :: Bool -> Bool -> Bool

tal que (xor x y) es la disyunción excluyente de x e y. Por ejemplo,

   xor True  True  == False
   xor True  False == True
   xor False True  == True
   xor False False == False

Leer más…

División segura

Definiciones elementales de funciones

Definir la función

   divisionSegura :: Double -> Double -> Double

tal que (divisionSegura x y) es x/y si y no es cero y 9999 en caso contrario. Por ejemplo,

   divisionSegura 7 2  ==  3.5
   divisionSegura 7 0  ==  9999.0

Leer más…

Tres diferentes

Definiciones elementales de funciones

Definir la función

   tresDiferentes :: Int -> Int -> Int -> Bool

tal que (tresDiferentes x y z) se verifica si los elementos x, y y z son distintos. Por ejemplo,

   tresDiferentes 3 5 2  ==  True
   tresDiferentes 3 5 3  ==  False

Leer más…

Tres iguales

Definiciones elementales de funciones

Definir la función

   tresIguales :: Int -> Int -> Int -> Bool

tal que (tresIguales x y z) se verifica si los elementos x, y y z son iguales. Por ejemplo,

   tresIguales 4 4 4  ==  True
   tresIguales 4 3 4  ==  False

Leer más…

Elemento mediano

Definiciones elementales de funciones

Definir la función

   mediano :: Int -> Int -> Int -> Int

tal que (mediano x y z) es el número mediano de los tres números x, y y z. Por ejemplo,

   mediano 3 2 5  ==  3
   mediano 2 4 5  ==  4
   mediano 2 6 5  ==  5
   mediano 2 6 6  ==  6

Leer más…

Primeros y últimos elementos

Definiciones elementales de funciones

Definir la función

   extremos :: Int -> [a] -> [a]

tal que (extremos n xs) es la lista formada por los n primeros elementos de xs y los n finales elementos de xs. Por ejemplo,

   extremos 3 [2,6,7,1,2,4,5,8,9,2,3]  ==  [2,6,7,9,2,3]

Leer más…

Segmento de una lista

Definiciones elementales de funciones

Definir la función

   segmento :: Int -> Int -> [a] -> [a]

tal que (segmento m n xs) es la lista de los elementos de xs comprendidos entre las posiciones m y n. Por ejemplo,

   segmento 3 4 [3,4,1,2,7,9,0]  ==  [1,2]
   segmento 3 5 [3,4,1,2,7,9,0]  ==  [1,2,7]
   segmento 5 3 [3,4,1,2,7,9,0]  ==  []

Leer más…