Erlang In My Head (Part 2) – String Reversal, The Educational Way

This is the second in an irregular series of musings on Erlang, with references to Python. The main aim is to encourage me to use spare moments in the evening to look at aspects of Erlang. Hopefully my murmurings will be of interest to fellow Pythonistas (and maybe others!) as well as generate feedback from the Erlang community.

Spare time is a scarce commodity at the moment, so I decided the best way to get back into learning and using Erlang is to pick small, often trivial, tasks that can be solved in a few minutes, but which would hopefully yield enlightenment on a facet or two of the language.

One example is that contrived task of reversing a string. Both Python and Erlang have efficient in-built or library methods/functions for reversing lists and strings, but calling something like my_string.reverse() or lists:reverse() isn’t very educational.

In Python, one quick’n’dirty solution would be:

def reverse_string(my_string):
    new_string = ""
    for character in my_string:
        new_string = character + new_strin
    return new_string

I could also dust off my computer science skills and approach the problem recursively, without the need for new_string:

def reverse_string(my_string):
    if my_string:
         return reverse_string(my_string[1:]) + my_string[0]
    return ""

It works, but it doesn’t look as tidy as the first function. There’s also a limit on the depth of recursion, the CPython default of which (I believe) would restrict string size to about 1000 characters. Not a scalable solution.

Approaching the problem in Erlang using the first, iterative, approach is hampered by the fact I can only assign a variable to a value once. It might be possible to do it iteratively, but it would probably look as awkward as the recursive approach felt in Python.

Erlang treats strings as lists of numbers. While this means string handling is not as natural as it is in Python, it does offer us some help when approaching the reversal problem. My string is a list, and I can adopt the same approach as I did for the recursive Python function: append the head of the list to a reversed copy of the tail.

reverse_string([Head|Tail]) ->
    reverse_string(Tail) ++ [Head];
reverse_string([]) ->
    [].

My reverse_string function has two clauses. The first clause takes a list and splits it into a Head (the first element) and a Tail (everything else). It then concatenates the result of reverse_string(Tail) to the Head. Simple!

Or not. My first attempt suffered a gotcha: I was concatenating a list to an integer, which errored. Turning Head into a single item list, [Head], allowed the two to be concatenated.

The second clause deals with the case of an empty string. When you reach the end of the string your Tail will be empty, which matches this clause and ends our recursion. If you supplied an empty string initially, this would also match. Using an empty string “” instead of [] works equally as well, but I decided to keep things consistent with the list notation used in the first clause.

With this exercise complete, I’ll stick to lists:reverse in future.

Update: See https://metaljoe.wordpress.com/2009/09/13/erlang-in-my-head-part-2-1-feedback/

Advertisements

2 thoughts on “Erlang In My Head (Part 2) – String Reversal, The Educational Way

  1. Hi

    Your example is not tail recursive so thereis still a limit on string limit and recursion depth.

    I think this one shouldb be equvalent without any limit imposed on true recursion.

    reverse_string(Str) ->
    reverse_string(Str,[]).
    reverse_string([Head|Tail],Acc) ->
    reverse_string(Tail,Head++Acc);
    reverse_string([],Acc) ->
    Acc.

    Regads, Angel

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s