Re: Faster `elem` "Hack" for Data.Set?
David Feuer <[email protected]> Sat, 29 Jan 2022 19:59:51 -0500
| Newsgroups | gmane.comp.lang.haskell.libraries |
|---|---|
| Message-ID | <CAMgWh9uLKrEFkznybbHDeLXz7W_VWY8TvHbhZmzxqZY2JY+T_w@mail.gmail.com> |
VGhlIHRpZ2h0ZXIgYEZvbGRhYmxlYCBpbnN0YW5jZSBwcm9iYWJseSB3b3VsZG4ndCBodXJ0IHRv byBtdWNoIGluCnByYWN0aWNlLiBJIGhhdmUgc29tZSBvdGhlciBjb25jZXJucywgaG93ZXZlci4g T25lIGlzIHRoYXQKYGNvbnRhaW5lcnNgIGhhcyBhIGxvbmcgaGlzdG9yeSBvZiBhdHRlbXB0aW5n IHRvIHJlbWFpbiBjb21wYXRpYmxlCndpdGggcG90ZW50aWFsIGZ1dHVyZSBIYXNrZWxsIDk4LWxp a2UgSGFza2VsbCBpbXBsZW1lbnRhdGlvbnMgKGxpa2VseQp3aXRoIGEgZmV3IGRheXMgb2Ygd29y ayB0byBwYXRjaCB1cCBtaXN0YWtlcyB3aGVuIHRoZSB0aW1lIGNvbWVzKS4KVXNpbmcgYSBHQURU IHRvIGRlZmluZSBTZXQgd291bGQgYnJlYWsgdGhhdCBxdWl0ZSB0aG9yb3VnaGx5LiBNeQpzZWNv bmQgY29uY2VybiBpcyBtb3JlIHByYWN0aWNhbDoKCiAgdHlwZSBTZXQgYSA9IFNldEltcGwgYSBh CgppcyBhbGwgc29ydHMgb2YgcHJvYmxlbWF0aWMuIEl0IGZvcmNlcyBhbnlvbmUgd2hvIHdhbnRz IHRvIHVzZSB3aGF0J3MKYWx3YXlzIGJlZW4gdGhlIGBTZXRgIHR5cGUgY29uc3RydWN0b3IgKFNl dCA6OiBUeXBlIC0+IFR5cGUpIHRvIGRpZwppbnRvIHRoZSBpbXBsZW1lbnRhdGlvbiBhbmQgdXNl IGBTZXRJbXBsIDo6IFR5cGUgLT4gVHlwZSAtPiBUeXBlYAppbnN0ZWFkLiBUaGF0J3MgcXVpdGUg YSBkaWZmZXJlbnQgYmVhc3QuIEkgZG9uJ3Qga25vdyBhbGwgdGhlIHRoaW5ncwp0aGF0IHdpbGwg YnJlYWssIGJ1dCB0aGV5J2xsIHN1cmVseSBpbmNsdWRlCmh0dHBzOi8vaGFja2FnZS5oYXNrZWxs Lm9yZy9wYWNrYWdlL2NvbnN0cmFpbmVkLW1vbmFkcy0wLjUuMC4wL2RvY3MvQ29udHJvbC1Nb25h ZC1Db25zdHJhaW5lZC5odG1sCi4gSSB0aGluayB0aGUgcmVhbCBhbnN3ZXIgaXMgdG8gcmVtb3Zl IGBlbGVtYCBmcm9tIGBGb2xkYWJsZWAgYW5kIHB1dAppdCBzb21ld2hlcmUgbW9yZSBhcHByb3By aWF0ZS4KCk9uIFNhdCwgSmFuIDI5LCAyMDIyIGF0IDc6MjYgUE0gVmlrdG9yIER1a2hvdm5pIDxp ZXRmLWRhbmVAZHVraG92bmkub3JnPiB3cm90ZToKPgo+Cj4gSW4gYSByZWNlbnQgIkZvbGRpbmcg dGhlIHVuZm9sZGFibGUiICJnaXN0IjoKPgo+ICAgICBodHRwczovL29sZWcuZmkvZ2lzdHMvcG9z dHMvMjAyMi0wMS0yNS1mb2xkaW5nLXVuZm9sZGFibGUuaHRtbAo+Cj4gT2xlZyBkZXNjcmliZXMg YSB3YXkgdG8gbWFrZSB1bmJveGVkIFZlY3RvcnMgRm9sZGFibGU6Cj4KPiAgICAgVGhlcmUgaXMg YW5vdGhlciB3YXkgdG8gbWFrZSBGb2xkYWJsZSB3b3JrLCB3aXRoIGEKPgo+ICAgICAgICAgZGF0 YSBIYWNrIGEgYiB3aGVyZQo+ICAgICAgICAgICAgIEhhY2sgOjogVS5WZWN0b3IgYSAtPiBIYWNr IGEgYQo+Cj4gICAgIFRoaXMgaXMgYSB0d28gdHlwZS1wYXJhbWV0ZXIgd3JhcHBlciwgYnV0IHRo ZSB0eXBlcyBhcmUgYWx3YXlzIHRoZQo+ICAgICBzYW1lISAoSSB3aXNoIHRoYXQgY291bGQgYmUg YSBuZXd0eXBlKS4gVGhlIEZvbGRhYmxlIGluc3RhbmNlIGlzCj4gICAgIHNpbXBseToKPgo+ICAg ICAgICAgaW5zdGFuY2UgVS5VbmJveCBhID0+IEZvbGRhYmxlIChIYWNrIGEpIHdoZXJlCj4gICAg ICAgICAgICAgZm9sZHIgZiB6IChIYWNrIHYpICA9IFUuZm9sZHIgZiB6IHYKPiAgICAgICAgICAg ICBmb2xkbCcgZiB6IChIYWNrIHYpID0gVS5mb2xkbCcgZiB6IHYKPgo+IEluIHRoZSBhc3NvY2lh dGVkIFJlZGRpdCB0aHJlYWQKPgo+ICAgICBodHRwczovL3d3dy5yZWRkaXQuY29tL3IvaGFza2Vs bC9jb21tZW50cy9zZDZnZWwvY29tbWVudC9odWRtc2lzLz91dG1fc291cmNlPXNoYXJlJnV0bV9t ZWRpdW09d2ViMngmY29udGV4dD0zCj4KPiBpdCB3YXMgb2JzZXJ2ZWQgdGhhdCBhIHNpbWlsYXIg YXBwcm9hY2ggY2FuIGJlIHVzZWQgdG8gZ2l2ZSBEYXRhLlNldCBhCj4gcGVyZm9ybWFudCBgZWxl bWAgbWV0aG9kIChjb2RlIGNvcGllZCBiZWxvdyBteSBzaWduYXR1cmUpLgo+Cj4gSXQgaXMgc29t ZXdoYXQgdGVtcHRpbmcgdG8gY29uc2lkZXIgd2hldGhlciB0aGUgIkhhY2siIG91Z2h0IHRvIGJl Cj4gYnVpbHQtaW4gZGlyZWN0bHkgaW50byB0aGUgcmVhbCBEYXRhLlNldDoKPgo+ICAgICBodHRw czovL3d3dy5yZWRkaXQuY29tL3IvaGFza2VsbC9jb21tZW50cy9zZDZnZWwvY29tbWVudC9odWls MDcwLz91dG1fc291cmNlPXNoYXJlJnV0bV9tZWRpdW09d2ViMngmY29udGV4dD0zCj4KPiAgICAg dHlwZSBTZXQgYSA9IFNldEltcGwgYSBhCj4gICAgIGRhdGEgU2V0SW1wbCBhIGIgd2hlcmUKPiAg ICAgICAgIEJpbiA6OiB7LSMgVU5QQUNLICMtfSAhU2l6ZSAtPiAhYSAtPiAhKFNldEltcGwgYSkg LT4gIShTZXRJbXBsIGEpIC0+IFNldEltcGwgYSBhCj4gICAgICAgICBUaXAgOjogU2V0SW1wbCBh IGEKPiAgICAgdHlwZSBTaXplICAgICA9IEludAo+Cj4gICAgIGluc3RhbmNlIE9yZCBhID0+IEZv bGRhYmxlIChTZXRJbXBsIGEpIHdoZXJlCj4gICAgICAgICAuLi4KPiAgICAgICAgIGVsZW0gXyBU aXAgPSBGYWxzZQo+ICAgICAgICAgZWxlbSB4IChCaW4gXyB5IGwgcikgPSBjYXNlIGNvbXBhcmUg eCB5IG9mCj4gICAgICAgICAgICAgICAgRVEgLT4gVHJ1ZQo+ICAgICAgICAgICAgICAgIExUIC0+ IGVsZW0geCBsCj4gICAgICAgICAgICAgICAgR1QgLT4gZWxlbSB4IHIKPiAgICAgICAgIC4uLgo+ Cj4gVGhpcyByZXByZXNlbnRhdGlvbiBkb2VzIG5vdCBzZWVtIHRvIGNhcnJ5IGFueSBvYnZpb3Vz IHJ1bnRpbWUgb3ZlcmhlYWQsCj4gYW5kIGdpdmVzIFNldCBhIHBlcmZvcm1hbnQgYGVsZW1gIG1l dGhvZC4gVGhlIG9ubHkgY2hhbmdlIGZyb20gdGhlCj4gc3RhdHVzIHF1byB3b3VsZCBiZSB0aGF0 IGZvbGRzIHdvdWxkIG5vdCBiZSBhdmFpbGFibGUgZm9yIGVtcHR5IG9yCj4gc2luZ2xldG9uIHNl dHMgd2l0aCBub24tT3JkIGVsZW1lbnRzIChjdXJyZW50bHkgcG9zc2libGUgd2l0aCBTZXQpLgo+ Cj4gSG93IG11Y2ggb2YgYSBsb3NzIHdvdWxkIGl0IGJlIHRvIGNvbnN0cmFpbiB0aGUgZWxlbWVu dCB0eXBlIG9mIGVtcHR5Cj4gYW5kIHNpbmdsZXRvbiBzZXRzIHVzZWQgaW4gZm9sZHM/ICBBcmUg dGhlcmUgb3RoZXIgaXNzdWUgdGhhdCBtYWtlIHRoZQo+IGFib3ZlIGltcHJhY3RpY2FsPwo+Cj4g LS0KPiAgICAgVmlrdG9yLgo+Cj4gICAgIHR5cGUgT1NldCBhID0gT3JkU2V0IGEgYQo+ICAgICBk YXRhIE9yZFNldCBhIGIgd2hlcmUKPiAgICAgICAgIE9TZXQgOjogU2V0LlNldCBhIC0+IE9yZFNl dCBhIGEKPgo+ICAgICBpbnN0YW5jZSBPcmQgYSA9PiBGb2xkYWJsZSAoT3JkU2V0IGEpIHdoZXJl Cj4gICAgICAgICBmb2xkIChPU2V0IHhzKSA9IGZvbGQgeHMKPiAgICAgICAgIGZvbGRNYXAgZiAo T1NldCB4cykgPSBmb2xkTWFwIGYgeHMKPiAgICAgICAgIGZvbGRNYXAnIGYgKE9TZXQgeHMpID0g Zm9sZE1hcCcgZiB4cwo+ICAgICAgICAgZm9sZHIgZiB6IChPU2V0IHhzKSA9IGZvbGRyIGYgeiB4 cwo+ICAgICAgICAgZm9sZHInIGYgeiAoT1NldCB4cykgPSBmb2xkcicgZiB6IHhzCj4gICAgICAg ICBmb2xkbCBmIHogKE9TZXQgeHMpID0gZm9sZGwgZiB6IHhzCj4gICAgICAgICBmb2xkbCcgZiB6 IChPU2V0IHhzKSA9IGZvbGRsJyBmIHogeHMKPiAgICAgICAgIGZvbGRyMSBmIChPU2V0IHhzKSA9 IGZvbGRyMSBmIHhzCj4gICAgICAgICBmb2xkbDEgZiAoT1NldCB4cykgPSBmb2xkbDEgZiB4cwo+ ICAgICAgICAgdG9MaXN0IChPU2V0IHhzKSA9IHRvTGlzdCB4cwo+ICAgICAgICAgbnVsbCAoT1Nl dCB4cykgPSBudWxsIHhzCj4gICAgICAgICBsZW5ndGggKE9TZXQgeHMpID0gbGVuZ3RoIHhzCj4g ICAgICAgICAtLSBUaGUgcG9pbnQgb2YgdGhlIGV4ZXJjaXNlIGlzIGBlbGVtYAo+ICAgICAgICAg ZWxlbSBlIChPU2V0IHhzKSA9IFNldC5tZW1iZXIgZSB4cwo+ICAgICAgICAgbWF4aW11bSAoT1Nl dCB4cykgPSBtYXhpbXVtIHhzCj4gICAgICAgICBtaW5pbXVtIChPU2V0IHhzKSA9IG1pbmltdW0g eHMKPiAgICAgICAgIHN1bSAoT1NldCB4cykgPSBzdW0geHMKPiAgICAgICAgIHByb2R1Y3QgKE9T ZXQgeHMpID0gcHJvZHVjdCB4cwo+Cj4gICAgIGluc3RhbmNlIEVxIGEgPT4gRXEgKE9TZXQgYSkg d2hlcmUKPiAgICAgICAgIChPU2V0IHhzKSA9PSAoT1NldCB5cykgPSB4cyA9PSB5cwo+Cj4gICAg IGluc3RhbmNlIChFcSBhLCBPcmQgYSkgPT4gT3JkIChPU2V0IGEpIHdoZXJlCj4gICAgICAgICBj b21wYXJlIChPU2V0IHhzKSAoT1NldCB5cykgPSBjb21wYXJlIHhzIHlzCj4KPiAgICAgZW1wdHkg OjogT3JkIGEgPT4gT1NldCBhCj4gICAgIGVtcHR5ID0gT1NldCBTZXQuZW1wdHkKPgo+ICAgICBz aW5nbGV0b24gOjogT3JkIGEgPT4gYSAtPiBPU2V0IGEKPiAgICAgc2luZ2xldG9uID0gT1NldCAu IFNldC5zaW5nbGV0b24KPgo+ICAgICBmcm9tTGlzdCA6OiBPcmQgYSA9PiBbYV0gLT4gT1NldCBh Cj4gICAgIGZyb21MaXN0ID0gT1NldCAuIFNldC5mcm9tTGlzdAo+Cj4gICAgIChcXCkgOjogT3Jk IGEgPT4gT1NldCBhIC0+IE9TZXQgYSAtPiBPU2V0IGEKPiAgICAgKE9TZXQgeHMpIFxcIChPU2V0 IHlzKSA9IE9TZXQgKHhzIFNldC5cXCB5cykKPgo+ICAgICBhbHRlckYgOjogKE9yZCBhLCBGdW5j dG9yIGYpID0+IChCb29sIC0+IGYgQm9vbCkgLT4gYSAtPiBPU2V0IGEgLT4gZiAoT1NldCBhKQo+ ICAgICBhbHRlckYgZiB4IChPU2V0IHhzKSA9IGZtYXAgT1NldCAkIFNldC5hbHRlckYgZiB4IHhz Cj4KPiAgICAgLi4uCj4gX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fX18KPiBMaWJyYXJpZXMgbWFpbGluZyBsaXN0Cj4gTGlicmFyaWVzQGhhc2tlbGwub3JnCj4g aHR0cDovL21haWwuaGFza2VsbC5vcmcvY2dpLWJpbi9tYWlsbWFuL2xpc3RpbmZvL2xpYnJhcmll cwpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fXwpMaWJyYXJp ZXMgbWFpbGluZyBsaXN0CkxpYnJhcmllc0BoYXNrZWxsLm9yZwpodHRwOi8vbWFpbC5oYXNrZWxs Lm9yZy9jZ2ktYmluL21haWxtYW4vbGlzdGluZm8vbGlicmFyaWVzCg==