lists:partition/2

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Raimo Niskanen-3
Hello,

I am missing function in the module lists, one that using a predicate
partitions a list into two; one with all elements for which the
predicate was true, and one for the rest, while preserving the ordering
of the elements.

It could be defined as follows:

        partition(Pred, List) ->
            partition(Pred, List, [], []).

        partition(Pred, [], ListTrue, ListFalse) ->
            {reverse(ListTrue), reverse(ListFalse)};
        partition(Pred, [H | T], ListTrue, ListFalse) ->
            case Pred(H) of
                true ->
                    partition(Pred, T, [H | ListTrue], ListFalse);
                false ->
                    partition(Pred, T, ListTrue, [H | ListFalse])
            end.

This could be accomplished with lists:foldr/3 like this:

        partition(Pred, List) ->
            foldr(
                fun(Element, {ListTrue, ListFalse}) ->
                    case Pred(Element) of
                        true ->
                            {[Element | ListTrue], ListFalse};
                        false ->
                            {ListTrue, [Element | ListFalse]}
                    end
                end,
                {[], []},
                List).
               
The latter one is unfortunately not tail recursive, and it is less
efficient because it assembles / disassembles a tuple in each loop
recursion.

The questions are: is partition/2 sucha a useful function that it is
worthy of being included in the lists module, and are there any comments
on the implementation?

/ Raimo Niskanen, Ericsson UAB, Erlang/OTP.


Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Martin Bjorklund-2
Raimo Niskanen <raimo> wrote:
> Hello,
>
> I am missing function in the module lists, one that using a predicate
> partitions a list into two; one with all elements for which the
> predicate was true, and one for the rest, while preserving the ordering
> of the elements.

> The questions are: is partition/2 sucha a useful function that it is
> worthy of being included in the lists module,

yes, definitely!  i've (re)implemented it many times...

> and are there any comments on the implementation?

use the first one.  also, maybe you could add a function that doesn't
preserve the order.


/martin


Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Luke Gorrie-3
In reply to this post by Raimo Niskanen-3
Raimo Niskanen <raimo> writes:

> Hello,
>
> I am missing function in the module lists, one that using a predicate
> partitions a list into two; one with all elements for which the
> predicate was true, and one for the rest, while preserving the ordering
> of the elements.

Yes yes!

And here are a few other functions I've written lots of times:

  %% For 'lists'
  %% separate(X, L):
  %% Separate the elements of the list L by placing X between them.
  %% e.g.: lists:flatten(separate(", ", ["foo", "bar", "baz"]))
  %%         => "foo, bar, baz"
  separate(X, [])    -> [];
  separate(X, [H])   -> [H];
  separate(X, [H|T]) -> [H,X|separate(X, T)].

  %% For 'lists'
  %% first(Pred, List)
  %% Find the first element of List satisfying Pred.
  %% Returns: {value, Item} | false
  first(Pred, []) ->
      false;
  first(Pred, [H|T]) ->
      case Pred(H) of
          true ->
              {value, H};
          false ->
              first(Pred, T)
      end.

  %% For 'io_lib'
  %% Very simple, but it's amazing how often
  %% lists:flatten(io_lib:format(..)) makes me go over the 80-column
  %% boundry :)
  flatformat(Fmt, Args) ->
      lists:flatten(io_lib:format(Fmt, Args)).

I know that you can do the 'first' with 'dropwhile' and so on, but I'd
still like to have these :-)

P.S. it's very nice that the latest erlang's lists:sort can take a
predicate!

Cheers,
Luke



Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Daniel Néri-2
Luke Gorrie <luke> writes:

>   %% separate(X, L):
>   %% Separate the elements of the list L by placing X between them.

This one is called `intersperse' in the Haskell library, which could
maybe also serve as inspiration for other additions to the lists
module:

    http://www.haskell.org/onlinelibrary/list.html


Regards,
   ---Daniel

PS. BTW, could we please drop the plural `s' from `lists', `sets' and
    `ordsets'?

--
Daniel Neri                                      mailto:dn
Sigicom AB, Sweden                              http://www.sigicom.com



Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Samuel Elliott
On 17/01, Daniel Neri wrote:
| Luke Gorrie <luke> writes:
|
| >   %% separate(X, L):
| >   %% Separate the elements of the list L by placing X between them.
|
| This one is called `intersperse' in the Haskell library, which could
| maybe also serve as inspiration for other additions to the lists
| module:

and `join' in Perl and many other languages.




Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Luke Gorrie-3
Samuel Tardieu <sam> writes:

> On 17/01, Daniel Neri wrote:
> | Luke Gorrie <luke> writes:
> |
> | >   %% separate(X, L):
> | >   %% Separate the elements of the list L by placing X between them.
> |
> | This one is called `intersperse' in the Haskell library, which could
> | maybe also serve as inspiration for other additions to the lists
> | module:
>
> and `join' in Perl and many other languages.

There is something fun about different people deciding on the names
"separate" and "join" for the same function. :-)

Cheers,
Luke



Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Robert Virding-4
In reply to this post by Luke Gorrie-3
Luke Gorrie <luke> writes:

>And here are a few other functions I've written lots of times:
>
>  %% For 'lists'
>  %% separate(X, L):
>  %% Separate the elements of the list L by placing X between them.
>  %% e.g.: lists:flatten(separate(", ", ["foo", "bar", "baz"]))
>  %%         => "foo, bar, baz"
>  separate(X, [])    -> [];
>  separate(X, [H])   -> [H];
>  separate(X, [H|T]) -> [H,X|separate(X, T)].
>
>  %% For 'lists'
>  %% first(Pred, List)
>  %% Find the first element of List satisfying Pred.
>  %% Returns: {value, Item} | false
>  first(Pred, []) ->
>      false;
>  first(Pred, [H|T]) ->
>      case Pred(H) of
>          true ->
>              {value, H};
>          false ->
>              first(Pred, T)
>      end.

The name is not 'first' is not very good to use for such a function.
There is a function pair hd/tl (head/tail) which return the first
element of a list and the other elements.  There is also a function
'last' which returns the last element of a list.  To have some form of
name symmetry the function which returns all the elemnts except for the
last should be called 'first'.

There has been some wimpish grumbling that a name like 'first' is not
very obvious for a function like that.  The has been suggestions like
'but_last'.  Can't understand the problem myself. :-)  Anyway many
other functional libraries have 'first'.

        Robert




Reply | Threaded
Open this post in threaded view
|

lists:partition/2

Robert Virding-4
In reply to this post by Raimo Niskanen-3
Raimo Niskanen <raimo> writes:

>Hello,
>
>I am missing function in the module lists, one that using a predicate
>partitions a list into two; one with all elements for which the
>predicate was true, and one for the rest, while preserving the ordering
>of the elements.
>
>It could be defined as follows:
>...
>This could be accomplished with lists:foldr/3 like this:
>...
>        
>The latter one is unfortunately not tail recursive, and it is less
>efficient because it assembles / disassembles a tuple in each loop
>recursion.

A function like partition would be useful.

The latter may not be tail recursive (because foldr is not) but it may
not be so much more inefficient as you save doing to reverses.  In
terms of memory they are almost equal.

        Robert