Elementos más frecuentes

4 Comentarios

1. Haskell

   import Data.List (sort, group) masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes n xs = take n (reverse(sort [(length ys,head ys)|ys<- group (sort xs)]))

   1 2 3 4

   import Data.List (sort, group)   masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes n xs = take n (reverse(sort [(length ys,head ys)|ys<- group (sort xs)]))

   Responder

2. Para que usar una clara lista por comprehension cuando uno puede liarla usando aplicativos :-P :

   Haskell

   import Data.List (sort, group) import Control.Applicative ((<*>), (<$>)) masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes i = take i . reverse . sort . (zip . map length <*> map head) . group . sort

   1 2 3 4 5

   import Data.List (sort, group) import Control.Applicative ((<*>), (<$>))   masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes i = take i . reverse . sort . (zip . map length <*> map head) . group . sort

   o (igual mas claro todavia)

   Haskell

   masFrecuentes i = take i . reverse . sort . (map $ (,) <$> length <*> head) . group . sort

   1	masFrecuentes i = take i . reverse . sort . (map $ (,) <$> length <*> head) . group . sort

   Responder

   1. Algunos comentarios sobre las funciones aplicativas que aún no se han estudiado en I1M2014.

      En la primera definición se usa el operador (<*>). Su significado se explica con el siguiente ejemplo,

      Haskell

      (zip <*> tail) [2,3,5] = zip [2,3,5] (tail [2,3,5]) = zip [2,3,5] [3,5] = [(2,3),(3,5)]

      1 2 3 4

      (zip <*> tail) [2,3,5] = zip [2,3,5] (tail [2,3,5]) = zip [2,3,5] [3,5] = [(2,3),(3,5)]

      En general,

      Haskell

      (f <*> g) xs

      1	(f <*> g) xs

      es equivalente a

      Haskell

      f xs (g xs)

      1	f xs (g xs)

      El significado de (zip . map length <*> map head) se puede apreciar con el siguiente cálculo

      Haskell

      (zip . map length <*> map head) ["aa","bbb"] = ((zip . map length) <*> (map head)) ["aa","bbb"] = (zip . map length) ["aa","bbb"] (map head ["aa","bbb"]) = (zip . map length) ["aa","bbb"] "ab" = zip (map length ["aa","bbb"]) "ab" = zip [2,3] "ab" = [(2,'a'),(3,'b')]

      1 2 3 4 5 6 7

      (zip . map length <*> map head) ["aa","bbb"] = ((zip . map length) <*> (map head)) ["aa","bbb"] = (zip . map length) ["aa","bbb"] (map head ["aa","bbb"]) = (zip . map length) ["aa","bbb"] "ab" = zip (map length ["aa","bbb"]) "ab" = zip [2,3] "ab" = [(2,'a'),(3,'b')]

      En la segunda definición se ha usado el operador (<$>). Su significado se explica con el siguiente ejemplo,

      Haskell

      ((+) <$> length) "abc" 4 = (+) (length "abc") 4 = (+) 3 4 = 3 + 4 = 7

      1 2 3 4 5

      ((+) <$> length) "abc" 4 = (+) (length "abc") 4   = (+) 3 4   = 3 + 4 = 7

      También se ha usado el operador (,) para construir pares. Por ejemplo,

      Haskell

      (,) 3 4 = (3,4)

      1	(,) 3 4 = (3,4)

      El significado de (map $ (,) <$> length <*> head) se puede apreciar con el siguiente cálculo

      Haskell

      (map $ (,) <$> length <*> head) ["aa","bbb"] = [((,) <$> length <*> head) "aa", ((,) <$> length <*> head) "bbb"] = [(((,) <$> length) <*> head) "aa", (((,) <$> length) <*> head) "bbb"] = [((,) <$> length) "aa" (head "aa"), ((,) <$> length) "bbb" (head "bbb")] = [((,) <$> length) "aa" 'a', ((,) <$> length) "bbb" 'b'] = [(,) (length "aa") 'a', (,) (length "bbb") 'b'] = [(,) 2 'a', (,) 3 'b'] = [(2,'a'),(3,'b')]

      1 2 3 4 5 6 7 8

      (map $ (,) <$> length <*> head) ["aa","bbb"] = [((,) <$> length <*> head) "aa", ((,) <$> length <*> head) "bbb"] = [(((,) <$> length) <*> head) "aa", (((,) <$> length) <*> head) "bbb"] = [((,) <$> length) "aa" (head "aa"), ((,) <$> length) "bbb" (head "bbb")] = [((,) <$> length) "aa" 'a', ((,) <$> length) "bbb" 'b'] = [(,) (length "aa") 'a', (,) (length "bbb") 'b'] = [(,) 2 'a', (,) 3 'b'] = [(2,'a'),(3,'b')]

      Responder

3. Un poco lioso pero quería intentarlo sin utilizar librerías extra.

   Haskell

   masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes n xs = take n (elimina (orden xs)) orden :: Eq a => [a] -> [(Int,a)] orden xs = [a | b <- reverse [1..maxlistafrec xs], a <- listafrecuencias xs, fst a == b] maxlistafrec :: Eq a => [a] -> Int maxlistafrec xs = maximum [fst a | a <- listafrecuencias xs] listafrecuencias :: Eq a => [a] -> [(Int,a)] listafrecuencias xs = [(numocu a xs,a) | a <- xs] numocu :: Eq a => a -> [a] -> Int numocu n xs = ocu n xs 0 ocu :: Eq a => a -> [a] -> Int -> Int ocu n [] c = c ocu n (x:xs) c | n == x = ocu n xs (c+1) | otherwise = ocu n xs c elimina :: Eq a => [a] -> [a] elimina [] = [] elimina (x:xs) | elem x xs = elimina xs | otherwise = x : elimina xs

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)] masFrecuentes n xs = take n (elimina (orden xs))   orden :: Eq a => [a] -> [(Int,a)] orden xs = [a | b <- reverse [1..maxlistafrec xs],                 a <- listafrecuencias xs,                 fst a == b]   maxlistafrec :: Eq a => [a] -> Int maxlistafrec xs =     maximum [fst a | a <- listafrecuencias xs] listafrecuencias :: Eq a => [a] -> [(Int,a)] listafrecuencias xs = [(numocu a xs,a) | a <- xs]   numocu :: Eq a => a -> [a] -> Int numocu n xs = ocu n xs 0   ocu :: Eq a => a -> [a] -> Int -> Int ocu n [] c = c ocu n (x:xs) c | n == x  = ocu n xs (c+1)                | otherwise = ocu n xs c   elimina :: Eq a => [a] -> [a] elimina [] = [] elimina (x:xs) | elem x xs = elimina xs                | otherwise = x : elimina xs

   Responder