Right turn list in Erlang
I am now familiar with Sequential Erlang (and the functional programming mindset). Therefore, I want to implement the following two functions without using BIF. One is left_rotate
(which I came up with for a solution) and the other is right_rotate
(which I ask 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 do not want to use BIF in this exercise. How can I achieve correct rotation?
A related question and a slightly more important question. How can I know if one of my implementations is efficient or not (i.e. avoid unnecessary recursion if I implement the same thing with BIF, etc.).
I think the BIF is built to provide some functionality to improve efficiency, that functional programming is not very good (or if we do them in a "functional way" the performance is not optimal).
source to share
First, your implementation is a little buggy (try with an empty list ...)
Secondly, 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, to compare 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 haven't tested the code, so take a critical look at it, just come up with it. Moreover, you may want to implement your own "reverse" function. This would be trivial with tail recursion. Why not give it a try?
source to share
The efficiency problem you are talking about has nothing to do with over-recursion (function calls are cheap) and anything to do with walking and rebuilding the list. Every time you add something to the end of the list, you have to walk around and copy the entire list, which is obvious from your append implementation. Thus, to rotate the list of N steps, we need to copy the entire list N times. We can use lists: split (as seen in one of the other answers) to do the whole turn in one step, but what if we don't know in advance how many steps we need to rotate?
A list is really not an ideal data structure for this task. Suppose we instead use a pair of lists, one for the head and one for the tail, then we can easily rotate moving items from one list to another.
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 like this. I wrote this without referencing it, so theirs are probably smarter.
source to share
If you're trying to think in functional terms, then perhaps consider implementing correct rotation in terms of your rotation:
rightrotate( List, 0 ) ->
List;
rightrotate( List, Times ) ->
lists:reverse( leftrotate( lists:reverse( List ), Times ) ).
Not to say that this is the best idea or something else :)
source to share
Your implementation will not be efficient as the list is not the correct representation to use if you need to reorder items, like rotating. (Imagine a round robin planner with many thousands of assignments, taking the front job and placing it at the end when you're done.)
So we are really just asking ourselves what it would be like in the least time to do this on lists. But then what qualifies as the overhead that we want to get rid of? Often you can save a little computation by going (highlighting) more objects or vice versa. In a computation, too, there can often be more than is required to preserve and preserve the distribution.
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, etc .; The above code will link directly to the final list. Very little rubbish. The final list is created as the package is unpacked. The cost is that we need more memory for the entire input list and list in the construct during this operation, but this is a short transitional thing. My damage from Java and Lisp forces me to focus on optimizing unnecessary needs, but in Erlang you don't risk a global full GC that kills every dream of real-time properties. Anyway, I like this approach in general.
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 Rev list, which is removed after we pass it to lists: reverse / 1 (it calls BIF lists: reverse / 2, but it doesn't do anything interesting). By creating this temporary inverted list, we avoid crossing the list twice. Once to create a list containing everything but the last item, and once to get the last item.
source to share
One quick comment on your code. I would change the name of the function you are calling append. In a functional context, append usually means adding a new list to the end of the list, not just one element. There is no point in adding confusion.
Like the lists mentioned: split is not a BIF, it is a library function written in erlang. That the BIF isn't really well defined.
Split or split-like solutions look good. As someone has already pointed out that a list is not the best data structure for this type of operation. Depends on what you are using it for.
source to share
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).
On 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
source to share