How to write an `intersperse` function in Perl 6

Question

One thing I've been missing in Perl 6, is an intersperse function like Haskell has:

The intersperse function takes an element and a list and `intersperses' that element between the elements of the list.

E.g. this:

intersperse <X Y>, (<a b>, <c d>, <e f>);

...should return this sequence:

<a b>, <X Y>, <c d>, <X Y>, <e f>

So I've been trying to implement it myself as a custom function. For maximum re-usability, it should:

Support any kind of object (including List and Nil) as elements.
Not change the containerization of elements in any way.
Not flatten or otherwise affect the inner structure of elements in any way.
Return a lazy sequence if the input list is given as a lazy sequence, so that it can be used on infinite sequences, as in intersperse 42, 1..Inf.

What I've come up with so far, is this:

sub intersperse (\element, +list) {
    ((element xx *) Z list).map(|*)[1..*]
}

That is: Infinitely repeat the element to be interspersed, zip it with the list, then use map to slip each tuple so as to remove the layer of nesting added by the zip without flattening the original elements, and then use an array subscript to remove the leading repetition of the interspersed element.

It satisfies the requirements 1-3, but not 4, because the array subscript operates eagerly (i.e. fully iterates the input sequence and then returns a non-lazy List) and thus causes this function to hang when given an infinite sequence.

What would be a good way to implement this function so that it satisfies all 4 requirements?

Christoph Christoph · Accepted Answer · 2016-09-01T09:38:21

I'm not particularly happy with the solutions I've come up with, but here they go:

sub intersperse (\element, +list) {
    map { ((element xx *) Z list).map(|*)[$_] },
        1..(list.is-lazy ?? Inf !! list.elems * 2 - 1);
}

sub intersperse (\element, +list) {
    gather for list {
        FIRST .take, next;
        take slip element, $_;
    }
}

sub intersperse (\element, +list) {
    list.map({ slip element, $_ }) does role {
        method iterator {
            my \it = callsame;
            it.pull-one;
            it;
        }
    }
}

Perhaps it'll serve as inspiration for someone else to come up with something better...

How to write an `intersperse` function in Perl 6

1 Answers