Как определить карту с помощью foldr?

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

Как бы вы определяли карту и фильтр с помощью foldr в Haskell?

Однако здесь решение включает использование лямбд, которые я еще не рассмотрел, и я предполагаю, что из-за этого упражнение должно выполняться без лямбд (хотя вы никогда не знаете).

Я думаю, что меня больше всего смущает то, что map принимает унарную функцию (например, +1), тогда как foldr принимает двоичную функцию (например, +), и я действительно не понимаю, как заставить эти два работать вместе.


map fold haskell variable-assignment
person user3062734    schedule 03.12.2013    source источник
comment
Все возможно без лямбд. Просто создайте именованную функцию, которая делает то же самое. Что касается того, как подойти к этому, выясните, как писать id :: [a] -> [a] с foldr. Затем помните, что id :: [a] -> [a] - это то же самое, что map (id :: a -> a), и выясните, где вам нужно применить дополнительную функцию.   -  person Carl    schedule 03.12.2013
comment
Нет разницы между тем, что вы называете лямбдой, и любой другой функцией. Все они просто функции. Здесь показан синтаксис для определения функции без имени.   -  person Chuck    schedule 03.12.2013
comment
Релевантно: web.jaguarpaw.co.uk/~tom/blog/posts/   -  person Tom Ellis    schedule 04.12.2013
comment
попробуйте википедию, en.wikipedia.org/wiki/Fold_(higher-order_function) :)   -  person JJJ    schedule 04.12.2013
comment
@TomEllis left_fold f z xs = let rs = z : zipWith f xs rs in last rs; zipWith - это карта: zipWith f a b = map (uncurry f) $ zip a b (хотя last - своего рода складка ... (?)). Но, игнорируя это, rev xs = left_fold (flip (:)) [] xs (реверс - левая складка); а затем right_fold f z xs = let rs = z : zipWith f (rev xs) rs in last rs. ср. stackoverflow.com/a/11951590/849891.   -  person Will Ness    schedule 04.12.2013

Ответы (2)


arrow_upward
7
arrow_downward

foldr на самом деле просто: учитывая список (написанный с помощью : и []), например

a : (b : (c : (d : [])))

затем применение к нему foldr h x заменит каждый : на `h` и [] на x:

a `h` (b `h` (c `h` (d `h` x)))

Сравните это с тем, что map f будет со списком:

f a : (f b : (f c : (f d : [])))

Это должно помочь вам выбрать h и x так, чтобы foldr h x = map f.

person Joachim Breitner    schedule 03.12.2013
comment
Я думаю, вы забыли :s до []s и до x. - person David Young; 04.12.2013

arrow_upward
5
arrow_downward

foldr разбивает список справа и позволяет передавать накопленное значение через вычисление. Поскольку map сохраняет длину списка, вам нужно пропустить новый список, который содержит преобразованные значения.

Тип foldr - (a -> b -> b) -> b -> [a] -> b

Ваша функция-аккумулятор принимает состояние (создаваемый новый список) и текущий элемент списка, и вам необходимо создать новый список, содержащий элемент, преобразованный функцией сопоставления.

Второй аргумент foldr - это начальное значение аккумулятора, и это значение, возвращаемое, если список ввода пуст, поэтому вы должны иметь возможность использовать это, чтобы выяснить, каким оно должно быть для вашей функции карты.

person Lee    schedule 03.12.2013