Haskell:函数应用程序分布在列表连接上是真的吗？

Question

看完这个问题后：Functional proofs (Haskell)

并且在查看 Haskell 音乐学院（第 164 页）的 forall xs ys. length (xs ++ ys) = length xs + length ys 的归纳证明之后。

在我看来，函数应用程序分布在列表连接上。

因此更普遍的规律可能是 forall f xs ys. f (xs ++ ys) = f xs ++ f ys.

但是如何prove/disprove这样的谓词呢？

-- 编辑--

我打错了，本来应该是：forall f xs ys. f (xs ++ ys) = f xs + f ys，这与上一个问题和 Haskell SoM 使用的相符。也就是说，由于这个错字，它不再是 "distributivity" 属性。但是，@leftaroundabout 为我最初打错字的问题做出了正确答案。至于我的预期问题，法律仍然不正确，因为功能不需要保留结构值。 f 可能会给出完全不同的答案，具体取决于它所应用的列表的长度。

Answer 1

不，这显然不是一般情况：

f [_] = []
f l = l

然后

f ([1] ++ [2]) = f [1,2] = [1,2]

但是

f [1] ++ f [2] = [] ++ [] = []

我确信确实有这个问题的函数形成了一个有趣的 class，但是一般函数可以对列表的结构做几乎任何事情，这会阻碍这种不变量。

Answer 2

And after looking at the inductive proof of forall xs ys. length (xs ++ ys) = length xs + length ys from the Haskell School of Music (page 164).

It seemed to me that function application distributes over list concatenation.

嗯，显然不是这样。例如：

reverse ([1..3] ++ [4..6]) /= reverse [1..3] ++ reverse [4..6]

您引用的示例是一种特殊情况，称为 幺半群态射 ：函数 f :: m -> n 使得：

m 和 n 是二元运算 <> 和恒等式 mempty;
f mempty = mempty
f (m <> m') == f m <> f m'

所以length :: [a] -> Int是一个幺半群态射，发送[]到0和++到+：

length [] = 0
length (xs ++ ys) = length xs + length ys

Haskell:函数应用程序分布在列表连接上是真的吗？

Haskell: Is it true that function application distributes over list concatenation?

haskell

functional-programming

proof