Tengo que reemplazar todos los elementos en una lista por el número de apariciones de ese elemento, como si tuviera "Taylor Swift" el resultado será [1,1,1,1,1,1,1,1,1,1 , 1,1].

Ya hice el código para contar las ocurrencias, solo sé cómo reemplazar todos los elementos por el número de ocurrencias que ya probé:

ocurr :: [Char] -> Char -> Int
ocurr xs x = length(filter (x==) xs)

frequencias :: [Char] -> [Char] 
frequencias "" = []
frequencias xs = [ ocurr xs y| y <- xs]

Y

ocurr :: [Char] -> Char -> Int
ocurr xs x = length(filter (x==) xs)

frequencias :: [Char] -> [Char] 
frequencias "" = []
frequencias xs = [x | y <- xs x = ocurr xs x]

Pero nada de esto funciona ... ¿alguien puede ayudarme por favor?

0
one user 27 sep. 2020 a las 20:01

3 respuestas

La mejor respuesta

Esto no funcionará ya que el tipo de retorno que especificas en frequencias es [Char], mientras que las frecuencias son, según tu función occurr, Int s. La cláusula especial para una lista vacía no es necesaria (aunque no es incorrecta). Por tanto, puede trabajar con:

frequencias :: [Char] -> [Int]
frequencias xs = [ ocurr xs y | y <- xs ]

También puede hacer uso de un simple map :: (a -> b) -> [a] -> [b] :

frequencias :: [Char] -> [Int]
frequencias xs = map (ocurr xs) xs

Esto nos da así:

Prelude> frequencias "Taylor Swift"
[1,1,1,1,1,1,1,1,1,1,1,1]
Prelude> frequencias "taylor swift"
[2,1,1,1,1,1,1,1,1,1,1,2]
5
Willem Van Onsem 27 sep. 2020 a las 17:06

Todo este filtrado podría resultar caro. Aquí tienes una solución fácil:

import qualified Data.IntMap.Strict as M
import Data.IntMap.Strict (IntMap)
import Data.Char (ord)
import Control.DeepSeq (force)
import Data.List (foldl')

frequencias :: [Char] -> [Int]
frequencias xs = force res
  where
   freq_map :: IntMap Int
   freq_map = foldl' go M.empty xs
   go fm c = M.insertWith (+) (ord c) 1 fm
   res = map (\c -> case M.lookup (ord c) freq_map of
          Just freq -> freq
          Nothing -> error "impossible") xs

El force asegura que el mapa de frecuencias será recolectado como basura rápidamente; no es necesario o probablemente deseable si el resultado se consume rápidamente.

Una forma alternativa de evitar una pérdida de memoria es eliminar las claves que ya no son necesarias:

import qualified Data.IntMap.Strict as M
import Data.IntMap.Strict (IntMap)
import Data.Char (ord)
import Data.List (foldl')

data Blob = Blob
  { total_count :: !Int
  , remaining :: !Int
  }

frequencias :: [Char] -> [Int]
frequencias xs0 = finish xs0 freq_map0
  where
    freq_map0 :: IntMap Blob
    freq_map0 = foldl' go M.empty xs0
    go fm c = M.alter f (ord c) fm
      where
        f Nothing = Just (Blob 1 1)
        f (Just (Blob x _)) = Just (Blob (x + 1) (x + 1))
    finish [] _ = []
    finish (c : cs) freq_map = case M.updateLookupWithKey (\_ (Blob tot remn) ->
      if remn == 1
      then Nothing
      else Just (Blob tot (remn - 1))) (ord c) freq_map of
        (Nothing, _) -> error "Whoopsy"
        (Just (Blob tot _), freq_map') -> tot : finish cs freq_map'
2
dfeuer 30 sep. 2020 a las 05:38

Para comparar con la respuesta de @ dfeuer, aquí hay un par de enfoques de baja tecnología.

  1. Enfoque de fuerza bruta. Esto tiene una complejidad de tiempo O(n^2), para la longitud de la lista de entrada n.

     occurrences :: Eq a => [a] -> [Int]
     occurrences xss = map (\ x -> count (== x) xss) xss
    
     count :: (a -> Bool) -> [a] -> Int
     count _ [] = 0
     count p (x : xs) | p x       = 1 + count p xs
                      | otherwise =     count p xs
    

(Usé nombres en inglés para mis funciones ;-) count hace el trabajo de ocurr de O.P. Pero cambié el orden de los argumentos para que se parezca más a Prelude.filter. ocurr es un poco ineficiente porque filter crea un resultado intermedio para ser el argumento de length. No necesitamos construir eso: simplemente contar cuántos elementos cumplen con el predicado (== x).

(Estoy bastante sorprendida de que no haya un Prelude.count ni Data.List.count). (Estoy bastante sorprendido de que no haya un Prelude.count ni Data.List.count).

Esto es ineficiente porque atraviesa la lista para cada elemento, incluso si ya 'conoce' el recuento del valor de ese elemento, es decir, porque ya ha cumplido con ese elemento anteriormente en la lista.

OTOH, si una gran proporción de los elementos ocurre solo una vez, evita la sobrecarga de construir algún tipo de estructura de búsqueda.

  1. Aquí hay una versión que usa una caché intermedia, pero solo para los elementos que se sabe que ocurren más de una vez. ¿A alguien le gustaría adivinar cuál es su complejidad temporal?

     data Cache3 a = TheList3 [a] | Cached3 a Int (Cache3 a)
    
     count3 :: (a -> Bool) -> Cache3 a -> (Int, Bool)
                         -- return both the count and whether it was cached
     count3 p (TheList3 xss) = ( count p xss, False)    -- reuse count from sol'n 1
     count3 p (Cached3 x c xs) | p x = (c, True)
                               | otherwise = count3 p xs
    
     -- don't cache if count = 1: we've just counted its only appearance so won't need it again
    
     occurrences3 :: Eq a => [a] -> [Int]
     occurrences3 xss = go (TheList3 xss) xss  where
       go _ [] = []
       go cc (x: xs) = c: go (if cached || c < 2 then cc else ( Cached3 x c cc)) xs  where
         (c, cached) = count3 (== x) cc
    
0
AntC 30 sep. 2020 a las 04:07