Programming Praxis

We have today our third essay: SRFI-41 Streams. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

Today’s essay describes a data structure that is fundamental to functional programming languages. Streams, also known as lazy lists, are a sequential data structure containing elements computed only on demand. A stream is either null or is a pair with a stream in its cdr. Since elements of a stream are computed only when accessed, streams can be infinite. Once computed, the value of a stream element is cached in case it is needed again. Streams without memoization were first described by Peter Landin in 1965. Memoization became accepted as an essential feature of streams about a decade later. Today, streams are the signature data type of functional programming languages such as Haskell.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

When I made the list of heap algorithms in the previous exercise, I realized that we don’t have an implementation of what is probably the most common form of heaps, the mutable heaps of imperative languages implemented in an array x. The basic idea is to arrange the items in the array so the largest is at index 1, and each item x_i is greater than x_2i and x_2i+1 (that’s a max-heap—a min-heap with the smallest item at the root has the sense of the comparison reversed).

A heap stored sub-array x_1..n−1 is unlikely to remain a heap if a new item is placed at x_n. The siftup function restores the heap property to x_1..n by repeatedly swapping the item at x_n with its parent at x_n/2 until it reaches its proper place in the heap.

The siftdown operation takes a heap stored in a sub-array x_1..n in which the item at x₁ is out of place and restores the heap property to x_1..n by repeatedly swapping the out-of-order item with its lesser child until it reaches the proper place in the array.

Given the siftup and siftdown operations, sorting an array is easy. First, for each item from the second to the last, sift it up to its proper position, forming a heap in x_1..n. Then, swap each item from the last to the second with the first item and sift the new first item down to its proper position in the heap.

Your task is to write functions that implement the siftup, siftdown, and heapsort procedures. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have implemented heaps (priority queues) using several different methods: leftist heaps, pairing heaps, maxiphobic heaps, binomial heaps. Today, we implement heaps using splay trees, based on an implementation in Chris Okasaki’s book Purely Functional Data Structures, which is a favorite of Programming Praxis.

Splay trees are perhaps the most famous and successful of all amortized data structures. Splay trees are a close relative of balanced binary search trees, but they maintain no explicit balance information. Instead, every operation blindly restructures the tree using some simple transformations that tend to increase balance. Although any individual operation can take as much as O(n) time, … every operation runs in O(log n) amortized time.

Okasaki explains that splay trees are inconvenient to implement in functional languages because the tree is restructured even during queries, which makes splay trees awkward to use because both the tree and the value must be returned during lookup. However, a heap only queries its minimum item, a limitation that makes it easy to implement heaps using splay trees in a functional setting.

To insert an item in a splay heap, partition the existing heap into two subtrees, one containing all elements less than or equal to the new element and one containing all elements greater than the new element, then construct a new splay tree with the new element at its root. Partitioning performs a right rotation every time it follows two left branches in a row, which reduces the depth of every node in the search path by half, thus maintaining the approximate balance of the tree.

The smallest node in a splay tree is the leftmost node in the tree, which is easy to find by following left paths, performing no restructurings along the way. Deleting the smallest node is done by traversing the path to the leftmost node, performing restructurings along the way in the same manner as partitioning.

Your task is to implement priority queues using splay heaps; you should provide insert, findMin and deleteMin operators. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is Problem A from the Google Code Jam Beta 2008. The problem is to accept three points as input, determine if they form a triangle, and, if they do, classify it at equilateral (all three sides the same), isoceles (two sides the same, the other different), or scalene (all three sides different), and also classify it as acute (all three angles less than 90 degrees), obtuse (one angle greater than 90 degrees) or right (one angle equal 90 degrees).

Your task is to write the triangle classifier. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

A common format for data storage is the CSV format for comma-separated values. A common format for data presentation is HTML for browsers using tables.

Your task is to write a function that reads a file in CSV format and translates it to a table in HTML format. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We have today our second essay: Text File Databases. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

Today’s essay provides a library that makes it convenient to read, write, transform and summarize files of data in ascii-text format. An astonishing amount of data is available in such formats, and doubtless a large percentage of computing power is expended in processing such files, so it makes sense to have a powerful library of easy-to-use functions for handling those files. I have personally been using some-or-another variant of this library for at least a dozen years, and can’t imagine how much time it has saved me in all those years.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

This question appears regularly at beginning-programmer discussion sites:

Write a function that takes a floating point number f and an integer n and rounds the floating point number to n places after the decimal point. For instance, given the floating point number 1000/7, rounding to 3 places would produce 142.857, rounding to 2 places would produce 142.86, rounding to 1 place would produce 142.9, and rounding to 0 places would produce 143. For extra credit, allow n to be negative, indicating rounding before the decimal point; for instance, rounding 1000/7 to -1 places would produce 140.

It’s not fair to use a built-in round function if your language provides one.

Your task is to write the function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is an interview question. It’s not hard, but it’s unusual enough that it took several minutes before I knew what to do.

Consider a list of four points on a plane; the points have integral coordinates, and their order is irrelevant. The four points determine a square if the distances between them are all equal, and the lengths of the two diagonals are also equal. For instance, the following lists are all squares:

(0,0), (0,1), (1,1), (1,0) -- the unit square
(0,0), (2,1), (3,-1), (1, -2) -- square not aligned to axis
(0,0), (1,1), (0,1), (1,0) -- unit square, in different order

And the following lists do not represent squares:

(0,0), (0,2), (3,2), (3,0) -- rectangle
(0,0), (3,4), (8,4), (5,0) -- rhombus
(0,0), (0,0), (1,1), (0,0) -- degenerate
(0,0), (0,0), (1,0), (0,1) -- degenerate

The degenerate square that consists of four repetitions of a single point may be considered either square, or not.

Your task is to write a function that determines if four input points determine a square. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

As we begin the new year, we note that 109-8*7+654*3-2/1 = 2013. There are three other combinations of the numbers 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, in order, combined with the five operators NIL, +, -, * and / that also evaluate to 2013.

Your task is to write a program that finds all four expressions that evaluate to 2013. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2