Как правильно вычислить попарные различия в схеме?

Учитывая список чисел, скажем, (1 3 6 10 0), как вы вычисляете разности (xi - xi-1), при условии, что у вас есть x-1< /под> = 0?

(результат в этом примере должен быть (1 2 3 4 -10))

Я нашел это решение правильным:

(define (pairwise-2 f init l)
  (first 
   (foldl
    (λ (x acc-data)
      (let ([result-list (first acc-data)]
            [prev-x (second acc-data)])
        (list 
         (append result-list (list(f x prev-x)))
         x))) 
    (list empty 0)
    l)))

(pairwise-2 - 0 '(1 3 6 10 0))
;; => (1 2 3 4 -10)

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

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

Спасибо.


functional-programming scheme
person ansgri    schedule 12.03.2009    source источник

Ответы (6)


arrow_upward
2
arrow_downward

map принимает несколько аргументов. Так что я бы просто сделал

(define (butlast l)
  (reverse (cdr (reverse l))))
(let ((l '(0 1 3 6 10)))
  (map - l (cons 0 (butlast l)))

Если вы хотите обернуть его в функцию, скажите

(define (pairwise-call f init l)
  (map f l (cons init (butlast l))))

Это, конечно, не способ Маленького Интригана, а способ избежать самостоятельного написания рекурсии. Выберите способ, который вам больше нравится.

person Nathan Shively-Sanders    schedule 13.03.2009
comment
Да, это очевидное решение, но мне нужен эффективный подход: код будет вызываться несколько тысяч раз. - person ansgri; 13.03.2009
comment
Ой. В своем вопросе вы просили об элегантности. Для эффективности вам нужно беспокоиться о хвостовой рекурсии, которая не рассматривается в решениях, приведенных до сих пор. - person Nathan Shively-Sanders; 14.03.2009

arrow_upward
1
arrow_downward

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

Я начал с базового определения (пожалуйста, игнорируйте неправильное размещение скобок - у меня нет под рукой интерпретатора схемы:

(define pairwise-diff
    (lambda (list)
      (cond
       ((null? list) '())
       ((atom? list) list)
       (t (pairwise-helper 0 list)))))

Это обрабатывает дерьмовые случаи null и atom, а затем делегирует мясной случай помощнику:

(define pairwise-helper
    (lambda (n list)
       (cond
         ((null? list) '())
         (t
            (let ([one (car list)])
               (cons (- one n) (pairwise-helper one (cdr list))))
         ))))

Вы можете переписать это, используя «if», но я запрограммирован на использование cond.

Здесь есть два случая: нулевой список — это легко и все остальное. Для всего остального я беру начало списка и привожу этот diff к рекурсивному случаю. Я не думаю, что это становится намного проще.

person plinth    schedule 12.03.2009
comment
Вы не можете использовать LIST для переменной, потому что Scheme — это Lisp-1. - person Svante; 13.03.2009
comment
Удивительно, но код работает, если убрать ((atom? list) list) - person ansgri; 13.03.2009
comment
'list как переменная работает нормально, если вам не нужно вызывать функцию с именем 'list. Затенение случается - привыкайте к этому. :) (атом? список) должен быть нужен только для неправильного списка (того, который не заканчивается на nil), что редко случается. - person Nathan Shively-Sanders; 14.03.2009

arrow_upward
1
arrow_downward

После доработки и адаптации к схеме PLT плинтус code, я думаю, почти идеальным решением было бы:

(define (pairwise-apply f l0 l)
  (if (empty? l)
      '()
      (let ([l1 (first l)])
        (cons (f l1 l0) (pairwise-apply f l1 (rest l))))))
person ansgri    schedule 12.03.2009
comment
Остается одна проблема: это не хвостовая рекурсия, поэтому стек будет взорван, если ваши списки аргументов не гарантированно будут маленькими. - person Svante; 13.03.2009

arrow_upward
1
arrow_downward

Haskell говорит мне использовать zip ;)

(define (zip-with f xs ys)
  (cond ((or (null? xs) (null? ys)) null)
        (else (cons (f (car xs) (car ys))
                    (zip-with f (cdr xs) (cdr ys))))))
(define (pairwise-diff lst) (zip-with - (cdr lst) lst))

(pairwise-diff (list 1 3 6 10 0))
; gives (2 3 4 -10)
person Josh Lee    schedule 13.03.2009
comment
Если вы сделаете (zip-with - lst (cons 0 lst)), вы получите то, что хотел спрашивающий. - person Svante; 16.03.2009

arrow_upward
1
arrow_downward

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

(define (pairwise-call fun init-element lst)
  (map fun lst (cons init-element lst)))

edit: jleedev сообщает мне, что это не так, по крайней мере, в одной реализации Scheme. Это немного раздражает, так как нет операции O(1) для отсечения конца списка.

Возможно, мы можем использовать reduce:

(define (pairwise-call fun init-element lst)
  (reverse (cdr (reduce (lambda (a b)
                          (append (list b (- b (car a))) (cdr a)))
                        (cons (list init-element) lst)))))

(Отказ от ответственности: быстрый взлом, непроверенный)

person Svante    schedule 13.03.2009
comment
mzscheme дает мне карту: все списки должны иметь одинаковый размер. - person Josh Lee; 13.03.2009

arrow_upward
0
arrow_downward

Это самый простой способ:

(define (solution ls)
  (let loop ((ls (cons 0 ls)))
    (let ((x (cadr ls)) (x_1 (car ls)))
      (if (null? (cddr ls)) (list (- x x_1))
          (cons (- x x_1) (loop (cdr ls)))))))

(display (equal? (solution '(1)) '(1))) (newline)
(display (equal? (solution '(1 5)) '(1 4))) (newline)
(display (equal? (solution '(1 3 6 10 0)) '(1 2 3 4 -10))) (newline)

Напишите расширение кода для каждого примера, чтобы увидеть, как это работает.

Если вы заинтересованы в том, чтобы начать работу с FP, обязательно ознакомьтесь с How To Design Program. Конечно, она написана для людей, новичков в программировании, но в ней много хороших идиом FP.

person grettke    schedule 27.03.2009