Menu Close

Etiqueta: map

Ramas de un árbol

Enunciado

-- 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 
--    ramas :: Arbol b -> [[b]]
-- tal que (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    ramas ej1  ==  [[1,2],[1,3,4]]
--    ramas ej2  ==  [[3,5,6],[3,4],[3,7,2],[3,7,1]]

Soluciones

data Arbol a = N a [Arbol a]
               deriving Show
 
-- 1ª solución:
ramas1 :: Arbol b -> [[b]]
ramas1 (N x []) = [[x]]
ramas1 (N x as) = [x : xs | a <- as, xs <- ramas1 a]
 
-- 2ª solución:
ramas2 :: Arbol b -> [[b]]
ramas2 (N x []) = [[x]]
ramas2 (N x as) = concat (map (map (x:)) (map ramas2 as))
 
-- 3ª solución:
ramas3 :: Arbol b -> [[b]]
ramas3 (N x []) = [[x]]
ramas3 (N x as) = concatMap (map (x:)) (map ramas3 as)

Anagramas

Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, mora y roma son anagramas de amor.

Enunciado

-- Definir la función
--    anagramas :: String -> [String] -> [String]
-- tal que (anagramas x ys) es la lista de los elementos de ys que son
-- anagramas de x. Por ejemplo,
--    anagramas "amor" ["Roma","mola","loma","moRa"] ==  ["Roma","moRa"]

Soluciones

import Data.List
import Data.Char
 
-- 1ª definición (por recursión):
anagramas :: String -> [String] -> [String]
anagramas x [] = []
anagramas x (y:ys) | sonAnagramas x y = y : anagramas x ys
                   | otherwise        = anagramas x ys
 
-- (sonAnagramas xs ys) se verifica si xs e ys son anagramas. Por
-- ejemplo,
--    sonAnagramas "amor" "Roma"  ==  True
--    sonAnagramas "amor" "mola"  ==  False
sonAnagramas :: String -> String -> Bool
sonAnagramas xs ys = 
    sort (map toLower xs) == sort (map toLower ys) 
 
-- 2ª definición de sonAnagramas
sonAnagramas2 :: String -> String -> Bool
sonAnagramas2 xs ys = 
    (sort . map toLower) xs == (sort . map toLower) ys 
 
-- 2ª definición (por comprensión)
anagramas2 :: String -> [String] -> [String]
anagramas2 x ys = [y | y <- ys, sonAnagramas x y]
 
-- 3ª definición (con filter y sin el 2ª argumento)
anagramas3 :: String -> [String] -> [String]
anagramas3 x = filter (`sonAnagramas` x)

Ordenación por máximos

Enunciado

-- Definir la función 
--    ordenadosPorMaximo :: Ord a => [[a]] -> [[a]]
-- tal que (ordenadosPorMaximo xss) es la lista de los elementos de xss
-- ordenada por sus máximos. Por ejemplo,
--    ghci> ordenadosPorMaximo [[3,2],[6,7,5],[1,4]]
--    [[3,2],[1,4],[6,7,5]]
--    ghci> ordenadosPorMaximo ["este","es","el","primero"]
--    ["el","primero","es","este"]

Soluciones

import Data.List
 
-- 1ª definición (por compresión)
ordenadosPorMaximo :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo xss =
    [xs | (_,xs) <- sort [(maximum xs,xs) | xs <- xss]]
 
-- 2ª definición (con map)
ordenadosPorMaximo2 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo2 xss =
    map snd (sort [(maximum xs,xs) | xs <- xss])

Iguales al siguiente

Enunciado

-- Definir la función
--    igualesAlSiguiente :: Eq a => [a] -> [a]
-- tal que (igualesAlSiguiente xs) es la lista de los elementos de xs
-- que son iguales a su siguiente. Por ejemplo,
--    igualesAlSiguiente [1,2,2,2,3,3,4]  ==  [2,2,3]
--    igualesAlSiguiente [1..10]          ==  []

Soluciones

import Data.List (group)
 
-- 1ª definición (por comprensión):
igualesAlSiguiente :: Eq a => [a] -> [a]
igualesAlSiguiente xs =
    [x | (x,y) <- zip xs (tail xs), x == y]
 
-- 2ª definición (por recursión):
igualesAlSiguiente2 :: Eq a => [a] -> [a]
igualesAlSiguiente2 (x:y:zs) | x == y    = x : igualesAlSiguiente2 (y:zs)
                             | otherwise = igualesAlSiguiente2 (y:zs)
igualesAlSiguiente2 _                    = []
 
-- 3ª definición (con concat y comprensión):
igualesAlSiguiente3 :: Eq a => [a] -> [a]
igualesAlSiguiente3 xs = concat [ys | (_:ys) <- group xs]
 
-- 4ª definición (con concat y map):
igualesAlSiguiente4 :: Eq a => [a] -> [a]
igualesAlSiguiente4 xs = concat (map tail (group xs))