[erlang-questions] Fast binary reverse

Jachym Holecek <>
Thu Oct 27 13:42:25 CEST 2011


# Antoine Koener 2011-10-27:
> Keep in mind that lists:reverse does not reverse a list, but instead change
> the walking direction and the starting point...

There's no distinguished starting point in a list, every element is as good
as any. And by definition there's only one possible direction of traversal.
Doubly linked lists, which is what you're referring to, are a different data
structure with different properties and wouldn't be a reasonable choice for
implementation of lists.

List reversal works basically like this (only it's done in C):

  rev(L) ->
      rev(L, []).

  rev([H | T], L) ->
      rev(T, [H | L]);
  rev([], L) ->
      L.

See erts/emulator/beam/erl_bif_lists.c:lists_reverse_2() for details.

BR,
	-- Jachym



More information about the erlang-questions mailing list