[erlang-questions] Sorting a list according to another list

Ulf Wiger (TN/EAB) ulf.wiger@REDACTED
Wed Apr 23 11:12:12 CEST 2008


Alexander Lamb skrev:
> Hello List,
> 
> I have a list of tuples:
> 
> [ {Type,Item,Value}, ... ]
> 
> that I would like to sort according to another list of tuples, using  
> Type and Item as keys.
[...]
> 
> Isn't this a very common situation?

I've come across it every once in a while...

I guess there are a few different scenarios:

A The unsorted list must only contain keys that are
   in the reference list
B Items not found in the reference list can be appended
   to the sorted list
C The list to be sorted is "semi-sorted", in that the
   algorithm should preserve order as far as possible
...

A fairly complex version of C can be found in
systools_make:sort_appls/1 in OTP's SASL application.
It tries to sort a list of applications, preserving
the existing order as far as possible, while still
preserving dependency restrictions.

A version of B could be (not tested or compiled):

sort(L, Keys, KeyPos) ->
   {Sorted, Tail} =
    lists:foldl(
       fun(K, {L1, Rest}) ->
         {L1 ++ [X || X <- Rest,
                      element(KeyPos,X) == K],
          [X || X <- Rest,
                element(KeyPos,X) =/= K]}
       end, {[], L}, Keys),
   Sorted ++ Tail.

AFAIK, lists:keytake/3 only exists in OTP R12B.
lists:keydelete/3 only deletes the first occurrence
of the key.

BR,
Ulf W



More information about the erlang-questions mailing list