Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I completely flatten a list (of lists (of lists) ... )

Tags:

list

flatten

raku

I was wondering about how I could completely flatten lists and things that contain them. Among other things, I came up with this solution that slips things that have more than one element and puts them back, or takes things with one element after slipping it.

This is a bit different than How do I “flatten” a list of lists in perl 6?, which doesn't completely flat because the task is to restructure.

But, maybe there's a better way.

my @a  = 'a', ('b', 'c' );
my @b  = ('d',), 'e', 'f', @a;
my @c  = 'x', $( 'y', 'z' ), 'w';

my @ab = @a, @b, @c;
say "ab: ", @ab;

my @f = @ab;

@f = gather {
    while @f {
        @f[0].elems == 1 ??
            take @f.shift.Slip
                !!
            @f.unshift( @f.shift.Slip )
        }
    }

say "f: ", @f;

This gives:

ab: [[a (b c)] [(d) e f [a (b c)]] [x (y z) w]]
f: [a b c d e f a b c x y z w]

Curiously, I also read some python answers:

  • Making a flat list out of list of lists in Python
  • How flatten a list of lists one step
  • flatten list of lists of lists to a list of lists

itertools.chain(*sublist) look interesting, but the answers were either recursive or limited to two levels from hard-coding. The functional languages were recursive in the source code, but I expected that.

like image 596
brian d foy Avatar asked Jan 14 '17 08:01

brian d foy


People also ask

How do I make a flat list out of a list of lists?

Flatten List of Lists Using sum. Summing over inner lists is another solution. The function has two parameters: iterable which is a list of lists and start which is an empty list in our case that serves as the initial flat list to which items of the inner sublists are added.

How do I convert a list to one list?

Using sum() Function The sum() function will add the list elements inside of lists and return a single list. To convert lists of lists into a single list, we will add the nested list into an empty list to get a regular list.


2 Answers

Unfortunately there's no direct built-in that completely flattens a data structure even when sub-lists are wrapped in item containers.

Some possible solutions:

Gather/take

You've already come up with a solution like this, but deepmap can take care of all the tree iteration logic to simplify it. Its callback is called once for every leaf node of the data structure, so using take as the callback means that gather will collect a flat list of the leaf values:

sub reallyflat (+@list) { gather @list.deepmap: *.take }

Custom recursive function

You could use a subroutine like this to recursively slip lists into their parent:

multi reallyflat (@list) { @list.map: { slip reallyflat $_ } }
multi reallyflat (\leaf) { leaf }

Another approach would be to recursively apply <> to sub-lists to free them of any item containers they're wrapped in, and then call flat on the result:

sub reallyflat (+@list) {
    flat do for @list {
        when Iterable { reallyflat $_<> }
        default       { $_               }
    }
}

Multi-dimensional array indexing

The postcircumfix [ ] operator can be used with a multi-dimensional subscript to get a flat list of leaf nodes up to a certain depth, though unfortunately the "infinite depth" version is not yet implemented:

say @ab[*;*];     # (a (b c) (d) e f [a (b c)] x (y z) w)
say @ab[*;*;*];   # (a b c d e f a (b c) x y z w)
say @ab[*;*;*;*]; # (a b c d e f a b c x y z w)
say @ab[**];      # HyperWhatever in array index not yet implemented. Sorry.

Still, if you know the maximum depth of your data structure this is a viable solution.

Avoiding containerization

The built-in flat function can flatten a deeply nested lists of lists just fine. The problem is just that it doesn't descend into item containers (Scalars). Common sources of unintentional item containers in nested lists are:

  • An Array (but not List) wraps each of its elements in a fresh item container, no matter if it had one before.

    • How to avoid: Use Lists of Lists instead of Arrays of Arrays, if you don't need the mutability that Array provides. Binding with := can be used instead of assignment, to store a List in a @ variable without turning it into an Array:
      my @a  := 'a', ('b', 'c' );
      my @b  := ('d',), 'e', 'f', @a;
      say flat @b; # (d e f a b c)
  • $ variables are item containers.

    • How to avoid: When storing a list in a $ variable and then inserting it as an element into another list, use <> to decontainerize it. The parent list's container can also be bypassed using | when passing it to flat:
      my $a = (3, 4, 5);
      my $b = (1, 2, $a<>, 6);
      say flat |$b; # (1 2 3 4 5 6)
like image 69
smls Avatar answered Oct 23 '22 18:10

smls


I'm unaware of a built-in way to do so, though there very well might be (and if not, there probably should be).

The best I could come up with on short notice is this:

gather @ab.deepmap(*.take)

I'm not sure how gather/take interacts with the potentially parallelized evaluation of hyper operators, so the following alternative might not be safe to use, in particular if you care about element order:

gather @ab>>.take

You can put the code into square brackets if you need an array or reify it into a list via .list.

Lastly, this is the first solution rewitten as a retro-style subroutine:

sub deepflat { gather deepmap &take, @_ }
like image 22
Christoph Avatar answered Oct 23 '22 17:10

Christoph