Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

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

Por ejemplo, el árbol

      "B"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "C" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C"))

Definir la función

enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

λ> enumeraArbol ej1
N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))

Gráficamente,

      3
     / \
    /   \
   /     \
  1       5
 / \     / \
0   2   4   6

Números triangulares con n cifras distintas

José A. Alonso

27-05-2014 (actualizado 29-08-2025)

Misceláneas

Los números triangulares se forman como sigue

*     *      *
     * *    * *
           * * *
1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Definir la función

triangularesConCifras :: Int -> [Integer]

tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,

take 6 (triangularesConCifras 1)   ==  [1,3,6,55,66,666]
take 6 (triangularesConCifras 2)   ==  [10,15,21,28,36,45]
take 6 (triangularesConCifras 3)   ==  [105,120,136,153,190,210]
take 5 (triangularesConCifras 4)   ==  [1035,1275,1326,1378,1485]
take 2 (triangularesConCifras 10)  ==  [1062489753,1239845706]

Trenzado de listas

José A. Alonso

26-05-2014 (actualizado 28-08-2025)

Misceláneas

Definir la función

trenza :: [a] -> [a] -> [a]

tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,

trenza [5,1] [2,7,4]             ==  [5,2,1,7]
trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]
trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]
take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]

Biparticiones de una lista

José A. Alonso

23-05-2014 (actualizado 28-08-2025)

Misceláneas

Definir la función

biparticiones :: [a] -> [([a],[a])]

tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. Por ejemplo,

λ> biparticiones [3,2,5]
[([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])]
λ> biparticiones "Roma"
[("","Roma"),("R","oma"),("Ro","ma"),("Rom","a"),("Roma","")]

Mayor producto de las ramas de un árbol

José A. Alonso

22-05-2014 (actualizado 28-08-2025)

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles

  1              3
 / \            /|\
2   3          / | \
    |         5  4  7
    4         |     /\
              6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

λ> mayorProducto (N 1 [N 2 [], N  3 []])
3
λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
12
λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
12
λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
90
λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
0
λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
λ> mayorProducto a
84

Número de pares de elementos adyacentes iguales en una matriz

José A. Alonso

21-05-2014 (actualizado 28-08-2025)

Misceláneas

Una matriz se puede representar mediante una lista de listas. Por ejemplo, la matriz

|2 1 5|
|4 3 7|

se puede representar mediante la lista

[[2,1,5],[4,3,7]]

Definir la función

numeroParesAdyacentesIguales :: Eq a => [[a]] -> Int

tal que (numeroParesAdyacentesIguales xss) es el número de pares de elementos consecutivos (en la misma fila o columna) iguales de la matriz xss. Por ejemplo,

numeroParesAdyacentesIguales [[0,1],[0,2]]              ==  1
numeroParesAdyacentesIguales [[0,0],[1,2]]              ==  1
numeroParesAdyacentesIguales [[0,1],[0,0]]              ==  2
numeroParesAdyacentesIguales [[1,2],[1,4],[4,4]]        ==  3
numeroParesAdyacentesIguales ["ab","aa"]                ==  2
numeroParesAdyacentesIguales [[0,0,0],[0,0,0],[0,0,0]]  ==  12
numeroParesAdyacentesIguales [[0,0,0],[0,1,0],[0,0,0]]  ==  8

Elemento más repetido de manera consecutiva

José A. Alonso

20-05-2014 (actualizado 28-08-2025)

Misceláneas

Definir la función

masRepetido :: Ord a => [a] -> (a,Int)

tal que (masRepetido xs) es el elemento de xs que aparece más veces de manera consecutiva en la lista junto con el número de sus apariciones consecutivas; en caso de empate, se devuelve el mayor de dichos elementos. Por ejemplo,

masRepetido [1,1,4,4,1]  ==  (4,2)
masRepetido [4,4,1,1,5]  ==  (4,2)
masRepetido "aadda"      ==  ('d',2)
masRepetido "ddaab"      ==  ('d',2)
masRepetido (show (product [1..5*10^4]))  ==  ('0',12499)

Regiones determinadas por n rectas del plano

José A. Alonso

19-05-2014 (actualizado 28-08-2015)

Misceláneas

En los siguientes dibujos se observa que el número máximo de regiones en el plano generadas con 1, 2 ó 3 líneas son 2, 4 ó 7, respectivamente.

                   \  |
                    \5|
                     \|
                      \
                      |\
                      | \
            |         |  \
 1        1 | 3     1 | 3 \  6
------   ---|---   ---|----\---
 2        2 | 4     2 | 4   \ 7
            |         |      \

Definir la función

regiones :: Integer -> Integer

tal que (regiones n) es el número máximo de regiones en el plano generadas con n líneas. Por ejemplo,

regiones 1     ==  2
regiones 2     ==  4
regiones 3     ==  7
regiones 100   ==  5051
regiones 1000  ==  500501
regiones 10000 ==  50005001
length (show (regiones (10^(10^5)))) ==  200000
length (show (regiones (10^(10^6)))) ==  2000000
length (show (regiones (10^(10^7)))) ==  20000000

Ampliación de matrices por columnas

José A. Alonso

16-05-2014 (actualizado 28-08-2025)

Misceláneas

Las matrices enteras se pueden representar mediante tablas con índices enteros:

type Matriz = Array (Int,Int) Int

Definir la función

ampliaColumnas :: Matriz -> Matriz -> Matriz

tal que (ampliaColumnas p q) es la matriz construida añadiendo las columnas de la matriz q a continuación de las de p (se supone que tienen el mismo número de filas). Por ejemplo, si p y q representa las dos primeras matrices, entonces (ampliaColumnas p q) es la tercera

|0 1|    |4 5 6|    |0 1 4 5 6|
|2 3|    |7 8 9|    |2 3 7 8 9|

En Haskell, se definen las dos primeras matrices se definen por

ej1 = listArray ((1,1),(2,2)) [0..3]
ej2 = listArray ((1,1),(2,3)) [4..9]

y el cálculo de la tercera es

λ> ampliaColumnas ej1 ej2
array ((1,1),(2,5)) [((1,1),0),((1,2),1),((1,3),4),((1,4),5),((1,5),6),
                     ((2,1),2),((2,2),3),((2,3),7),((2,4),8),((2,5),9)]
λ> elems (ampliaColumnas ej1 ej2)
[0,1,4,5,6,2,3,7,8,9]

Emparejamiento binario

José A. Alonso

15-05-2014 (actualizado 28-08-2025)

Misceláneas

Definir la función

zipBinario :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (zipBinario fs xs ys) es la lista obtenida aplicando cada una de las operaciones binarias de fs a los correspondientes elementos de xs e ys. Por ejemplo,

zipBinario [(+), (*), (*)] [2,2,2] [4,4,4]    == [6,8,8]
zipBinario [(+)] [2,2,2] [4,4,4]              == [6]
zipBinario [(<), (==), (==)] "coloca" "lobo"  == [True,True,False]

Exercitium

Enumeración de árboles binarios

Números triangulares con n cifras distintas

Trenzado de listas

Biparticiones de una lista

Mayor producto de las ramas de un árbol

Número de pares de elementos adyacentes iguales en una matriz

Elemento más repetido de manera consecutiva

Regiones determinadas por n rectas del plano

Ampliación de matrices por columnas

Emparejamiento binario