Карта, фильтр, папка в DrRacket/Scheme

Язык программирования: Схема/DrRacket

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

Кто-нибудь хочет объяснить, для чего каждый из них используется и чем они отличаются? К сожалению, моя книга не очень ясна.


filter functional-programming fold map-function scheme
person Lukas Pleva    schedule 24.10.2011    source источник
comment
Из любопытства, какую книгу вы используете? Я собираюсь подключить книгу, которую один из моих профессоров написал под названием Просто схема; он доступен бесплатно в Интернете, и его стоит посмотреть. Он был лучшим профессором, который у меня был, так что я подозреваю, что книга очень хорошая, хотя сам я ее не читал.   -  person Tikhon Jelvis    schedule 24.10.2011

Ответы (2)


arrow_upward
41
arrow_downward

Основная идея состоит в том, что все три являются способами применения некоторой функции ко всем элементам списка.

Карта, пожалуй, самая простая — вы просто применяете функцию к каждому элементу списка. Это в основном то же самое, что и цикл for-each в других языках:

 (map (lambda (x) (+ x 1)) '(1 2 3))
   => (2 3 4)

По сути, карта такая: (map f '(1 2 3)) совпадает с (list (f 1) (f 2) (f 3)).

Фильтр также прост: функция действует как арбитр, решая, сохранять ли каждое число. Представьте себе очень разборчивого едока, просматривающего меню и ноющего о вещах, которые он не будет есть ;)

 (filter (lambda (x) (equal? x 1)) '(1 2 3))
   => (1)

Мне кажется, фолд труднее всего понять. Более интуитивно понятным названием было бы «накопить». Идея состоит в том, что вы «комбинируете» список по мере продвижения. В повседневном использовании есть некоторые функции, которые на самом деле являются сгибами — sum — прекрасный пример.

 (foldr + 0 '(1 2 3)) 
   => 6

Вы можете думать о сгибе как о том, что вы берете функцию и помещаете ее между каждым элементом в списке: (foldr + 0 '(1 2 3)) совпадает с 1 + 2 + 3 + 0.

Fold особенный, потому что, в отличие от двух других, он обычно возвращает скалярное значение — то, что было элементом списка, а не самим списком. (Это не всегда верно, но все равно подумайте об этом сейчас.)

Обратите внимание, что я, возможно, не довел до совершенства каждую деталь кода — я когда-либо использовал только другую, более старую реализацию Scheme, поэтому я мог упустить некоторые детали Racket.

person Tikhon Jelvis    schedule 24.10.2011
comment
Прохладный! Большое спасибо за отличное объяснение :-) - person Lukas Pleva; 24.10.2011
comment
Всегда рад помочь. Если что-то все еще не ясно, не стесняйтесь сказать мне, чтобы я мог попытаться пересмотреть свое объяснение. - person Tikhon Jelvis; 24.10.2011
comment
Будет ли (foldl + 0 '(1 2 3)) таким же, как 3 + 2 + 1 + 0 ? - person No_name; 30.11.2012
comment
@No_name: Ага. Вы не можете отличить их друг от друга с помощью +, потому что это коммутативно, но попробуйте (foldl cons '() '(1 2 3)) и (foldr cons '() '(1 2 3)). - person Tikhon Jelvis; 30.11.2012
comment
Точнее было бы сказать, что вы не можете отличить их друг от друга, потому что + ассоциативно. foldl и foldr дают один и тот же результат, если операция, которую они передают, является ассоциативной. - person Pig; 03.09.2017

arrow_upward
2
arrow_downward

Я могу порекомендовать эти упражнения для пальцев (и текст, который идет раньше):

http://htdp.org/2003-09-26/Book/curriculum-ZH-27.html#node_idx_1464

person soegaard    schedule 24.10.2011