Write a function that takes a string and reverses its word order. So, "Reverse this string" results in "string this Reverse".
Notice that the task isn't to reverse the string, but rather to reverse the order of the string's words. So the first word becomes the last. The second word becomes the second to last, and so on.
Whenever I come across puzzles like this, I shudder when I start to think about the nested loops and pointer arithmetic. Unfortunately, that describes the classic solution pretty well. The common wisdom is that first you should reverse the entire string. Then you should go back and reverse each word. So:
The first step isn't bad, but reversing each word will require at least one nested loop, and some careful thinking about how to deal with the spaces. Instead, let's think through a functional solution that doesn't involve any loops. It will necessarily be recursive, so the first step will be to come up with each of the cases we'll encouter as we walk the string.
So, there are two accumulators. One grabs the letters of each word as we walk the string and keeps the letters in order (the word accumulator). Then, once an entire word has been read into the word accumulator, it's prepended to the string accumulator. Prepending, reverses the word order. Once it's prepended, the word accumulator is cleared in preparation for the next word. Let's translate this case by case.
The base case is the easiest. Let's start there:
```python Base Case if len(s) == 0:
return word_acc + str_acc
```
Start by testing if the input string, s, is empty. If it is, then we've reached the end of the string, so we return the contents of the word_acc, prepended to the str_acc. word_acc contains the last word in the string, and we're prepending it to the rest of the string that has already been reversed.
Now let's deal with the second recursive case:
```python 2nd Recursive Case elif s[0] == " ":
return helper(s[1:], "", " " + word_acc + str_acc)
```
If we've gotten this far, the input string must have some length, so we check if the first character is a space. If it is, we've reached the end of a word, so we need to prepend str_acc with the word that's just been read in (word_acc). We then clear out the word_acc in preparation for the next word, and recursively call the function with the rest of the input string, s. The recursive call is to helper because this will be nested inside a convenience wrapper that only takes one argument.
Finally, the last case:
```python 1st Recursive Case else:
return helper(s[1:], word_acc + s[0], str_acc)
```
If we've gotten this far, we're in the midst of a word (the string isn't empty, and the current character isn't a space). In this case, we add the current character onto the word_acc and then recurse with the rest of the string. Remember, the word_acc is building up each word character by character as we walk the input string.
Finally, we can simply throw these cases into a function, and it should just work. Ahh, the magic of recursion.
```python Reversing Word Order def rev_words(s):
'''Returns the string `s` with its words in the reverse order.
Example: rev_words("Reverse this!") #"this! Reverse"
'''
def helper(s, word_acc, str_acc):
# Base case: Return word accumulator plus whatever words
# you have in the string acc
if len(s) == 0:
return word_acc + str_acc
# This is the end of a word. Clear `word_acc`, and start with
# the next word.
elif s[0] == " ":
return helper(s[1:], "", " " + word_acc + str_acc)
# In the middle of a word. Add the letter to `word_acc`, and continue
else:
return helper(s[1:], word_acc + s[0], str_acc)
return helper(s, "", "")
```
As much as I like this solution, it's not without its drawbacks. The most significant is that Python's string methods are very slow. Each concatenation causes both strings to be copied, and at least one concat is happening for each character in the string. Possible solutions include turning the string into a list of characters (list methods are much faster), or using a language that better supports the functional paradigm.1 But really, if speed is your highest priority, the imperative solution of swapping characters in place is your best bet, warts and all.
If you'd like to play with this code yourself, I've posted a gist here, along with some tests.
Suppose you are programming in a language that only supports function application. That is, defining functions and applying arguments to these functions are the only things this language supports. Using only these building blocks, could you construct a linked list?
Surprisingly, the answer is yes, and the exercise linked to above provides a partial solution. Below, I've translated that solution into Python, and completed the exercise:
```python Solution in Python
def cons(l, r):
return lambda get: get(l, r)
def head(pair):
return pair(lambda l, r: l)
def tail(pair):
return pair(lambda l, r: r)
```
First, let's examine how these functions can be used, and then I'll explain how they work. Consider the snippet below:
python Usage Example
l1 = cons(1, 2)
print head(l1) # Prints 1
print tail(l1) # Prints 2
l2 = cons(0, l1)
print head(l2) # Prints 0
print head(tail(l2)) # Prints 1
print tail(tail(l2)) # Prints 2
As can be seen, cons() is the constructor for this pair type. Give it two values, and it will create a pair of those two values. head() and tail() are the basic operators that let us access values inside these pairs; they return the left and right element of the pair, respectively. Also notice that we can create pairs of pairs. The last half of the example creates a pair composed of 0 and (1,2). Why is this significant? Well, we've just made a linked list! Linked lists are simply pairs of pairs. The list [1,2,3,4] can, for example, be represented as cons(1,cons(2,cons(3,cons(4,None)))). What's None doing at the end of the list? You can think of it like the NULL pointer at the end of a linked list in C. If a function were traversing the list, None would signify to the function that it has reached the end. Mathematically, you can think of a linked list as an inductively defined data structure, where None is the base case. None is referred to as the empty list.
Now for the interesting part. How do these functions work? First let's look at the cons() function:
```python cons()
def cons(l, r):
return lambda get: get(l, r)
```
This takes in two parameters (l and r) and returns a function.1 This returned function takes yet another function, which it applies to l and r and returns the result. So, if we call cons(1,2), we are returned a function, which takes a function and applies that function to the arguments 1 and 2. If, for example, I called cons(1,2)(lambda x, y: x+y) I'd get 3, because the addition function would be applied to 1 and 2.
Now suppose that we didn't want to add l and r. Instead, we wanted to pull either l or r out of a pair that was already constructed. In other words, given list = cons(1,2), how could we pull the 1 or 2 out of the function stored in list? Well, all we need to do is pass it a function that returns only the left or right parameter. So, cons(1,2)(lambda l, r: l) would give us back 1, and cons(1,2)(lambda l,r: r) would give us back 2. This is almost exactly what the head() and tail() functions are doing! They take in a function (presumably produced by the cons() function), and apply either lambda l,r: l or lambda l,r: r. Just to cement this all together, below I step through the evaluation for the example head(cons(1,2)).
python Evaluation Steps for head(cons(1,2,))
head(cons(1,2))
-> head(lambda get: get(1, 2))
-> (lambda get: get(1, 2))(lambda l,r: l)
-> (lambda l,r: l)(1,2)
-> 1
And here is a bit of code that uses these new functions to add the elements of a list:
```python Sum Function def sum_list(l):
return head(l) if tail(l) == None else head(l) + sum_list(tail(l))
sum_list(cons(1,cons(2,cons(3,None)))) # Returns 6 ```
In the end, this might strike you as nothing more than a useless programming trick. In a sense that's right. I'd never use this in my own code. What makes this technique so valuable is that it actually fits into the broader context of lambda calculus, which is a mathematical abstraction of computation. In the language of lambda calculus, you're given only a very basic set of tools. Essentially all you have are simple one parameter functions (it doesn't even have integers!). Incredibly, it turns out that that's all you need for a Turing complete language. It's possible to build integers, conditionals, loops, arithmetic operations, and (as you've seen here) data structures out of these simple building blocks. As a next step, and to see this for yourself, it might be fun to take a minute and see how the code presented here could be modified to give you binary trees, or even graphs. After that, you could check out this incredible article on writing the infamous FizzBuzz exercise in Ruby using only functions.