Thanks, Viktor, for your response, but I think you misunderstood my question:
On Tue, Dec 15, 2020 at 3:14 PM Viktor Dukhovni
On Tue, Dec 15, 2020 at 02:05:13PM -0800, Todd Wilson wrote:
In code of the form case as ++ bs of [] -> ... x:xs -> ...
under what circumstances is the overhead of cons-cell creation for the elements of `as` that would happen in an eager language avoided?
In Haskell, even without optimisation, I'd expect the above to run in constant space and time regardless of the length of `as`.
Of course this is constant time and space, but that wasn't what I was asking. Suppose HNF(as) = a : ys. Then the `case` will cause the definition of (++) to unfold once and produce a : (ys ++ bs), taking the second branch with x = a and xs = ys ++ bs, the latter a thunk. My question was whether a cons-cell containing `a` is created in the heap or not -- that's the "overhead" I was asking about. In this case, it seems that the compiler could easily avoid this overhead by inlining the definition of (++) and doing some basic simplification to arrive at
case as of [] -> case bs of [] -> -- 1st branch above x:xs -> -- 2nd branch above x:ys -> let xs = ys ++ bs in -- 2nd branch above
My follow-up questions were about whether this overhead would also be avoided in `f (as ++ bs)` if f was defined in the same module by list recursion, or in another module or the Prelude (say f = length). Here is a similar, but more sophisticated example involving flattening of nested lists, coded three ways:
data Nest a = Nil | Cons a (Nest a) | Nest (Nest a) (Nest a)
flatten :: Nest a -> [a] flatten Nil = [] flatten (Cons x n) = x : flatten n flatten (Nest n1 n2) = flatten n1 ++ flatten n2
flatten2 n = fl [n] where fl :: [Nest a] -> [a] fl [] = [] fl (Nil : ns) = fl ns fl (Cons x n : ns) = x : fl (n:ns) fl (Nest n1 n2 : ns) = fl (n1:n2:ns)
flatten3 n = fl n [] where fl :: Nest a -> [Nest a] -> [a] fl Nil [] = [] fl Nil (n:ns) = fl n ns fl (Cons x n) ns = x : fl n ns fl (Nest n1 n2) ns = fl n1 (n2:ns)
On the surface, the difference between these three functions is how many cons-cells they create, in decreasing order. In `flatten`, elements are also copied during (++) operations a number of times equal to their depth in the original nested list; the other two each copy the original elements once. But does (or can) the compiler simplify `flatten2` more or less to `flatten3`? It seems to hinge on how nested patterns are handled. Again, I wish I had some general principles about what kind of compiler optimizations are applied, so that I could answer such questions in the abstract and write code in an easier-to-understand but seemingly more expensive way knowing that the extra expense was going to be compiled away. --Todd