right rotate a List in Erlang

Question

I am getting myself familiar to Sequential Erlang (and the functional programming thinking) now. So I want to implement the following two functionality without the help of BIF. One is left_rotate (which I have come up with the solution) and the other is right_rotate (which I am asking here)

-export(leftrotate/1, rightrotate/1).
%%(1) left rotate a lits
leftrotate(List, 0) ->
  List;
leftrotate([Head | Tail], Times) ->
  List = append(Tail, Head),
  leftrotate(List, Times -1).

append([], Elem)->
  [Elem];
append([H|T], Elem) ->
  [H | append(T, Elem)].

%%right rotate a list, how?
%%

I don't want to use BIF in this exercise. How can I achieve the right rotation?

A related question and slightly more important question. How can I know one of my implementation is efficient or not (i.e., avoid unnecessary recursion if I implement the same thing with the help of a BIF, and etc.)

I think BIF is built to provide some functions to improve efficiency that functional programming is not good at (or if we do them in a 'functional way', the performance is not optimal).

Answer 1

The efficiency problem you mention has nothing to do with excessive recursion (function calls are cheap), and everything to do with walking and rebuilding the list. Every time you add something to the end of a list you have to walk and copy the entire list, as is obvious from your implementation of append. So, to rotate a list N steps requires us to copy the entire list out N times. We can use lists:split (as seen in one of the other answers) to do the entire rotate in one step, but what if we don't know in advance how many steps we need to rotate?

A list really isn't the ideal data structure for this task. Lets say that instead we use a pair of lists, one for the head and one for the tail, then we can rotate easily by moving elements from one list to the other.

So, carefully avoiding calling anything from the standard library, we have:

rotate_right(List, N) ->
    to_list(n_times(N, fun rotate_right/1, from_list(List))).

rotate_left(List, N) ->
    to_list(n_times(N, fun rotate_left/1, from_list(List))).

from_list(Lst) ->
    {Lst, []}.

to_list({Left, Right}) ->
    Left ++ reverse(Right).

n_times(0, _, X) -> X;
n_times(N, F, X) -> n_times(N - 1, F, F(X)).

rotate_right({[], []}) ->
    {[], []};
rotate_right({[H|T], Right}) ->
    {T, [H|Right]};
rotate_right({[], Right}) ->
    rotate_right({reverse(Right), []}).

rotate_left({[], []}) ->
    {[], []};
rotate_left({Left, [H|T]}) ->
    {[H|Left], T};
rotate_left({Left, []}) ->
    rotate_left({[], reverse(Left)}).

reverse(Lst) ->
    reverse(Lst, []).
reverse([], Acc) ->
    Acc;
reverse([H|T], Acc) ->
    reverse(T, [H|Acc]).

The module queue provides a data structure something like this. I've written this without reference to that though, so theirs is probably more clever.

Answer 2

First, your implementation is a bit buggy (try it with the empty list...)

Second, I would suggest you something like:

-module(foo).

-export([left/2, right/2]).

left(List, Times) ->
    left(List, Times, []).

left([], Times, Acc) when Times > 0 ->
    left(reverse(Acc), Times, []);
left(List, 0, Acc) ->
    List ++ reverse(Acc);
left([H|T], Times, Acc) ->
    left(T, Times-1, [H|Acc]).

right(List, Times) ->
     reverse(foo:left(reverse(List), Times)).

reverse(List) ->
    reverse(List, []).

reverse([], Acc) ->
    Acc;
reverse([H|T], Acc) ->
    reverse(T, [H|Acc]).

Third, for benchmarking your functions, you can do something like:

test(Params) ->
    {Time1, _} = timer:tc(?MODULE, function1, Params),
    {Time2, _} = timer:tc(?MODULE, function2, Params),
    {{solution1, Time1}, {solution2, Time2}}.

I didn't test the code, so look at it critically, just get the idea. Moreover, you might want to implement your own "reverse" function. It will be trivial by using tail recursion. Why not to try?

Answer 3

If you're trying to think in functional terms then perhaps consider implementing right rotate in terms of your left rotate:

rightrotate( List, 0 ) ->
  List;
rightrotate( List, Times ) ->
  lists:reverse( leftrotate( lists:reverse( List ), Times ) ).

Not saying this is the best idea or anything :)

Answer 4

Your implementation will not be efficient since the list is not the correct representation to use if you need to change item order, as in a rotation. (Imagine a round-robin scheduler with many thousands of jobs, taking the front job and placing it at the end when done.)

So we're actually just asking ourself what would be the way with least overhead to do this on lists anyway. But then what qualifies as overhead that we want to get rid of? One can often save a bit of computation by consing (allocating) more objects, or the other way around. One can also often have a larger than needed live-set during the computation and save allocation that way.

---

first_last([First|Tail]) ->
  put_last(First, Tail).

put_last(Item, []) ->
  [Item];
put_last(Item, [H|Tl]) ->
  [H|put_last(Item,Tl)].

Ignoring corner cases with empty lists and such; The above code would cons the final resulting list directly. Very little garbage allocated. The final list is built as the stack unwinds. The cost is that we need more memory for the entire input list and the list in construction during this operation, but it is a short transient thing. My damage from Java and Lisp makes me reach for optimizing down excess consing, but in Erlang you dont risk that global full GC that kills every dream of real time properties. Anyway, I like the above approach generally.

---

last_first(List) ->
  last_first(List, []).

last_first([Last], Rev) ->
  [Last|lists:reverse(Rev)];
last_first([H|Tl], Rev) ->
  last_first(Tl, [H|Rev]).

This approach uses a temporary list called Rev that is disposed of after we have passed it to lists:reverse/1 (it calls the BIF lists:reverse/2, but it is not doing anything interesting). By creating this temporary reversed list, we avoid having to traverse the list two times. Once for building a list containing everything but the last item, and one more time to get the last item.

Answer 5

One quick comment to your code. I would change the name of the function you call append. In a functional context append usually means adding a new list to the end of a list, not just one element. No sense in adding confusion.

As mentioned lists:split is not a BIF, it is a library function written in erlang. What a BIF really is is not properly defined.

The split or split like solutions look quite nice. As someone has already pointed out a list is not really the best data structure for this type of operation. Depends of course on what you are using it for.

Answer 6

Left:

lrl([], _N) ->
  [];

lrl(List, N) ->
  lrl2(List, List, [], 0, N).

% no more rotation needed, return head + rotated list reversed
lrl2(_List, Head, Tail, _Len, 0) ->
  Head ++ lists:reverse(Tail);

% list is apparenly shorter than N, start again with N rem Len
lrl2(List, [], _Tail, Len, N) ->
  lrl2(List, List, [], 0, N rem Len);

% rotate one
lrl2(List, [H|Head], Tail, Len, N) ->
  lrl2(List, Head, [H|Tail], Len+1, N-1).

Right:

lrr([], _N) ->
  [];

lrr(List, N) ->
  L = erlang:length(List),
  R = N rem L,                        % check if rotation is more than length
  {H, T} = lists:split(L - R, List),  % cut off the tail of the list
  T ++ H.                             % swap tail and head