Bottom-up computation using trees of sublists
Some top-down problem specifications, if executed, may compute sub-problems repeatedly. Instead, we may want a bottom-up algorithm that stores solutions of sub-problems in a table to be reused. How the table can be represented and efficiently maintained, however, can be tricky. We study a special case: computing a function h taking lists as inputs such that hxs is defined in terms of all immediate sublists of xs . Richard Bird studied this problem in 2008 and presented a concise but cryptic algorithm without much explanation. We give this algorithm a proper derivation and discovered a key property that allows it to work. The algorithm builds trees that have certain shapes—the sizes along the left spine is a prefix of a diagonal in Pascal’s triangle. The crucial function we derive transforms one diagonal to the next.
Mon 13 OctDisplayed time zone: Perth change
16:00 - 17:40 | AlgorithmsICFP Papers / JFP First Papers at Orchid Plenary Ballroom Chair(s): Kimball Germane Brigham Young University | ||
16:00 25mTalk | Pushing the Information-Theoretic Limits of Random Access Lists ICFP Papers Edward Peters , Yong Qi Foo National University of Singapore, Michael D. Adams National University of Singapore DOI | ||
16:25 25mTalk | Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl) ICFP Papers DOI | ||
16:50 25mPaper | Bottom-up computation using trees of sublists JFP First Papers Shin-Cheng Mu Academia Sinica, Taiwan DOI | ||
17:15 25mPaper | You could have invented Fenwick treesRemote JFP First Papers Brent Yorgey Hendrix College DOI | ||
