{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:54Z","timestamp":1779836754875,"version":"3.53.1"},"reference-count":2,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2016,8,10]],"date-time":"2016-08-10T00:00:00Z","timestamp":1470787200000},"content-version":"unspecified","delay-in-days":9263,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[1991,4]]},"abstract":"<jats:p>\n                    The function\n                    <jats:italic>remdup<\/jats:italic>\n                    (also called\n                    <jats:italic>mkset<\/jats:italic>\n                    in some functional languages) removes duplicates from a given list. The following definition of\n                    <jats:italic>remdup<\/jats:italic>\n                    is standard and leads to a quadratic time algorithm\n                  <\/jats:p>\n                  <jats:p>\n                    <jats:disp-formula>\n                      <jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0956796800020074_Uequ1\"\/>\n                    <\/jats:disp-formula>\n                  <\/jats:p>\n                  <jats:p>The operator (\u2014) used in the last expression subtracts one list from another; its definition is<\/jats:p>\n                  <jats:p>\n                    <jats:disp-formula>\n                      <jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0956796800020074_Uequ2\"\/>\n                    <\/jats:disp-formula>\n                  <\/jats:p>\n                  <jats:p>\n                    Defined in this way\n                    <jats:italic>remdup x<\/jats:italic>\n                    returns the list of distinct elements of\n                    <jats:italic>x<\/jats:italic>\n                    in the order in which they first appear in\n                    <jats:italic>x<\/jats:italic>\n                    . In other words, the position of\n                    <jats:italic>remdup<\/jats:italic>\n                    JC as a subsequence of\n                    <jats:italic>x<\/jats:italic>\n                    is lexically the smallest among all possible solutions.\n                  <\/jats:p>\n                  <jats:p>\n                    Now let us change the problem and ask that\n                    <jats:italic>remdup<\/jats:italic>\n                    simply return the lexically least solution. Note the subtle difference between this version and the previous one: before, it was the position of the subsequence that was lexically the least, now it is the subsequence itself. To make the distinction clear, consider\n                    <jats:italic>x<\/jats:italic>\n                    = [1,4,2,4,3]. With the original definition\n                    <jats:italic>remdup x<\/jats:italic>\n                    returns [1,4,2,3]; the lexically least subsequence, however, is [1,2,4,3].\n                  <\/jats:p>\n                  <jats:p>The question we are interested in is this: can we also find a quadratic time algorithm for the new problem? The answer turns out to be yes, but justifying it requires a bit of work.<\/jats:p>","DOI":"10.1017\/s0956796800020074","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T18:01:05Z","timestamp":1558116065000},"page":"235-243","source":"Crossref","is-referenced-by-count":0,"title":["Functional Pearls:\n                    <i>On removing duplicates<\/i>"],"prefix":"10.1017","volume":"1","author":[{"given":"Richard S.","family":"Bird","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2016,8,10]]},"reference":[{"key":"S0956796800020074_ref002","volume-title":"Constructive Methods in Computing Science","volume":"52","author":"Bird","year":"1989"},{"key":"S0956796800020074_ref001","volume-title":"Logic of Programming and Calculi of Discrete Design","volume":"36","author":"Bird","year":"1987"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796800020074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:36:48Z","timestamp":1779835008000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796800020074\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":2,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["S0956796800020074"],"URL":"https:\/\/doi.org\/10.1017\/s0956796800020074","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,4]]}}}