[Haskell-cafe] Question on optimization

[Todd Wilson]

Thanks, Viktor, for your response, but I think you misunderstood my question:

On Tue, Dec 15, 2020 at 3:14 PM Viktor Dukhovni <ietf-dane at dukhovni.org> wrote:
>
> 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