2009-06-10

Post date: Jun 11, 2009 2:06:17 AM

Went over ralist in Assignment 3 solution.

    • ralist is analogous to binary representation of natural number (bignum) like singly linked list is analogous to unary representation.
      • Unary representation: empty string is zero, successor adds one by prepending a digit to the string, predecessor removes a digit from the beginning of the string.
      • Singly linked list represents a sequence of data by placing one element at each digit. Empty list is analogous to zero, cons analogous to successor, uncons (pattern matching) analogous to predessor.
      • Binary representation: still a list of digits, least significant digit first so carrying is easier to implement. Each digit is either odd (1) or even (0).
      • Random access list represents a sequence of data by grouping them into a forest of balanced binary trees. If the i-th digit is odd, then that digit carries a balanced binary tree of size 2i. The length of the data sequence is the binary number represented by odd and even.
      • Racons is analogous to successor (needs to build the tree by carrying) and rauncons to the predecessor (needs destruct by borrowing).
      • The easy way to implement ralookup and raupdate is to keep track of the indices skipped to the respective size of the trees, and to perform a binary tree lookup/update at the correct digit.
    • Alternative way to define ralist:
      • datatype ralist (a:t@ype) = Emp(a) | Odd(a) of (a, ralist '(a, a)) | Evn(a) of ralist '(a, a)
      • The idea is that we recursively form pairs as we go down the digits. The pairing guarantee completely balanced binary tree. The key to lookup and update is to treat the rest of the list indexed in pairs. This is the approach taken by the solution.
      • Efficient update, however, requires a "map" function f: a → a. At the very top level, it updates only an element. As we recurse down the digits, we build the pair update function f': '(a, a) → '(a, a), which takes a pair, and according to the index, updates either the left or the right a using f. To go down one more digit, the update function becomes f'': '('(a, a), '(a, a)) → '('(a, a), '(a, a)) and so on.

Briefly talked about stream, partial sum, and Euler's method. Eratosthenes sieve construction using lazy evaluated streams (straightforward adaptation to the non-lazy version).