Loading...
Please wait, while we are loading the content...
The Concatenate Vanishes (1987)
| Content Provider | CiteSeerX |
|---|---|
| Author | Wadler, Philip |
| Abstract | This note presents a trivial transformation that can eliminate many calls of the concatenate (or “append”) operator from a program. The general form of the transformation is well known, and one of the examples, transforming the reverse function, is a classic. However, so far as I am aware, this style of transformation has not previously been systematised in the way done here. The transformation is suitable for incorporation in a compiler, and improves the asymptotic time complexity of some programs from quadratic to linear. There is a syntactic test that determines when the transformation will succeed in eliminating a concatenate operation. Section 1 describes the transformation. Section 2 presents examples. Section 3 characterises the transformation’s benefits. Section 4 describes related work. Section 5 concludes. 1 The transformation First, some notational preliminaries. We write concatenate as infix +, list construction (cons) as infix:, and the empty list as []. We write [x, y, z] as an abbreviation for x: (y: (z: [])). We will make use of the following laws: (1) [ ] + x = x (2) (x: y) + z = x: (y + z) (3) (x + y) + z = x + (y + z) Laws (1) and (2) provide a recursive definition of concatenate. Law (3) states that concatenate is associative; it may be proved from laws (1) and (2). We now describe the transformation. The key idea is that whenever an application of a function f may appear as the left argument of a concatenation, then we introduce a new function f ′ , satisfying the property |
| File Format | |
| Language | English |
| Publisher Date | 1987-01-01 |
| Access Restriction | Open |
| Subject Keyword | Concatenate Vanishes Following Law Reverse Function Asymptotic Time Complexity List Construction Present Example New Function Many Call Trivial Transformation Key Idea Notational Preliminary Describes Related Work Transformation First Recursive Definition General Form Empty List Syntactic Test Left Argument Concatenate Operation |
| Content Type | Text |
| Resource Type | Technical Report |
