列表上的哪些函数满足连接法则？

Question

哪些函数f :: [a] -> [a]满足定律：

f . concat = concat . f . map f

我能想到id、、reverse还有const []-还有其他的吗？

Answer 1

没有其他满足法律的（终止）函数。下面是一个尝试的证明，请大家戳破。

如果f丢弃任何元素（但不是全部），则违反法律。

事实上，可以说从特定 length 的输入中f删除带有索引的元素，但保留一些其他元素。然后它在列表上失败（索引处的非空列表，总共列出）：返回一个非空列表，而返回一个空列表。il[[], [], ..., [0..l-1], [], ...]ilf . concatconcat . f . map f

如果f复制任何元素，就违反了法律。

假设在特定长度的输入上将f具有索引的元素复制i有限次。然后它在与上面相同的列表上失败：返回一个出现 的列表，而返回一个出现 的列表。k > 1lf . concatkiconcat . f . map fk**2i

因此f必须删除所有元素（即 be const []）或重新排列元素。我们来分析一下后一种情况。

将每个输入长度视为f一个函数族、一个单独的函数是很方便的。假设是第一个既不是也不是 的，那么它会失败。f_llf_kidreverse[[1], [2..k]]

如果允许非终止，则不复制属性不成立（k可能是无限的）并且附加函数（例如f [] = []; f (x:_) = repeat x）满足定律。