Схема - функция карты для применения функции к элементам во вложенном списке - PullRequest
Новая
       48

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

1 голос
/ 18 апреля 2011

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

Например, (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))]

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

Ответы [ 2 ]

4 голосов
/ 18 апреля 2011

Вот мое решение - оно очень дешевое, поскольку использует встроенный 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)).

3 голосов
/ 18 апреля 2011

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

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

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

...