{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:29Z","timestamp":1750221029754,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,7,26]]},"abstract":"<jats:p>\n            Effectively computing the difference between two version of a source file has become an indispensable part of software development. The\n            <jats:italic>de facto<\/jats:italic>\n            standard tool used by most version control systems is the UNIX diff utility, that compares two files on a line-by-line basis without any regard for the\n            <jats:italic>structure<\/jats:italic>\n            of the data stored in these files.\n          <\/jats:p>\n          <jats:p>\n            This paper presents an alternative\n            <jats:italic>datatype generic<\/jats:italic>\n            algorithm for computing the difference between two values of\n            <jats:italic>any<\/jats:italic>\n            algebraic datatype. This algorithm maximizes sharing between the source and target trees, while still running in linear time.\n          <\/jats:p>\n          <jats:p>Finally, this paper demonstrates that by instantiating this algorithm to the Lua abstract syntax tree and mining the commit history of repositories found on GitHub, the resulting patches can often be merged automatically, even when existing technology has failed.<\/jats:p>","DOI":"10.1145\/3341717","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["An efficient algorithm for type-safe structural diffing"],"prefix":"10.1145","volume":"3","author":[{"given":"Victor Cacciari","family":"Miraldo","sequence":"first","affiliation":[{"name":"Utrecht University, Netherlands"}]},{"given":"Wouter","family":"Swierstra","sequence":"additional","affiliation":[{"name":"Utrecht University, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118232.3118518"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628158"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54494-5_9"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/829519.830817"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"volume-title":"Advanced Data Structures (1 ed.)","author":"Brass Peter","key":"e_1_2_2_6_1"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.08.003"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2633628.2633634"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394560"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2364506.2364522"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2642937.2642982"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159876.1159880"},{"key":"e_1_2_2_13_1","unstructured":"GHC Trac. 2018. Memory usage exploding for complex pattern matching. (2018). https:\/\/ghc.haskell.org\/trac\/ghc\/ticket\/ 14987#no2 .  GHC Trac. 2018. Memory usage exploding for complex pattern matching. (2018). https:\/\/ghc.haskell.org\/trac\/ghc\/ticket\/ 14987#no2 ."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001106"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/229593.229595"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/647908.740125"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645938.671208"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596614.1596624"},{"volume-title":"Developments in Language Theory","author":"Lohrey Markus","key":"e_1_2_2_20_1"},{"volume-title":"{n. d.}. Handbook of Applied Cryptography (boca raton, xiii, 780","year":"1997","author":"van Oorschot Paul","key":"e_1_2_2_21_1"},{"volume-title":"Advances in Cryptology \u2014 CRYPTO \u201987","author":"Merkle Ralph C.","key":"e_1_2_2_22_1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535851"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2013.09.018"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240719.3241790"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122975.3122976"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240719.3241786"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1088348.1088349"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3242744.3242745"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661136.2661137"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976022.2976026"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/293677.293678"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103786.2103795"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341717","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:24Z","timestamp":1750207404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":33,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341717"],"URL":"https:\/\/doi.org\/10.1145\/3341717","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}