Справка по составлению списков неравномерных списков - Схема - PullRequest
1 голос
/ 06 ноября 2011

Я пытаюсь создать функцию, в которой я объединяю элементы из двух разных списков.Конечно, моя первая идея - использовать функцию map, которая работает для списков одинакового размера, но если бы я хотел соединить два списка разных размеров и заменить отсутствующие элементы, скажем, *, как бы я поступил так?

Ответы [ 3 ]

3 голосов
/ 06 ноября 2011

Вы можете думать об этом так:

Ваша рекурсивная функция, назовите ее zip-uneven, возьмет два списка A и B и вернет список списков из двух элементов.На каждом этапе мы будем думать только о начале списков, оставляя остальную часть каждого для рекурсивного вызова zip-uneven с остальными списками.Существует четыре варианта:

  1. Оба списка пусты (null?).

    Это ваш базовый случай, который должен вернуть пустой список.

  2. Список B пуст, а в списке A все еще есть элементы

    В этом случае вы хотите вернуть список, первым элементом которого является список (car a) и ваш фиктивный *символ и другие элементы которого создаются путем повторения с использованием остальной части списка A (cdr a) и «остатка» списка B (который по-прежнему является пустым списком, '()).

    То естьвозвращаемое значение zip-uneven будет cons из (list (car a) '*) и результатом рекурсивного вызова (zip-uneven ...).

  3. Как и в случае 2, но с пустыми непустые списки перевернуты

  4. Ни один список не пуст.Это будет очень похоже на случаи (2) и (3), но вы вернетесь к cdr обоих списков.

Если один список короче другого,в конце концов, когда вы cdr выберете списки, это уменьшится до case (2) или case (3);независимо от того, имеют ли списки разную длину или нет, в конечном итоге рекурсия сведется к случаю (1), в этом случае «остаток списка» равен '(), и мы закончили с рекурсией.

Помогает ли этовообще?

1 голос
/ 07 ноября 2011

Мой ответ состоит из двух частей: сначала я реализую map-shortest, затем я настрою его для реализации map-longest, поскольку это (едва ли) более сложное занятие. Оба решения требуют SRFI 1 ; решение map-shortest использует unfold и any, а решение map-longest использует unfold и every. (Кстати, SRFI 1 также предоставляет map, который работает так же, как map-shortest.)

Сначала map-shortest:

(define (map-shortest func . lists)
  (unfold (lambda (lists)
            (any null? lists))
          (lambda (lists)
            (apply func (map car lists)))
          (lambda (lists)
            (map cdr lists))
          lists))

Это просто:

  1. Проверяет, пусты ли какие-либо списки. Если это так, остановитесь.
  2. В противном случае car каждого списка используется в качестве аргументов для вызова функции с помощью.
  3. Затем cdr через каждый список для следующей итерации.

Теперь map-longest - это вариант, за исключением того, что вам приходится иметь дело с тем фактом, что некоторые списки могут быть уже пустыми:

(define (map-longest func filler . lists)
  (define (car-or-filler x)
    (if (pair? x) (car x) filler))
  (define (cdr-or-null x)
    (if (pair? x) (cdr x) '()))
  (unfold (lambda (lists)
            (every null? lists))
          (lambda (lists)
            (apply func (map car-or-filler lists)))
          (lambda (lists)
            (map cdr-or-null lists))
          lists))

Итак, это очень похоже на map-shortest, с тремя отличиями:

  1. Условие завершения: every, а не any: мы останавливаемся, когда каждый список пуст.
  2. Вместо car мы используем car-or-filler, который получает car, если список не пустой, или заполнитель в противном случае.
  3. Вместо cdr мы используем cdr-or-null, который получает cdr, если список не пустой, или пустой список в противном случае. (В этот момент я могу слышать смех Common Lispers: в ​​Common Lisp (cdr '()) возвращает '(); на Схеме не так.)

Достаточно просто, надеюсь? : -)

0 голосов
/ 06 ноября 2011

Используйте цикл WHILE, чтобы ... подождите, дерьмо.

Хорошо, используйте цикл FOR, чтобы ... э-э ...

Честно говоря, у меня был бы помощникфункция, которая сравнивает длины каждого списка, а затем добавляет звездочки в конец более короткого, пока он не станет того же размера.

Итак, псевдокод, потому что я не могу вспомнить все особенности схемы:

    (define helperFunction(list1, list2)
      first = list-length(list1)
      second = list-length(list2)
      if(first > second)
         asteriskPopulate(list2, first-second)
      else if(second > first)
         asteriskPopulate(list1, second-first)
     )

Редактировать для дополнительной ясности:

    (define list-length
       (lambda (l)
       (cond
          ((null? l) 0)
          (#t (+ 1 (list-length (cdr l)))))))

Редактировать для объяснения (Извините!):

Функция helperFunction принимает два списка возможных неодинаковых длин и наборовдве переменные firstLength и secondLength для представления длин двух списков.Это достигается с помощью кода длины списка (взято с благодарностью из Схема обучения ).Этот код работает через встроенную рекурсию, рекурсивно отбрасывая элементы CDR и добавляя их к конечному результату.

Когда у нас есть две длины, которые мы можем сравнить, вызывается отдельная функция asteriskPopulate с более коротким из двух списков и разницей в длинах.Внутри этой функции мы просто добавим серию звездочек, пока наша разностная переменная (первая минус вторая или вторая минус первая) не станет равной 0. Я оставляю вам право написать эту функцию, она должна быть быстрой и информативной.

Инаконец, когда у нас есть списки равной длины, вы можете использовать MAP соответствующим образом.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...