[Haskell-cafe] Performance best practices
bertram.felgenhauer at googlemail.com
Sun Aug 4 06:43:14 UTC 2019
Todd Wilson wrote:
> For example, splits1 [1,2,3] is
Note that `inits` (and hence `splits`) on lists is inherently quadratic,
because the resulting lists , [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
rinits = scanl (flip (:)) 
(so `rinits [1,2,3] = [,,[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
More information about the Haskell-Cafe