Haskell - Как преобразовать сумму карты (map (x:) xss) в карту (x+) (сумма карты xss)

Question

Читая "Мышление функционально с Haskell", я натолкнулся на часть расчета программы, которая требовала, чтобы map sum (map (x:) xss) быть переписан как map (x+) (map sum xss)

Интуитивно я знаю, что это имеет смысл...

если у вас есть несколько списков, которые вы собираетесь суммировать, но перед суммированием к тем же спискам вы также добавите один элемент 'x', то это то же самое, что взять список сумм оригинальных списков и добавить х значение для каждого из них.

Но я хотел бы знать, как преобразовать одно в другое, используя только рациональные рассуждения. Я чувствую, что мне не хватает закона или правила, которые помогли бы мне понять.

Answer 1

Используя закон

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

Мы можем вывести

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

Эта-расширить, чтобы дать аргумент для работы с

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 =

Эта-уменьшить лямбда

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]

Суть в том, что в первом примере вы меняете типы не так, как во втором. Точка, в которой список списков становится просто списком, меняется, как и способ добавления номера.