Problem in search of an elegant solution

[cormullion]

Here's a little problem I'm trying to solve. Given a value, and a list/association list, find the entry that provides the nearest match for the first element. For example:

Code Select Expand

(set 'target 200906281845)

(set 'data '(
(200906282050 "29003KT" "CAVOK" "19/13" "Q1015=")
(200906281950 "05004KT" "CAVOK" "19/13" "Q1014=")
(200906281750 "12010KT" "9999" "FEW020" "20/13" "Q1014=") ; <- this is the one to be found
(200906281700 "12010KT" "9999" nil "20/14" "Q1015=")
(200906280000 "12010KT" "9999" "FEW020" "20/14" nil)
; ...
))


The elegant solution is currently eluding me... Can I do it with ref/ref-all or do I need a state-keeping function?

[Lutz]

This would return a list of indices where the first number differs less then maxdiff from target:

Code Select Expand

(set 'target '205)
(set 'maxdiff 30)

(set 'data '(
(101 a b c)
(200 c d e)
(230 x y z)
(250 f g h)))


(find-all 205 data $it (fn (x y) (< (abs (- x (y 0))) maxdiff)))

=> ((200 c d e) (230 x y z))


(find-all 205 data (rest $it) (fn (x y) (< (abs (- x (y 0))) maxdiff)))

=> ((c d e) (x y z))


In the comparison function x is 205 and y is each of the sublists.

[Kazimir Majorinc]

Additionally, Lutz's solution with maxdiff defined automatically:

Code Select Expand

(set 'target '205)
(set 'maxdiff 30)

(set 'data '((101 a b c)
             (200 c d e)
             (230 x y z)
             (250 f g h)))

(println ((lambda(t)(ref (apply min t) t))
          (map (lambda(y)(abs (- target y)))
               (map first data))))


I think that whole situation suggests defining functions as refmin and refclose :

Code Select Expand

(set 'target '205)
(set 'maxdiff 30)

(set 'data '((101 a b c)
             (200 c d e)
             (230 x y z)
             (250 f g h)))

(set 'refmin (lambda(t)(ref (apply min t) t)))

(set 'refclose
     (lambda(target L)
        (refmin (map (lambda(y)(abs (- target y)))
                      L))))
                         
(println (refclose target (map first data)))


[Cyril]

The elegant solution is currently eluding me... Can I do it with ref/ref-all or do I need a state-keeping function?

Is using apply for state keeping elegant enough?

Code Select Expand

(define (df datum) (abs (- target (datum 0))))
(define (choose x y) (if (< (df x) (df y)) x y))
(println (apply choose data 2))


[cormullion]

Ah, these are all looking great. When in doubt, ask the experts! My attempt was functional (hah) but basic and inelegant.

Code Select Expand

(context 'nearest-record)
(set 'error-margin 1000000000 'best nil)

(define (nearest-record:nearest-record lst target)
    (when (< (abs (sub target (first lst))) error-margin)
        (set 'error-margin (abs (sub target (first lst))))
        (set 'best lst)))

(context MAIN)

(dolist (record data) (nearest-record record target))


and the best score is in the context.



Thanks!

[unixtechie]

err.. if you stop  keeping it all as lists, but create a hash with the first member as its key and the rest as a list it refers to, you could use the fact that red-black trees used for hashes in newlisp are implicitly ordered.



Then iterating over them will give you a numerically growing sequence - and so you won't need to go through all your data. You will just compare until the elements become bigger than the given value (and/or compare it to the given value plus or minus the "maxdeviation"), then stop, as you got your solution.



This should make this snippet faster.

[cormullion]

It is difficult to evaluate the elegance of imaginary code  ... :)



But seriously, yes, that's a very good point. In fact I could even do a binary search, to narrow down the area of the data file even quicker. (Although I'm not worried about speed, much, in this application.)



Thanks!

[rickyboy]

Is using apply for state keeping elegant enough?

Yup.  Sure is.  Your code showed the general power of the folding operation.  Folding doesn't necessarily have to accumulate, as the canonical examples of it, like sums, seem to indicate.  Good job, Cyril!

[cormullion]

I ended up using Cyril's solution (refactored slightly) because it was the simplest and the coolest.



I'm going to have to think about why it's called 'folding' - my mental picture of apply-reduce involves walking along the seashore picking up pebbles, which shows how far away from being a real programmer I am... :)

[rickyboy]

Hi cormullion,



Here is a suggested interface to Cyril's code.  (But you will know best what you need, of course.)

Code Select Expand

(define (find-nearest db tgt)
  (let ((target tgt))
    (apply choose db 2)))

In action:

Code Select Expand

> (find-nearest data 205)
(200 c d e)
> (find-nearest data 228)
(230 x y z)
> (find-nearest data 500)
(250 f g h)
>
It should not be lost on the reader/programmer that this interface takes advantage of dynamic binding.  How?  Notice that function find-nearest binds the symbol target to the value of its parameter tgt (in the let expression).  The function df, when it gets called down the stack, will "see" this value in target.

[cormullion]

Thanks Rick! Good to see you round here occasionally...