Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorSwierstra, W.S.
dc.contributor.authorGorkum, Jort van
dc.date.accessioned2022-09-09T04:03:02Z
dc.date.available2022-09-09T04:03:02Z
dc.date.issued2022
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/42740
dc.description.abstractIncremental 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.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectPresents 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.titleGeneric Incremental Computation for Regular Datatypes in Haskell
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsincremental algorithm, datatype-generic programming, zipper, merkle tree, generic, regular datatypes, cache policies, pattern synonyms
dc.subject.courseuuComputing Science
dc.thesis.id10390


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record