5

So if I want to construct a circular list of n 0's and 1 1, which of the following ways is better/cheaper? And is there an even better/cheaper way? Taking into account that n is an Integer and may be large (though realistically its not going to exceed 2^32).

aZerosAndOnes :: Integer -> [Int]
aZerosAndOnes n 
    | n >= 0    = cycle (genericReplicate n 0 ++ [1])
    | otherwise = []

versus

bZerosAndOnes :: Integer -> [Int]
bZerosAndOnes n 
    | n >= 0    = tail (cycle (1 : genericReplicate n 0))
    | otherwise = []
Ramith Jayatilleka
  • 2,132
  • 16
  • 25

1 Answers1

8

I'd definitely go with the second, because it's obviously efficient and plenty clear enough. The first will depend on whether genericReplicate is able to fuse with ++ in some fashion. The best way to find out for sure is to run

ghc -O2 -ddump-simpl -dsuppress-all whatever.hs | less

and pore over what it spews.

That said, the entire length of a cycle will actually be allocated in memory. Such is the nature of the cycle function as currently implemented, and that does not seem likely to change (barring some significant advance—foldr/build fusion does not seem to be sufficient). So you probably be better off avoiding this altogether by writing the rest of your code differently.

Ah yes, I thought of something else. If you consume this list in a "single-threaded" fashion, you can dispense with cycle altogether:

weirdthing n = genericReplicate n 0 ++ [1] ++ weirdthing n

and that's my final answer. This makes an infinite list instead of a cyclic list, but when n is big enough, that's better.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • +1 good observation about `weirdthing`. I wonder if it deserves more explanation though, I guess OP can always ask for more. – luqui Aug 19 '14 at 05:22
  • Thanks. If I write the infinite list recursively instead of using cycle, does that then not have to store the entire cycle?Also, I'm not sure by what you mean that `cycle` stores the entire length. – Ramith Jayatilleka Aug 23 '14 at 19:38
  • Also, I'm not sure by what you mean that `cycle` stores the entire length. Does that mean cycle evaluates the entire list and then cycles over it? Because that would fail on an infinite list, and `cycle (repeat 1)` works fine. – Ramith Jayatilleka Aug 23 '14 at 19:44
  • @RamithJayatilleka, the trouble is that you defeat the garbage collector. As long as you're holding on to a single cons of a cyclic list, it has to keep all the parts that have already been allocated live. If, however, you just make an infinite list that just *looks* the same, it's free to drop anything before the first cons you hold. It won't try to allocate the whole thing at once, but whatever's allocated will be around until it all becomes garbage at once, rather than becoming garbage incrementally. – dfeuer Aug 24 '14 at 04:23