length $ splits $ replicate 1000000 M

This should give you the result 1000001 quite quickly.

Now try this:

length $ splits' $ replicate 1000000 M

I wasn’t able to get a result within a reasonable amount of time.

The problem with split' lies in the use of inits. The inits function is implemented as follows:

inits :: [a] -> [[a]]
inits xs = [] : case xs of
                    []      -> []
                    x : xs' -> map (x : ) (inits xs')

Note that the recursive application of inits is under a map. So the suffix of an expression inits [x_1,x_2,…,x_n] that starts at an index  is defined by a nested application of map of depth :

map (x_1 : ) (map (x_2 : ) (…(map (x_i : ) […])…))

To detect that the result of an expression map f xs is non-empty, we have to detect that xs is non-empty. So to detect that the above suffix is non-empty, we need to walk through the layers of maps, which takes time.

This means that to fetch the -th element of inits xs, we need

time.

The implementation of split doesn’t suffer from this problem, since it creates prefixes by a single application of map, and computes every single prefix independently.

Thank you!