изменяемые данные в схеме для возврата пар, где правый элемент - это самый большой суффикс, соответствующий условию - PullRequest
Новая
       28

изменяемые данные в схеме для возврата пар, где правый элемент - это самый большой суффикс, соответствующий условию

2 голосов
/ 17 июня 2011

У меня есть это определение "сортировать левый список" , который представляет собой список пар, отсортированных по левому элементу каждой пары, левый элемент должен быть неотрицательным целым числом и правый компонент может иметь значение любого типа

Я должен написать процедуру mkjump, которая принимает в качестве аргумента отсортированный список неотрицательных целых чисел, sorted-lst = (x1 ... xn) и возвращает отсортированный слева список: сортировать левый список = ((x1.y1) ... (xn.yn)) так, что: yi - самый большой суффикс сортировки левого списка, ((xj. yj) ... (xn. yn)) в котором xk> (xi) ^ 2 для всех xk. Например: 

   >(define lst (list 2 3 4 15 16 17))
   >(mkjump lst)
   >lst
    ( (2 (15) (16) (17))
    (3 (15) (16) (17))
    (4 (17))
    (15)
    (16)
    (17) )

Шестой элемент в res - это (x6. Y6), где x6 = 17 и y6 = null. Третий элемент в res (x3. Y3), где x3 = 4 и y3 - список, содержащий (x6. y6), который является наибольшим суффиксом res, в котором xk> (xi) ^ 2 для всех хк

Как это написать?

Ответы [ 2 ]

2 голосов
/ 29 июня 2011

Как указывалось ранее, вам не нужно изменяемое состояние для выполнения вашей работы.Однако, если вы действительно хотите их использовать, вы можете легко изменить решение Keen, чтобы получить то, что вы хотите.Сначала вы должны перевести его код хвостовым рекурсивным способом.Вы можете начать с mkjump

(define (mkjump lst) (reverse (mkjump-tr lst '())))

(define (mkjump-tr lst sol)
  (if (null? lst)
      sol
      (mkjump-tr (cdr lst) 
                 (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) ))

Затем вы можете изменить modmap

(define (modmap proc lst) (reverse (modmap-tr proc lst '())))

(define (modmap-tr proc lst sol)
  (cond ((null? lst) sol)
        ((proc (car lst)) (modmap-tr proc 
                                     (cdr lst) 
                                     (cons (proc (car lst)) sol) ))
        (else (modmap-tr proc (cdr lst) sol))))

Хвостовая рекурсия mkjump-tr будет переведена в итеративный процесс.Это потому, что его можно рассматривать как цикл , а .Это позволит вам создать этот цикл со структурой do.Таким образом, mkjump-tr можно записать как 

(define (mkjump-tr lst sol)
  (do ((lst lst (cdr lst))
       (sol sol (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) )
    ((null? lst) sol)
    ))

, а modmap-tr можно перевести как 

(define (modmap-tr proc lst sol)
  (do ((lst lst (cdr lst))
       (sol sol (if (proc (car lst)) (cons (proc (car lst)) sol) sol)) )
    ((null? lst) sol)
    ))

Но поскольку у нас нет рекурсивной формы, мы можем записать их непосредственно do в прежних функциях mkjump и modmap.Таким образом, мы получаем 

(define (mkjump lst) 
  (do ((lst lst (cdr lst))
       (sol '() (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
                       sol)) )
    ((null? lst) (reverse sol))
    ))

(define (modmap proc lst) 
  (do ((lst lst (cdr lst))
       (sol '() (if (proc (car lst)) (cons (proc (car lst)) sol) sol)) )
    ((null? lst) (reverse sol))
    ))

Вы можете увидеть некоторые небольшие изменения: reverse добавляется перед sol и sol инициализируется пустым списком в обоих случаях.

Наконец, если вы действительно хотите где-то увидеть set!, просто добавьте их, нарушив конструкцию do -loop.Вот решение для mkjump

(define (mkjump lst)
  (let ((elt 'undefined)
        (lst lst)
        (sol '()))
  (do () 
    ((null? lst) (reverse sol))
    (set! elt (car lst))
    (set! lst (cdr lst))
    (set! sol (cons (cons elt (wrapper elt lst)) sol))
    )))

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

Это то, что вы ожидали?

1 голос
/ 19 июня 2011

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

(define (square x) (* x x))

(define (mkjump lst)
  (if (null? lst)
      '()
      (cons (cons (car lst) (wrapper (car lst) (cdr lst)))
        (mkjump (cdr lst)))))

(define (wrapper item lst)
  (modmap (lambda (x) 
         (if (< (square item) x)
             (list x)
             #f))
         lst))

(define (modmap proc lst)
  (cond ((null? lst) '())
        ((proc (car lst)) (cons (proc (car lst)) (modmap proc (cdr lst))))
        (else (modmap proc (cdr lst)))))
...