满足f . concat = concat . f . map f定律的列表函数有哪些？已知id等还有其他吗？

首先明确定律的含义：对于任意列表的列表 xss :: [[a]]，函数 f 需要满足：

f (concat xss) = concat (f (map f xss))

你提到的三个函数确实都符合该定律：

• id：左边 id . concat = concat，右边 concat . id . map id = concat，两边完全相等。
• reverse：左边 reverse (concat xss) 是对拼接后的列表整体反转；右边 concat (reverse (map reverse xss)) 先反转每个子列表，再反转整个子列表的顺序，最后拼接，结果与左边一致（reverse(xs1++xs2++...++xsN) = reverse xsN ++ ... ++ reverse xs2 ++ reverse xs1）。
• const []：左边 const [] . concat 始终返回空列表；右边 concat . const [] . map (const []) 也始终返回空列表，两边相等。

是否存在其他符合条件的函数？ #

从推导和测试来看，不存在非平凡的其他函数，原因如下：

1. 必须满足 f [] = []：当 xss = [] 时，concat xss = []，代入定律可得 f [] = concat(f [])，只有 f [] = [] 能满足类型和值的一致性。
2. 单个元素列表的行为必须统一：对于任意 [x]，要么 f [x] = [x]，要么 f [x] = []。如果存在两种不同行为的元素，构造 xss = [[x], [y]] 时，左右两边结果会不一致。
3. 拼接行为必须全局一致：对于任意 xs ++ ys，函数只能是以下三种行为之一：
   • 保持拼接顺序：f(xs++ys) = f xs ++ f ys（对应 id）
   • 反转拼接顺序：f(xs++ys) = f ys ++ f xs（对应 reverse）
   • 始终返回空列表：f(xs++ys) = []（对应 const []）

任何尝试混合不同行为的函数（比如部分反转、部分保留，或基于元素筛选的函数），都会在特定的列表组合下违反定律。

内容的提问来源于stack exchange，提问作者Matt R