Reinventing the Wheel, Part I: String Reverse Algorithm

A string reverse algorithm takes a string of characters, and produces a string with the characters in reverse order.

In doing this, we could

• use a more high-level C++ approach,

std::string reverse(const std::string &str);

// ...

std::string reversed = reverse("uncategorized");
printf(reversed);                                 // dezirogetacnu

where the function returns a reversed copy of the original string. (Btw, to reverse a std::string, use the std::reverse algorithm, see bottom of this post.)

Alternatively, we can

• write a C-styled function, using a "raw" pointer and then modify the string, in-place:

void reverseInPlace(char *str);

// ...

char s[] = "november";
reverseInPlace(s);
printf(s);                                // rebmevon

Since we are going for minimal memory footprint and optimal performance, we will pursue the latter approach.

The Meaning and Usefulness of Closures

In the previous post, I talked about the Fixed Point Combinator in λ-Calculus, and mentioned that combinator is another word for a closed lambda term, i.e., an expression with no free variables:

λx.x, λxy.x, λxy.y, etc.

Take for example the term λxy.y, which is really shorthand for λx.λy.y:

FV(λx.λy.y)   =   FV(λy.y) − {x}   =   FV(y) − {y} − {x}   =   {y} − {y} − {x}   =   Ø.

The opposite of a combinator – any expression that uses free variables, is called a closure. Even though the meaning of the term is slightly different in different contexts, the idea is basically the same:

Examining the term λx.(f x), we have the free variables FV(λx.f x) …

= FV(f x) − {x} = FV(f) ∪ FV(x) − {x} = {f} ∪ {x} − {x} = {f, x} − {x}
= {f}.

In Haskell, the definition for a function, func:

func f = \x -> f x

… uses the variable f, bound outside of the abstraction. It is therefore a closure.

The Pattern of Recursion and Fixed Point Combinators

Recursion is an interesting, and important computation tool that enables us to formulate patterns of self-similarity and express infinity, using a finite set of elements. There is a strong relation between recursion and the principle of induction in mathematics. Imperative programming languages usually allow recursion in a program to take place by letting us define a function that calls itself. Here is a simple recursive function in C++:

#include <iostream.h>

void count(int n)
{
    std::cout << "Counting: " << n << "\n";
    if (n < 5) {
        count(n+1);
    }
}

int main(int argc, char **argv)
{
    count(1);
    return 0;
}

Run this example from codepad:
http://codepad.org/YmxQcTIX

In functional programming, recursion has a much more central position. Purely functional languages do not define any looping constructs, but instead rely entirely on recursion to achieve iterative algorithms. Many data types are defined recursively. In Haskell, recursion even allows us to define (conceptually) infinite data structures:

n = 5 : n
take 3 n                -- [5, 5, 5]

Codepad: http://codepad.org/sRbFkSH5

Here, we take the first three elements from an infinite list of fives. The list n is defined as a single element, 5, followed by a list – itself.

n is a 5, followed by n, which is a 5 followed by n, which is a 5 followed …