Haskell- написать функцию карты используя foldr

Question

Я пытаюсь написать функцию карты с помощью foldr. Проблема заключается в том, что, когда я запустил этот код:

> myMap f xs = foldr (\ acc x -> acc :(f x)) [] xs 

У меня есть следующая проблема:

Нет экземпляра для (Num [a0]), возникающие из использования 'это'

, но когда я бегу

myMap f xs = foldr (\x acc-> (f x):acc) [] xs 

Он отлично работает. Любые идеи почему?

Answer 1

типа foldr является

foldr :: (a -> b -> b) -> b -> [a] -> b 

поэтому бинарной операция, которая foldr использует для обхода и накапливать список имеет тип (a -> b -> b), он сначала принимает элемент списка (типа a), затем аккумулятор (тип b), что приводит к выражению типа b.

Итак, ваша первая функция myMap не работает, потому что вы используете «acc» и «x» в обратном порядке. Вы хотите применить f к x, а затем добавить его к acummulator типа b (список в этом случае)

Answer 2

Ошибка, которую вы отправили, не исходит из вашего определения myMap, это исходит из того, как вы ее используете. Тип первого myMap - ([a] -> [a]) -> [a] -> [a], который не соответствует типу Prelude.map. Во втором вы заменили имена переменных, а также тот, который вы применяете f. Компилятору все равно, что вы называете аргументами в вашей лямбда, переданной в foldr, поэтому foldr (\x acc -> f x : acc) идентичен foldr (\foo bar -> f foo : bar). Это может быть то, что вас трогает.

Второй работает, потому что (просто) это правильно. В первом вы подаете f в свой список аккумуляторов x (хотя у вас есть переменная с именем acc, это не ваш аккумулятор), поэтому f должен взять список и вернуть список. Во втором вы применяете f к каждому элементу, а затем добавляете это в свой список аккумуляторов. Если у вас myMap (+1), он будет иметь тип

myMap (+1) :: Num [a] => [a] -> [a] 

Который говорит, что вы должны передать ему список значений [a] где [a] реализует Num, и в настоящее время не существует ни одного случая для Num [a], не будет ли когда-нибудь.

TL; DR: В первом случае вы применяете свою отображаемую функцию в свой список аккумуляторов, а во втором вы применяете сопоставленную функцию к каждому элементу.