Wednesday, April 13, 2011

How do you properly compute pairwise differences in Scheme?

Hello,

Given a list of numbers, say, (1 3 6 10 0), how do you compute differences (xi - xi-1), provided that you have x-1 = 0 ?

(the result in this example should be (1 2 3 4 -10))

I've found this solution to be correct:

(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)

However, I think there should be more elegant though no less flexible solution. It's just ugly.

I'm new to functional programming and would like to hear any suggestions on the code.

Thanks.

From stackoverflow
  • I haven't done scheme in dog's years, but this strikes me as a typical little lisper type problem.

    I started with a base definition (please ignore misplacement of parens - I don't have a Scheme interpreter handy:

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

    This handles the crap cases of null and atom and then delegates the meat case to a helper:

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

    You could rewrite this using "if", but I'm hardwired to use cond.

    There are two cases here: null list - which is easy and everything else. For everything else, I grab the head of the list and cons this diff onto the recursive case. I don't think it gets much simpler.

    Svante : You can't use LIST for a variable, because Scheme is a Lisp-1.
    AnSGri : Surprisingly, the code works, if you remove ((atom? list) list)
    Nathan Sanders : 'list as variable works fine as long as you don't need to call the function named 'list. Shadowing happens--get used to it. :) (atom? list) should only be needed for an improper list (one that doesn't end in nil), which hardly ever happens.
  • After refining and adapting to PLT Scheme plinth's code, I think nearly-perfect solution would be:

    (define (pairwise-apply f l0 l)
      (if (empty? l)
          '()
          (let ([l1 (first l)])
            (cons (f l1 l0) (pairwise-apply f l1 (rest l))))))
    
    Svante : One problem remains: this is not tail recursive, so the stack will be blown unless your argument lists are guaranteed to be small.
  • map takes multiple arguments. So I would just do

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

    If you want to wrap it up in a function, say

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

    This is of course not the Little Schemer Way, but the way that avoids writing recursion yourself. Choose the way you like the best.

    AnSGri : Yes, this is the obvious solution, but I want an effective approach: the code will be called several thousand times.
    Nathan Sanders : Oh. In your question you asked for elegance. For effectiveness, you need to worry about tail-recursion, which is not addressed by the solutions given so far.
  • Haskell tells me to use 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)
    
    Svante : If you do (zip-with - lst (cons 0 lst)), you will get what the asker wanted.
  • Doesn't map finish as soon as the shortest argument list is exhausted, anyway?

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

    edit: jleedev informs me that this is not the case in at least one Scheme implementation. This is a bit annoying, since there is no O(1) operation to chop off the end of a list.

    Perhaps we can use 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)))))
    

    (Disclaimer: quick hack, untested)

    jleedev : mzscheme gives me "map: all lists must have same size".
  • This is the simplest way:

    (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)
    

    Write out the code expansion for each of the example to see how it works.

    If you are interested in getting started with FP, be sure to check out How To Design Program. Sure it is written for people brand new to programming, but it has tons of good FP idioms within.

  • (define (f l res cur)
      (if (null? l)
        res
        (let ((next (car l)))
          (f (cdr l) (cons (- next cur) res) next))))
    
    (define (do-work l)
      (reverse (f l '() 0)))
    
    (do-work '(1 3 6 10 0))
    
    ==> (1 2 3 4 -10)
    

0 comments:

Post a Comment