haskell - 列表的头部可以代表多个值吗

Question

如果我调用函数 interleave (定义如下 - 这是一个在列表的每个位置插入一个数字(或任何类型)的函数)像这样结果列表的长度都相同

interleave 1 [2,3,4]
[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]]

但是，由于对 interleave 的递归调用，我预计列表长度会越来越短。通过列表减去头部(即只有 ys )。由于每次调用列表的尾部都会变得更短，因此我希望生成的列表更短。

interleave :: a -> [a] -> [[a]]
interleave x []     = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)

如果递归调用的列表参数越来越短，列表如何最终保持相同的长度？

我能想象的唯一答案是映射值 map (y:)代表递归调用中的一个以上数字(即它是 [2,1,3,4] 中的 2 和 [2,3,1,4] 中的 2,3 和 [2,3, 中的 2,3,4， 4,1]` 但我不确定这是否可行，我不知道如何在 haskell 执行期间记录值。

问题，换句话说，可以 y (列表的头部)在递归调用中代表多个值？

在回答问题时(如果相关)，请确认/解释 (x:y:ys)在 (x:y:ys) : map (y:) (interleave x ys)只代表一个列表(即它是 [1,2,3,4- ，整数参数插入第一个位置)。

(如果您可以显示 func 的执行顺序，或者值如何存储在堆栈中，这可能会有所帮助)

Answer 1

递归调用的列表长度确实越来越短；但是，该函数会修改递归调用的结果以延长它们。让我们从底层建立起来。对于空列表，没有什么有趣的事情发生:

interleave 1 []
= { first clause of definition }
[[1]]

但是当我们得到一个只有一个元素的列表时，我们已经看到了有趣的事情发生了。具体来说，由于递归调用的结果传递给 map (y:) ，递归调用生成的短列表每个都扩展了一个元素。

interleave 1 [4]
= { list syntax }
interleave 1 (4:[])
= { second clause of definition }
(1:4:[]) : map (4:) (interleave 1 [])
= { recursive call, which produces short answers }
(1:4:[]) : map (4:) [[1]]
= { definition of map, which lengthens each answer }
(1:4:[]) : [4:[1]]
= { list syntax }
[[1,4],[4,1]]

类似地， interleave 1 [3,4]进行递归调用 interleave 1 [4]生产 [[1,4],[4,1]] ，但随后使用 map (3:)将其中的每个元素加长到 [[3,1,4],[3,4,1]] .

现在依次回答您的直接问题:

How do the lists end up being the same length if the list argument to the recursive call is increasingly shorter?

每次对较短列表进行递归调用时，递归调用的结果都会变长——这些结果完全平衡，因此调用 interleave带长度- n列表将产生一个长度为 n+1 的集合列表。

can y (the head of the list) represent more than a single value in the recursive calls?

不，列表的头部始终是单个值。真正的魔力是每个递归调用都添加到头部 - 因此您可以从许多递归调用中获得许多额外的头部。

confirm/explain if the (x:y:ys) in (x:y:ys) : map (y:) (interleave x ys) only ever represents one list (i.e. it is the [1,2,3,4- with the integer argument inserted in the first position).

正确的。