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