Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

Efficiency of `times1p` for `[]` #9

ppetr opened this Issue Dec 20, 2012 · 1 comment


None yet
2 participants

ppetr commented Dec 20, 2012

The instance Semigroup [a] uses the default implementation of times1p for replicating lists. I wonder, is there any advantage compared to the "standard" implementation

    times1p n x = let rep 0 = x
                      rep i = x ++ rep (i - 1)
                  in rep n

? Both have O(n) time overhead. But if the resulting list is consumed lazily, the default implementation of times1p has O(n * length x) memory overhead, while the "standard" variant has O(length x).

(Also head (times1p n x) takes O(1) time for the "standard" implementation but O(ln n) for the current default one. But I don't think this is important, since replicating a list to only read its head is probably something that never happens.)

@ekmett ekmett closed this in 194c8da Dec 20, 2012


ekmett commented Dec 20, 2012

Done. Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment