Схема — функция карты для применения функции к элементам во вложенном списке.

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

Например, (map number? '(3 (2 A) 2 Z) должно вернуть (#t (#t #f) #t #f)

Вот что у меня есть до сих пор:

(define (map fun lst)
    (if (null? lst) '()
        (if (list? (car lst)) 
            (cons (map fun (car lst)) (map fun (cdr lst)))
                 (cons (fun (car lst)) (map fun (cdr lst))))))

Это работает, если вложенный список находится в начале списка. Например, (map number? '((3 A) 2 Z)) правильно возвращает ((#t #f) #t #f)

Проблема возникает, когда вложенный список располагается после другого элемента в исходном списке. Например, (map number? '(3 A (2 Z))) неправильно возвращает (#t #f #f) [результат должен быть (#t #f (#t #f))]

Как я могу изменить свой алгоритм, чтобы исправить это?


list nested map-function scheme
person ben.coffee    schedule 18.04.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Вот мое решение — оно очень дешевое, поскольку повторно использует встроенный map, используя шаблон декоратора. (Я знаю, программы Scheme используют шаблоны проектирования? :-O)

(define (deep-map f l)
  (define (deep x)
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x))))
  (map deep l))

Это можно еще больше «упростить», используя именованный let:

(define (deep-map f l)
  (let deep ((x l))
    (cond ((null? x) x)
          ((pair? x) (map deep x))
          (else (f x)))))

(Два фрагмента кода не идентичны, но для этого вопроса оба будут работать одинаково, если в качестве входных данных будет указан список.)

Проверки null? и pair? (обе O(1)) используются, чтобы избежать использования list? (что равно O(n)).

person Chris Jester-Young    schedule 18.04.2011
comment
Серьезно дешевый здесь неверен... Например, я ожидаю, что многие реализации будут создавать лучший код для более простой версии, которая вызывает себя напрямую, поскольку map обычно достаточно тяжел, чтобы его нельзя было встроить. Таким образом, хотя в некоторых случаях это может быть дешевле, утверждение, что это всегда дешевле, неверно. - person Eli Barzilay; 18.04.2011
comment
@Eli: «Дешево» в этом контексте не имеет в виду производительность, а то, что я решил проблему мошенника. :-) - person Chris Jester-Young; 18.04.2011
comment
CKY: это даже не дешевле с точки зрения повторного использования кода — вы экономите на (cons (map ...) (map ...)), что является крошечным преимуществом, но результат более понятен с педагогической точки зрения... (И в процессе вы получаете что-то более общее, хотя это, конечно, не имеет отношения к вопросу.) - person Eli Barzilay; 18.04.2011
comment
@Eli: я ответил в IRC. (Думаю, это самый простой способ поставить всех на одну страницу.) :-) - person Chris Jester-Young; 18.04.2011
comment
Обратите внимание, что pair? не подразумевает список - это не сработает для (a (b . c) d) с (b . c) неправильным списком. Вы не можете избежать оплаты этого O(n) на list?, так как этого требует map - person Neowizard; 17.09.2018

arrow_upward
3
arrow_downward

Ваш код правильный, за исключением того, что он слишком многословен, чем мог бы быть. Подсказка: вам нужно беспокоиться только о двух случаях: является ли lst pair? или нет. Это все. Другими словами, ваш код предполагает, что ввод всегда является списком, но его можно упростить, чтобы принимать что угодно и выполнять специальные рекурсивные действия, когда это пара.

Что касается проблемы, которую вы видите, я предполагаю, что вы используете Racket, и поэтому вы столкнулись со странным случаем. Если это не так, то вы можете прекратить чтение здесь.

Дело в том, что в Racket сама функция скомпилируется до того, как будет выполнена привязка к map, поэтому вызовы map на самом деле не рекурсивны, а просто вызовы встроенного map. Позже map (повторно) привязывается к результирующей функции, но рекурсивные вызовы уже скомпилированы. Если вы введете одно и то же определение дважды, вы увидите, что оно снова начинает работать. Способ решить эту проблему состоит в том, чтобы просто не работать с REPL, а вместо этого всегда записывать определения в файл, который начинается с некоторого #lang <something>.

person Eli Barzilay    schedule 18.04.2011
comment
Я использую курицу. Спасибо за подсказку, постараюсь исправить. - person ben.coffee; 18.04.2011
comment
Ну, я не знал, что Цыпленок делает это, но я не удивлюсь, если это та же проблема... - person Eli Barzilay; 18.04.2011
comment
Извините, а не могли бы вы уточнить, что такое пара в контексте схемы? Я еще новичок. - person ben.coffee; 18.04.2011
comment
@user247679 user247679: Списки в схеме состоят из нуля или более минусов (пар). Например, (list 1) совпадает с (cons 1 '()) (список, состоящий из одной пары), а (list 1 2 3) совпадает с (cons 1 (cons 2 (cons 3 '()))) (список, состоящий из трех пар). В Scheme вы можете проверить пары, используя pair?. - person Chris Jester-Young; 18.04.2011