dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Swierstra, W.S. | |
dc.contributor.author | Gorkum, Jort van | |
dc.date.accessioned | 2022-09-09T04:03:02Z | |
dc.date.available | 2022-09-09T04:03:02Z | |
dc.date.issued | 2022 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/42740 | |
dc.description.abstract | Incremental computation is a method which tries to save time by only recomputing the output of changed input. A technique of incremental computation is memoization. Memoization stores the result of a computation and returns the cached result when the same input occurs again. As a result, a large part of memoization becomes dependent on determining if the input is equal to an already cached input. This can become problematic when a computation is given a large recursive data structure. To improve the performance of memoization this paper introduces an incremental algorithm which determines the equality in constant time. This is accomplished by storing hash values/digests, which describe the internal structure, inside the data structure. Furthermore, the incremental algorithm describes how to efficiently update the digests, using a Zipper, when the data structure changes. The incremental algorithm is then implemented using Datatype-generic programming, to support the class of regular datatypes. Meanwhile, the usage of the generic implementation stays the same for the developers as writing the non-incremental algorithm in Haskell. Finally, we show that the performance is better than the non-incremental version with minimal extra memory usage, when correctly tuned with cache policies. | |
dc.description.sponsorship | Utrecht University | |
dc.language.iso | EN | |
dc.subject | Presents a generic incremental algorithm using datatype-generic programming, zippers and merkle trees, to improve performance for incremental processes while still having the same programming experience as the non-incremental algorithm. | |
dc.title | Generic Incremental Computation for Regular Datatypes in Haskell | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | incremental algorithm, datatype-generic programming, zipper, merkle tree, generic, regular datatypes, cache policies, pattern synonyms | |
dc.subject.courseuu | Computing Science | |
dc.thesis.id | 10390 | |