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

Question

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.

Answer 1

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)