stimes for Endo · Issue #4 · haskell/core-libraries-committee (original) (raw)

Let me write down my understanding of the proposal.

Semigroup.stimes is a short-cut for sconcat (replicate n a). The latter, implemented naively, takes O(n) time to produce a result.

stimesMonoid implements stimes n a = sconcat (replicate n a) by building a, a2 = a <> a, a4 = a2 <> a2, a8 = a4 <> a4, and concatenating intermediate values corresponding to non-zero binary digits of n. This usually gives us O(log n) complexity.

In case of newtype Endo a = Endo { appEndo :: a -> a } we can indeed build a thunk, corresponding to stimes n f, in O(log n) time. However, we rarely wish to build such thunk just to adorn our heap, and most likely we intend to apply it to an argument. Unless f = const foo, evaluation of appEndo (stimes n f) x must invoke f repeatedly n times. However, the binary tree built by stimesMonoid is likely to hide from GHC the exact nature of computation and cause high constant factor.

The proposal is to implement stimes for Endo not via stimesMonoid, but rather via a generalized version of stimesList. This has two-fold advantage: a thunk itself is built in O(1), and its evaluation, while still O(n), is much friendlier to GHC optimizer and runtime, likely to lead to performance gains.

@treeowl, is my rendering correct? Could you please share results for Endo (1+) benchmarks?