[Haskell-cafe] Performance best practices

[Bertram Felgenhauer]

Todd Wilson wrote:
> For example, splits1 [1,2,3] is
> [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])].

Note that `inits` (and hence `splits`) on lists is inherently quadratic,
because the resulting lists [1], [1,2], [1,2,3], and so on, cannot share
any parts of their spines. The only way around this is to change the
result, either the type (as suggested elsewhere in this list), or the
result itself. A cute option is to produce reversed lists, which can be
achieved by

  rinits = scanl (flip (:)) []

(so `rinits [1,2,3] = [[],[1],[2,1],[3,2,1]]`). This works on plain
lists, and uses linear time and memory.

(One can view this as changing the result type to a list of snoc lists.
This fact can be expressed using a newtype wrapper or a custom list type
if desired.)

Cheers,

Bertram