Mysterious complexity annotations for `compose`

[sjakobi]

Here's an example from Data.Map.Lazy:

When I first saw this, I was a bit mystified.

• Does ab mean a * b?
• Does |ab| mean something like abs(ab)?

I now suspect that |ab| is supposed to be the size of the (Map a b) argument, but that took me a while.

Other functions nearby generally use m and n for the sizes of their arguments. Arguably that could be made clearer too. Nevertheless I think consistency with the surrounding code might be clearer than this kind of exceptional convention.

@alexfmpe Thoughts?

[treeowl]

Please do fix this.

…

On Fri, May 29, 2020, 7:24 PM Simon Jakobi ***@***.***> wrote: Here's an example from Data.Map.Lazy: [image: image] <https://user-images.githubusercontent.com/3664523/83312565-0595c080-a213-11ea-8ade-a55cf1943032.png> When I first saw this, I was a bit mystified. - Does ab mean a * b? - Does |ab| mean something like abs(ab)? I now suspect that |ab| is supposed to be the size of the (Map a b) argument, but that took me a while. Other functions nearby generally use m and n for the sizes of their arguments. Arguably that could be made clearer too. Nevertheless I think consistency with the surrounding code might be clearer than this kind of exceptional convention. @alexfmpe <https://github.com/alexfmpe> Thoughts? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#722>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7JDGVLN56TW2I5XJ5TRUA7Z3ANCNFSM4NONN2LQ> .

[alexfmpe]

Expanding on #672 (comment):

other bounds seem to be commutative in their arguments, so they don't need to say which argument map is n and which is m, but compose is asymmetric

The bounds I found at the time didn't care about which argument had size m and which had size n, only that m <= n. In this case, there is a need to specify the size of each argument.

How about

O (n * log m), where m is the size of the first argument

[sjakobi]

@alexfmpe Thanks, that looks good to me! Since the annotation is so long then, I think it might make sense to move it into a second paragraph below the Relate … sentence.