[erlang-questions] Fast binary reverse

Jachym Holecek freza@REDACTED
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) ->

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

	-- Jachym

More information about the erlang-questions mailing list