How to get every Nth element of an infinite list in Haskell?
haskell every second element of list
get nth element of list
haskell first n elements of list
haskell remove element from list
haskell index of element in list
haskell remove last element from list
haskell access first element of list
More specifically, how do I generate a new list of every Nth element from an existing infinite list?
E.g. if the list is
[5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ...] then getting every 3rd element would result in this list
My version using drop:
every n xs = case drop (n-1) xs of (y:ys) -> y : every n ys  -> 
Edit: this also works for finite lists. For infinite lists only, Charles Stewart's solution is slightly shorter.
How to get every Nth element of an infinite list in Haskell?, More specifically, how do I generate a new list of every Nth element from an existing infinite list? E.g. if the list is [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ] then getting cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists. You could define repeatInts in terms of cycle: *Main> let repeatInts n = cycle [1..n] *Main> :t repeatInts repeatInts :: (Num t, Enum t) => t -> [t] *Main> take 10 $ repeatInts 3 [1,2,3,1,2,3,1,2,3,1]
All the solutions using
zip and so on do tons of unnecessary allocations. As a functional programmer, you want to get into the habit of not allocating unless you really have to. Allocation is expensive, and compared to allocation, everything else is free. And allocation doesn't just show up in the "hot spots" you would find with a profiler; if you don't pay attention to allocation, it kills you everywhere.
Now I agree with the commentators that readability is the most important thing. Nobody wants to get wrong answers fast. But it happens very often in functional programming that there are multiple solutions, all about equally readable, some of which allocate and some of which do not. It's really important to build a habit of looking for those readable, non-allocating solutions.
You might think that the optimizer would get rid of allocations, but you'd only be half right. GHC, the world's best optimizing compiler for Haskell, does manage to avoid allocating a pair per element; it fuses the
zip composition into a
foldr2. The allocation of the list
[1..] remains. Now you might not think this is so bad, but stream fusion, which is GHC's current technology, is a somewhat fragile optimization. It's hard even for experts to predict exactly when it's going to work, just by looking at the code. The more general point is that when it comes to a critical property like allocation, you don't want to rely on a fancy optimizer whose results you can't predict. As long as you can write your code in an equally readable way, you're much better off never introducing those allocations.
For these reason I find Nefrubyr's solution using
drop to be by far the most compelling. The only values that are allocated are exactly those cons cells (with
:) that must be part of the final answer. Added to that, the use of
drop makes the solution more than just easy to read: it is crystal clear and obviously correct.
How to get every Nth element of an infinite list in Haskell?, More specifically, how do I generate a new list of every Nth element from an existing infinite list? E.g. if the list is [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ] then getting The problem to find the nth element of the list is that each element doesn't know which element it is. Then a simple answer is to add this information close to each element. ['a','b','c','d'] -> [('a',0), ('b',1), ('c',2), ('d',3)] You can achieve this by doing a simple: zip xs [1..]
I don't have anything to test this with at work, but something like:
extractEvery m = map snd . filter (\(x,y) -> (mod x m) == 0) . zip [1..]
should work even on infinite lists.
(Edit: tested and corrected.)
Take every n-th element from list (without recursion)? : haskell, More specifically, how do I generate a new list of every Nth element from an existing infinite list? E.g. if the list is [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, E.g. if the list is [5, 3, 0, 1, 8, 0, 3, 4, 0, 93, 211, 0 ] then getting every 3rd element would result in this list [0,0,0,0,0 ] extractEvery n l = map head (iterate (drop n) (drop (n-1) l)) I was going to feel proud of myself, until I saw that Greg got about the same answer and before me
Starting at the first element:
everyf n  =  everyf n as = head as : everyf n (drop n as)
Starting at the nth element:
every n = everyf n . drop (n-1)
Am I thinking functionally in these simple Haskell functions?, I have simple homework. I need to write function that takes list of alphas and return list of lists of alphas (1st element its the same list as function takes, then 2nd Call an helper function design to process recursively our indexed list. Now for the helper function, the list can't be empty then we can pattern match naively, and, if our index is equal to n we have a winner ; else, if our next element is empty it's over; else, call the helper function with the next element.
The compiler or interpreter will compute the step size (subtract 1 since it's zero based):
f l n = [l !! i | i <- [n-1,n-1+n..]]
Real World Haskell: Lecture 3, Haskell can do better! Use -Wall to get a proper warning for that one: incomplete patterns in function . isMiddleMax _ = error "Only works on 3-element lists!" an infinite list out of a finite one by repeatedly appending the list to itself (in effect). everyNth xs n = [x | (True, x) <- zip (cycle includes) xs] where includes = [i Note that, since the head of the resulting expression is produced by an application of the operator to the first element of the list, foldr can produce a terminating expression from an infinite list. For a general Foldable structure this should be semantically identical to, foldr f z = foldr f z . toList
The Haskell School of Expression: Learning Functional Programming , Real World Haskell: Lecture 3 Bryan O'Sullivan 2009-10-21. Integer is a signed integer type of unbounded size (unbounded if you have inﬁnite memory, that is). Functions have types, too f a c t : : I n t e g e r −> I n t e g e r fact n | n < 0 And as the notation suggests, every element in a list must have the Modifying the list or its elements. Apply a function to all list elements. map my_function xs. Apply a function to just some elements of a list. Assuming you only want to apply function f to elements for which function p returns true, you can do this: map (\x -> if p x then f x else x) xs.
The Haskell School of Music: From Signals to Symphonies, To start , iterate f x returns an infinite list of repeated applications off to x . of every element and replicate n x is a list of length n with x the value of every text ) is a very common practice , so it makes sense that Haskell would have a few n) stuff does not actually delete the nth element (every time)it actually just deletes the first element in the list that matches the nth element. Sothat is hard to do without traversing it least the first n steps initially.
To start, iterate f x returns an infinite list of repeated applications off to x. an infinite list, with x the value of every element. replicate n x is a list of length n with text) is a very common practice, so it makes sense that Haskell would have a few If you want to read more about using lazy lists in Haskell, the Haskell Wiki is your best bet, in particular this page on building an infinite list of prime numbers is a good example of where the
- I would be inclined to name this
takeNth; unfortunately, both of those in various other languages refer to a version that always includes the first element and only starts skipping N thereafter. Not sure how best to distinguish those intents in the name.
- Deciphering session would be great. What  ->  does?
 -> is using pattern matching to return an empty list when
drop (n-1) xsreturns an empty list.
- I would also like to add that the two patterns of this function should be switched for a properly formatted tail call. So
 -> should come before
(y:ys) -> y : every n ys.
- I'm still fresh with Haskell, this is melting my brain. But I shall not stop trying :) Thanks for the answers!
- I agree, and I find Nefrubyr's solution easier to follow as well.
- I'm sure a good compiler will avoid the unnessary allocations.
- -1, i would recommend coding for readability then profiling then optimizing the profiled portions. No point in making code readability sacrifices when it may not even cause a problem
- @trinithis: I checked with GHC, and you are mostly right. But you make a good point, so I have edited my answer to make it clear why you don't necessarily want to throw an optimizer at some code and hope for the best.
- @RCIX: I agree with you, but only in part. Certainly readability is paramount. But if you ignore allocation everywhere, then you will slow down all of your program, and there won't necessarily be "hot spots" that you can find easily by profiling. I've updated my asnwer to try to reflect a more nuanced view.
- Thanks, this works well, although I don't quite understand it yet (I'm still a beginner in Haskell).
- doing lots of work with predictable results... never do this in real code.