如何在Perl 6中编写一个“intersperse”函数

Question

在Perl 6中，我一直缺少的一个功能是像Haskell一样的intersperse函数：Data.List.intersperse。

intersperse函数接受一个元素和一个列表，并在列表元素之间“插入”该元素。

例如：

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

应该返回这个序列:

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

所以我一直在尝试将其作为自定义函数实现。

为了最大限度地提高可重用性，它应该具备以下特点：

1. 支持任何类型的对象（包括列表和Nil）作为元素。
2. 不以任何方式改变元素的容器化。
3. 不会扁平化或以任何其他方式影响元素的内部结构。
4. 如果输入列表作为懒惰序列给出，则返回一个懒惰序列，使其可以用于无限序列，例如intersperse 42, 1..Inf。

到目前为止，我想到了这个：

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

那就是：无限重复要插入的元素，将其与列表压缩，然后使用map对每个元组进行slip，以去除由zip添加的嵌套层，而不会使原始元素扁平化，然后使用数组下标来删除插入元素的前导重复部分。

它满足1-3的要求，但不满足4，因为数组下标操作急切地（即完全迭代输入序列，然后返回非惰性列表），从而在给定无限序列时导致此函数挂起。

有什么好方法可以实现此函数，以便满足所有4个要求？

- smls

---

有趣。有点像join的List版本。 - Christopher Bottoms

Answer 1

我对我提出的解决方案并不是特别满意，但它们是这样的:

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;
        }
    }
}

也许它能激发别人想出更好的东西...

- Christoph

---

哎呀，第一个把它从O(n)变成了O(n²)，是吗？ - smls

“gather”/“take” 的方法似乎是一个不错的选择，我之前没有想到过。但我认为逗号运算符在 Perl 中并不能像在 C 语言中一样保证是一个序列点，所以我可能会将那一行代码写成 FIRST { take $_; next }。 - smls

好的，我不建议使用第一种方法：那只是我想出来让你的原始想法工作的方法；我怀疑可能有更好的方法来完成它，但对我来说并不是显而易见的；关于逗号运算符，它应该是安全的，因为它从左到右进行评估；我认为这实际上没有在任何地方记录 - 如果没有，应该有人这样做，并添加相应的spectest。 - Christoph

S03 http://design.perl6.org/S03.html#Sequence_points明确指出，依赖未被指定为序列点的运算符的顺序副作用是错误的。它没有说明逗号属于哪个类别，但我依稀记得几个月前Larry或其他人在IRC上说过，目前不能保证逗号是一个序列点。 - smls