tuplas - ordenar lista haskell

¿Cómo obtener cada N elemento de una lista infinita en Haskell?

Question

Más específicamente, ¿cómo puedo generar una nueva lista de cada enésimo elemento de una lista infinita existente?

Por ejemplo, si la lista es [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...], obtener cada 3º elemento daría como resultado esta lista [0,0,0, 0,0 ...]

Answer 1

¡La recursión explícita es malvada! Utilice una construcción de biblioteca como mapa, filtro, plegado, escaneo, reproducción, iteración, etc. en su lugar. A menos que haga que el código sea drásticamente más fácil de leer incluso para aquellos au fait con las bibliotecas, entonces solo hará que su código sea menos modular, más detallado y más difícil de razonar.

En serio, las versiones explícitamente recursivas deben ser votadas negativamente para una tarea tan simple como esta. Ahora supongo que debería decir algo constructivo para equilibrar mis carpas.

Prefiero usar un mapa:

cada n xs = mapa (xs !!) [n-1, n-1 + n ..]

en lugar de la comprensión de la lista de ja para que el lector no tenga que preocuparse por lo que soy. Pero de cualquier forma es O (n ^ 2) cuando podría ser O (n), entonces quizás esto sea mejor:

cada n = mapa (!! (n-1)). iterar (soltar n)

Answer 2

Comenzando en el primer elemento:

everyf n [] = []
everyf n as  = head as : everyf n (drop n as)

Comenzando en el enésimo elemento:

every n = everyf n . drop (n-1)

Answer 3

Destruí mi versión de Haskell el otro día, por lo que no se probó, pero el siguiente parece un poco más simple que los otros (aprovecha la coincidencia de patrones y la caída para evitar zip y mod)

everynth n xs = y:(everynth n ys)
         where y:ys = drop (n-1) xs

Answer 4

El compilador o intérprete calculará el tamaño del paso (reste 1 ya que está basado en cero):

f l n = [l !! i | i <- [n-1,n-1+n..]]

El informe Haskell 98: secuencias aritméticas

Answer 5

Esto parece un poco mejor uso de despliegue:

everyNth :: Int -> [a] -> [a]
everyNth n = unfoldr g
  where
    g [] = Nothing
    g xs = let (ys, zs) = splitAt n xs in Just (head ys, zs)

O mejor aún, use Data.List.Spit:

everyNth n = (map head) . chunksOf n

Answer 6

La respuesta de MHarris es genial. Pero me gusta evitar el uso de / , así que aquí está mi golf:

extractEvery n
  = map snd . filter fst
  . zip (cycle (replicate (n-1) False ++ [True]))

Answer 7

Mi solución es:

every :: Int -> [a] -> [[a]]
every _ [] = []
every n list = take n list : (every n $ drop n list)

No uso zip pero no puedo decir sobre sus actuaciones y perfil de memoria.

Answer 8

Mi versión usando drop:

every n xs = case drop (n-1) xs of
              (y:ys) -> y : every n ys
              [] -> []

Editar: esto también funciona para listas finitas. Solo para listas infinitas, la solución de Charles Stewart es un poco más corta.

Answer 9

Muchas respuestas aquí ya usan Data.List.unfoldr, pero quería mostrar una forma interesante de escribir el despliegue un tanto molesto que puede ser útil en otros contextos:

