haskell - Haskell - 如何将 map sum (map (x:) xss) 转换为 map (x+) (map sum xss)

Question

阅读“使用 Haskell 进行功能思考”时，我遇到了一个程序计算的一部分，需要将map sum (map (x:) xss)其重写为map (x+) (map sum xss)

直觉上我知道这是有道理的......

如果您有一些要求和的列表，但在求和之前，您还要向这些相同的列表添加一个元素“x”，那么这与获取原始列表总和的列表并添加 x 相同对他们每个人的价值。

但我想知道如何仅使用等式推理将一个转换为另一个。我觉得我错过了可以帮助我理解的法律或规则。

Answer 1

使用法律

map f (map g list) === map (f . g) list

我们可以推断

map sum (map (x:) xss) =
map (sum . (x:)) xss =

eta-expand 给出一个与之合作的论点

map (\xs -> sum . (x:) $ xs) xss =

代入(f . g) x === f (g x)

map (\xs -> sum (x:xs)) xs =

在哪里

sum (x:xs) = x + sum xs
sum [] = 0

所以

map (\xs -> sum (x:xs)) xss =
map (\xs -> x + sum xs) xss =

替代f (g x) === (f . g) x

map (\xs -> (x +) . sum $ xs) xss =

eta-减少 lambda

map ((x +) . sum) xss =

使用上面第一定律的反面

map (x+) (map sum xss)

Answer 2

我建议您查看类型并让它们指导您完成转换。

> let xss = [[1], [2], [3]]
> :t xss
xss :: Num t => [[t]]
> map sum xss     -- basically compacting the lists
[1,2,3]
> :t map sum xss  -- into just a list of numbers
map sum xss :: Num b => [b]

接下来我们需要做加法

> :t (+5)
(+5) :: Num a => a -> a
> :t map (+5)     --  no magic in this
map (+5) :: Num b => [b] -> [b]
> map (+5) (map sum xss)
[6,7,8]

我猜的底线是，在第一个示例中，您正在以与第二个示例不同的方式更改类型。列表列表变成列表的点发生了变化，添加数字的方式也发生了变化。