Faster `elem` "Hack" for Data.Set?
Viktor Dukhovni <[email protected]> Sat, 29 Jan 2022 19:25:16 -0500
| Newsgroups | gmane.comp.lang.haskell.libraries |
|---|---|
| Message-ID | <[email protected]> |
CkluIGEgcmVjZW50ICJGb2xkaW5nIHRoZSB1bmZvbGRhYmxlIiAiZ2lzdCI6CgogICAgaHR0cHM6 Ly9vbGVnLmZpL2dpc3RzL3Bvc3RzLzIwMjItMDEtMjUtZm9sZGluZy11bmZvbGRhYmxlLmh0bWwK Ck9sZWcgZGVzY3JpYmVzIGEgd2F5IHRvIG1ha2UgdW5ib3hlZCBWZWN0b3JzIEZvbGRhYmxlOgoK ICAgIFRoZXJlIGlzIGFub3RoZXIgd2F5IHRvIG1ha2UgRm9sZGFibGUgd29yaywgd2l0aCBhCgog ICAgICAgIGRhdGEgSGFjayBhIGIgd2hlcmUKICAgICAgICAgICAgSGFjayA6OiBVLlZlY3RvciBh IC0+IEhhY2sgYSBhCgogICAgVGhpcyBpcyBhIHR3byB0eXBlLXBhcmFtZXRlciB3cmFwcGVyLCBi dXQgdGhlIHR5cGVzIGFyZSBhbHdheXMgdGhlCiAgICBzYW1lISAoSSB3aXNoIHRoYXQgY291bGQg YmUgYSBuZXd0eXBlKS4gVGhlIEZvbGRhYmxlIGluc3RhbmNlIGlzCiAgICBzaW1wbHk6CgogICAg ICAgIGluc3RhbmNlIFUuVW5ib3ggYSA9PiBGb2xkYWJsZSAoSGFjayBhKSB3aGVyZQogICAgICAg ICAgICBmb2xkciBmIHogKEhhY2sgdikgID0gVS5mb2xkciBmIHogdgogICAgICAgICAgICBmb2xk bCcgZiB6IChIYWNrIHYpID0gVS5mb2xkbCcgZiB6IHYKCkluIHRoZSBhc3NvY2lhdGVkIFJlZGRp dCB0aHJlYWQKCiAgICBodHRwczovL3d3dy5yZWRkaXQuY29tL3IvaGFza2VsbC9jb21tZW50cy9z ZDZnZWwvY29tbWVudC9odWRtc2lzLz91dG1fc291cmNlPXNoYXJlJnV0bV9tZWRpdW09d2ViMngm Y29udGV4dD0zCgppdCB3YXMgb2JzZXJ2ZWQgdGhhdCBhIHNpbWlsYXIgYXBwcm9hY2ggY2FuIGJl IHVzZWQgdG8gZ2l2ZSBEYXRhLlNldCBhCnBlcmZvcm1hbnQgYGVsZW1gIG1ldGhvZCAoY29kZSBj b3BpZWQgYmVsb3cgbXkgc2lnbmF0dXJlKS4KCkl0IGlzIHNvbWV3aGF0IHRlbXB0aW5nIHRvIGNv bnNpZGVyIHdoZXRoZXIgdGhlICJIYWNrIiBvdWdodCB0byBiZQpidWlsdC1pbiBkaXJlY3RseSBp bnRvIHRoZSByZWFsIERhdGEuU2V0OgoKICAgIGh0dHBzOi8vd3d3LnJlZGRpdC5jb20vci9oYXNr ZWxsL2NvbW1lbnRzL3NkNmdlbC9jb21tZW50L2h1aWwwNzAvP3V0bV9zb3VyY2U9c2hhcmUmdXRt X21lZGl1bT13ZWIyeCZjb250ZXh0PTMKICAgCiAgICB0eXBlIFNldCBhID0gU2V0SW1wbCBhIGEK ICAgIGRhdGEgU2V0SW1wbCBhIGIgd2hlcmUKICAgICAgICBCaW4gOjogey0jIFVOUEFDSyAjLX0g IVNpemUgLT4gIWEgLT4gIShTZXRJbXBsIGEpIC0+ICEoU2V0SW1wbCBhKSAtPiBTZXRJbXBsIGEg YQogICAgICAgIFRpcCA6OiBTZXRJbXBsIGEgYQogICAgdHlwZSBTaXplICAgICA9IEludAoKICAg IGluc3RhbmNlIE9yZCBhID0+IEZvbGRhYmxlIChTZXRJbXBsIGEpIHdoZXJlCiAgICAgICAgLi4u CiAgICAgICAgZWxlbSBfIFRpcCA9IEZhbHNlCiAgICAgICAgZWxlbSB4IChCaW4gXyB5IGwgcikg PSBjYXNlIGNvbXBhcmUgeCB5IG9mCiAgICAgICAgICAgICAgIEVRIC0+IFRydWUKICAgICAgICAg ICAgICAgTFQgLT4gZWxlbSB4IGwKICAgICAgICAgICAgICAgR1QgLT4gZWxlbSB4IHIKICAgICAg ICAuLi4gCgpUaGlzIHJlcHJlc2VudGF0aW9uIGRvZXMgbm90IHNlZW0gdG8gY2FycnkgYW55IG9i dmlvdXMgcnVudGltZSBvdmVyaGVhZCwKYW5kIGdpdmVzIFNldCBhIHBlcmZvcm1hbnQgYGVsZW1g IG1ldGhvZC4gVGhlIG9ubHkgY2hhbmdlIGZyb20gdGhlCnN0YXR1cyBxdW8gd291bGQgYmUgdGhh dCBmb2xkcyB3b3VsZCBub3QgYmUgYXZhaWxhYmxlIGZvciBlbXB0eSBvcgpzaW5nbGV0b24gc2V0 cyB3aXRoIG5vbi1PcmQgZWxlbWVudHMgKGN1cnJlbnRseSBwb3NzaWJsZSB3aXRoIFNldCkuCgpI b3cgbXVjaCBvZiBhIGxvc3Mgd291bGQgaXQgYmUgdG8gY29uc3RyYWluIHRoZSBlbGVtZW50IHR5 cGUgb2YgZW1wdHkKYW5kIHNpbmdsZXRvbiBzZXRzIHVzZWQgaW4gZm9sZHM/ICBBcmUgdGhlcmUg b3RoZXIgaXNzdWUgdGhhdCBtYWtlIHRoZQphYm92ZSBpbXByYWN0aWNhbD8KCi0tIAogICAgVmlr dG9yLgoKICAgIHR5cGUgT1NldCBhID0gT3JkU2V0IGEgYQogICAgZGF0YSBPcmRTZXQgYSBiIHdo ZXJlCiAgICAgICAgT1NldCA6OiBTZXQuU2V0IGEgLT4gT3JkU2V0IGEgYQoKICAgIGluc3RhbmNl IE9yZCBhID0+IEZvbGRhYmxlIChPcmRTZXQgYSkgd2hlcmUKICAgICAgICBmb2xkIChPU2V0IHhz KSA9IGZvbGQgeHMKICAgICAgICBmb2xkTWFwIGYgKE9TZXQgeHMpID0gZm9sZE1hcCBmIHhzCiAg ICAgICAgZm9sZE1hcCcgZiAoT1NldCB4cykgPSBmb2xkTWFwJyBmIHhzCiAgICAgICAgZm9sZHIg ZiB6IChPU2V0IHhzKSA9IGZvbGRyIGYgeiB4cwogICAgICAgIGZvbGRyJyBmIHogKE9TZXQgeHMp ID0gZm9sZHInIGYgeiB4cwogICAgICAgIGZvbGRsIGYgeiAoT1NldCB4cykgPSBmb2xkbCBmIHog eHMKICAgICAgICBmb2xkbCcgZiB6IChPU2V0IHhzKSA9IGZvbGRsJyBmIHogeHMKICAgICAgICBm b2xkcjEgZiAoT1NldCB4cykgPSBmb2xkcjEgZiB4cyAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICBmb2xkbDEgZiAoT1NldCB4 cykgPSBmb2xkbDEgZiB4cwogICAgICAgIHRvTGlzdCAoT1NldCB4cykgPSB0b0xpc3QgeHMKICAg ICAgICBudWxsIChPU2V0IHhzKSA9IG51bGwgeHMKICAgICAgICBsZW5ndGggKE9TZXQgeHMpID0g bGVuZ3RoIHhzCiAgICAgICAgLS0gVGhlIHBvaW50IG9mIHRoZSBleGVyY2lzZSBpcyBgZWxlbWAK ICAgICAgICBlbGVtIGUgKE9TZXQgeHMpID0gU2V0Lm1lbWJlciBlIHhzCiAgICAgICAgbWF4aW11 bSAoT1NldCB4cykgPSBtYXhpbXVtIHhzCiAgICAgICAgbWluaW11bSAoT1NldCB4cykgPSBtaW5p bXVtIHhzCiAgICAgICAgc3VtIChPU2V0IHhzKSA9IHN1bSB4cwogICAgICAgIHByb2R1Y3QgKE9T ZXQgeHMpID0gcHJvZHVjdCB4cwoKICAgIGluc3RhbmNlIEVxIGEgPT4gRXEgKE9TZXQgYSkgd2hl cmUKICAgICAgICAoT1NldCB4cykgPT0gKE9TZXQgeXMpID0geHMgPT0geXMKCiAgICBpbnN0YW5j ZSAoRXEgYSwgT3JkIGEpID0+IE9yZCAoT1NldCBhKSB3aGVyZQogICAgICAgIGNvbXBhcmUgKE9T ZXQgeHMpIChPU2V0IHlzKSA9IGNvbXBhcmUgeHMgeXMKCiAgICBlbXB0eSA6OiBPcmQgYSA9PiBP U2V0IGEKICAgIGVtcHR5ID0gT1NldCBTZXQuZW1wdHkKCiAgICBzaW5nbGV0b24gOjogT3JkIGEg PT4gYSAtPiBPU2V0IGEKICAgIHNpbmdsZXRvbiA9IE9TZXQgLiBTZXQuc2luZ2xldG9uCgogICAg ZnJvbUxpc3QgOjogT3JkIGEgPT4gW2FdIC0+IE9TZXQgYQogICAgZnJvbUxpc3QgPSBPU2V0IC4g U2V0LmZyb21MaXN0CiAgICAgCiAgICAoXFwpIDo6IE9yZCBhID0+IE9TZXQgYSAtPiBPU2V0IGEg LT4gT1NldCBhCiAgICAoT1NldCB4cykgXFwgKE9TZXQgeXMpID0gT1NldCAoeHMgU2V0LlxcIHlz KQoKICAgIGFsdGVyRiA6OiAoT3JkIGEsIEZ1bmN0b3IgZikgPT4gKEJvb2wgLT4gZiBCb29sKSAt PiBhIC0+IE9TZXQgYSAtPiBmIChPU2V0IGEpCiAgICBhbHRlckYgZiB4IChPU2V0IHhzKSA9IGZt YXAgT1NldCAkIFNldC5hbHRlckYgZiB4IHhzCgogICAgLi4uCl9fX19fX19fX19fX19fX19fX19f X19fX19fX19fX19fX19fX19fX19fX19fX19fCkxpYnJhcmllcyBtYWlsaW5nIGxpc3QKTGlicmFy aWVzQGhhc2tlbGwub3JnCmh0dHA6Ly9tYWlsLmhhc2tlbGwub3JnL2NnaS1iaW4vbWFpbG1hbi9s aXN0aW5mby9saWJyYXJpZXMK