{-# LANGUAGE TupleSections #-}
import Data.List (unfoldr)
import Data.Maybe (listToMaybe)

every n = unfoldr f . drop (n - 1)
    where f xs = (,drop n xs) <$> listToMaybe xs

Cuando la lista es nula, listToMaybe devuelve Nothing , y fmap manera similar será Nothing . Sin embargo, si se produce un Just , entonces se construye la tupla correcta convirtiendo el encabezado de la lista en una tupla del encabezado y el resto de los valores para usar en la siguiente iteración.

Answer 10

No tengo nada para probar esto en el trabajo, pero algo así como:

extractEvery m = map snd . filter (/(x,y) -> (mod x m) == 0) . zip [1..]

debería funcionar incluso en listas infinitas.

(Edición: probado y corregido)

Answer 11

Otra forma de hacerlo:

takeEveryM m lst = [n | (i,n) <- zip [1..] lst, i `mod` m == 0]

Aún otra:

import Data.List

takeEveryMth m = 
  (unfoldr g)  . dr
     where 
       dr = drop (m-1)
       g (x:xs) = Just (x, dr xs)
       g []     = Nothing

Answer 12

Pregunta anterior, pero publicaré lo que se me ocurrió:

everyNth :: [a] -> Int -> [a]
everyNth xs n = [snd x | x <- (zip [1..] xs), fst x `mod` n == 0]

Pongo el argumento de la lista antes de la Int para que pueda curry la función y una lista, luego la asocie a una lista de Int si alguna vez lo necesito.

Answer 13

Solución alternativa para deshacerse de mod :

extractEvery n = map snd . filter ((== n) . fst) . zip (cycle [1..n])

Answer 14

Todas las soluciones que usan zip y así sucesivamente hacen toneladas de asignaciones innecesarias. Como programador funcional, desea adquirir el hábito de no asignar a menos que realmente tenga que hacerlo. La asignación es costosa, y en comparación con la asignación, todo lo demás es gratis. Y la asignación no solo aparece en los "puntos calientes" que encontraría con un generador de perfiles; si no le prestas atención a la asignación, te matará en todas partes .

Ahora estoy de acuerdo con los comentaristas en que la legibilidad es lo más importante . Nadie quiere obtener respuestas incorrectas rápidamente. Pero sucede muy a menudo en la programación funcional que existen múltiples soluciones, todas igualmente legibles, algunas de las cuales se asignan y otras no. Es realmente importante crear el hábito de buscar esas soluciones legibles y no asignadas .

Puede pensar que el optimizador se desharía de las asignaciones, pero usted estaría a la mitad de lo correcto. GHC, el mejor compilador optimizador del mundo para Haskell, logra evitar la asignación de un par por elemento; Fusiona el filter - composición de zip en un foldr2 . La asignación de la lista [1..] permanece. Ahora puede que no pienses que esto es tan malo, pero la fusión de secuencias, que es la tecnología actual de GHC, es una optimización algo frágil. Incluso para los expertos es difícil predecir exactamente cuándo va a funcionar, simplemente mirando el código. El punto más general es que cuando se trata de una propiedad crítica como la asignación, no desea confiar en un optimizador sofisticado cuyos resultados no puede predecir . Mientras puedas escribir tu código de una manera igualmente legible, es mucho mejor que nunca introduzcas esas asignaciones.

Por esta razón, creo que la solución de Nefrubyr que usa drop es, con mucho, la más convincente. Los únicos valores que se asignan son exactamente esas células cons (con : que deben ser parte de la respuesta final. Además, el uso de drop hace que la solución sea más que fácil de leer: es clara como el cristal y obviamente correcta.

Answer 15

Una versión más fea de la respuesta aceptada

every n xs = if rest == [] 
                then [] 
                else head rest : every n (tail rest)
    where rest = drop (n-1) xs

Para "line golfing" puede escribirse así:

every n xs = if rest == [] then [] else head rest : every n (tail rest) 
    where rest = drop (n-1) xs

Answer 16

Use un patrón de vista!

{-# LANGUAGE ViewPatterns #-}

everynth n (drop (n-1) -> l)
  | null l = []
  | otherwise = head l : everynth n (tail l)

La versión fea de la respuesta de Nefrubyr se guardó para que los comentarios tengan sentido.

everynth :: Int -> [a] -> [a]
everynth n l = case splitAt (n-1) l of
                 (_, (x:xs)) -> x : everynth n xs
                 _           -> []

Answer 17

extractEvery nl = map head (iterate (drop n) (drop (n-1) l))

Me iba a sentir orgulloso de mí mismo, hasta que vi que Greg obtuvo la misma respuesta y antes que yo