18

I'm a C# guy trying to teach myself Haskell from Erik Meijer's Channel 9 webcasts. I came across an interesting puzzle which involved skipping every 'n' elements of a list using zip and mod.

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs [1..], i `mod` n == 0]

I've been thinking it might be more efficient (for really large lists, or streams) if we could avoid using mod.

I thought about lazily creating a repeating list of integers so we can simply compare the value of i to n.

repeatInts :: Int -> [Int]

such that calling repeatInts 3 returns [1,2,3,1,2,3,1,2,3,1,2,3,..] ad infinitum.

Given this, we could redefine every like so:

every :: Int -> [a] -> [a]
every _ [] = []
every n xs = [x | (x,i) <- zip xs (repeatInts n), i == n]

So my questions is: how would you implement repeatInts?

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
Damian Powell
  • 8,655
  • 7
  • 48
  • 58

2 Answers2

27

Use cycle:

cycle :: [a] -> [a]

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]

For the curious, GHC implements cycle with

cycle [] = errorEmptyList "cycle"
cycle xs = xs' where xs' = xs ++ xs'

In purely functional parlance, this curious technique is known as tying the knot, and it creates cyclic data structures rather than infinite ones.

For details see

Greg Bacon
  • 134,834
  • 32
  • 188
  • 245
  • Thanks, gbacon. Somehow I knew there'd be a simple answer! Now I can dig into the workings of `cycle`. – Damian Powell Jan 10 '10 at 00:29
  • Somewhat strangely, `cycle` is standard Haskell '98, even though cyclic lists are not. See what the source (above) says about it - you might or might not get a cyclic list... – Charles Stewart Jan 11 '10 at 11:38
  • 1
    funnily, this Q/A is itself an instance of the XY problem. ;) skipping every nth element in a list shouldn't involve any `mod`, nor counting to infinity. the proper solution seems to be with either `zip` with `(cycle $ (0 <$ [2..n]) ++ [1])`, or via `iterate` with `splitAt`. :) – Will Ness Oct 18 '17 at 15:40
4

Late answer but it can also be written like this:

repeatInts :: Int -> [Int]
repeatInts 0 = []
repeatInts a = [1..a] ++ repeatInts a
Sam R.
  • 16,027
  • 12
  • 69
  • 122