[darcs-devel] patch list concatenation

Ben Franksen ben.franksen at online.de
Mon May 24 06:36:53 UTC 2021


Hi Ganesh

>> * use +<<+ instead of  +<+ reverseFL
> 
> Fine though I'm not actually sure this is an improvement, it doesn't 
> have a complexity advantage and is another operator to remember.

It is true that it does not have better asymptotic complexity but it
fuses the two traversals. Assume the RHS has two elements and we demand
the head of the result. So we have xs +<+ reverseFL ys, where
ys = y1 :<: y2 :<: NilFL. (r is the local function inside reverseFL.)

  xs +<+ reverseFL (y1 :<: y2 :<: NilFL)
= xs +<+ r NilRL (y1 :<: y2 :<: NilFL)
= xs +<+ r (NilRL :<: y1) :<: (y2 :<: NilFL)
= xs +<+ r (NilRL :<: y1 :<: y2) NilFL
= xs +<+ (NilRL :<: y1 :<: y2)
= (xs +<+ (NilRL :<:y1)) :<: y2

With +<<+ this becomes

  xs +<<+ (y1 :<: y2 :<: NilFL)
= (xs :<: y1) +<<+ (y2 :<: NilFL)
= (xs :<: y1 :<: y2) :<: NilFL
= xs :<: y1 :<: y2

There are no intermediate data structures and less evaluation steps.

> But it was there before and we could debate removing it and +>>+
> entirely in a separate patch.

I prefer +<<+ and +>>+ over (+<+ reverseFL) and (reverseRL +>+) not only
because they are more efficient, but also  because they make the code
more concise, which means you can focus on  the interesting parts. I
regard reverseFL and reverseRL as "administrative noise" to be
eliminated where possible.

Regarding the cognitive burden: We have four concatenation operators:
+<+ +>+ +<<+ +>>+. They all have the same meaning, but differ in the
argument and result types. When reading code, it doesn't matter which
one is used: you can mentally replace them all with "concatenate these
two lists" without spending any thought on the concrete types.

Cheers
Ben
-- 
I would rather have questions that cannot be answered, than answers that
cannot be questioned.  -- Richard Feynman



More information about the darcs-devel mailing list