CODEWITHSUNDEEP
lispcommon-lispbinary-search
Andrew S.
Andrew S.

Reputation: 467

Binary search in lisp with higher level function

I am trying to write a (higher order function) which takes a vector and a function and makes a binary search accroding to that function, i.e. if it returns -1, we need to go lower, for 1 -- higher, for 0 we found the right place. I came up with something like this, but it seems that I did something wrong with passing function as an argument:

(defun bin-search (ls fpred)
 (let ((l (length ls))
       (x (aref ls (floor (length ls) 2))))
       (labels (binsearch (ls fpred l m)
                (case (funcall #'fpred (aref ls m))
                 (-1 (binsearch (ls fpred l (floor (- m l) 2))))
                 (0 (return-from binsearch m))
                 (1 (binsearch (ls fpred m (+ m (floor (- m l) 2)))))))
 (binsearch ls fpred 0 l))))

Compiler says that variable FPRED is defined but never used. What is wrong?

Upvotes: 1

Views: 966

Answers (2)

Andrew S.
Andrew S.

Reputation: 467

Fixed (supposedly) everything, it works now. Thanks a lot.

(defun bin-search (vec fpred)
 (let* ((l (length vec)))
  (labels ((binsearch (vec l m)
            (case (funcall fpred (aref vec m))
             (-1 (binsearch vec  l (+ l (floor (- m l) 2))))
             (0 (return-from binsearch m))
             (1 (binsearch vec m (+ m (floor (- m l) 2)))))))
     (binsearch vec 0 (floor l 2)))))

Improved:

  • let instead of let*
  • name of the internal function changed
  • return-from is not needed

applied:

(defun bin-search (vec fpred)
  (let ((l (length vec)))
    (labels ((bin-search-aux (vec l m)
               (case (funcall fpred (aref vec m))
                 (-1 (bin-search-aux vec l (+ l (floor (- m l) 2))))
                 ( 0 m)
                 ( 1 (bin-search-aux vec m (+ m (floor (- m l) 2)))))))
      (bin-search-aux vec 0 (floor l 2)))))
  • let replaced by &aux arg -> one indentation level less
  • vec does not need to be passed

applied:

(defun bin-search (vec fpred &aux (l (length vec)))
  (labels ((bin-search-aux (l m)
             (case (funcall fpred (aref vec m))
               (-1 (bin-search-aux l (+ l (floor (- m l) 2))))
               ( 0 m)
               ( 1 (bin-search-aux m (+ m (floor (- m l) 2)))))))
    (bin-search-aux 0 (floor l 2)))))

Test:

CL-USER > (bin-search #(1 2 3 4 5 6 7 8 9)
                      (lambda (x)
                        (if (< x 7) 1 (if (> x 7) -1 0))))
6

Upvotes: 1

coredump
coredump

Reputation: 38799

(defun bin-search (ls fpred)

Please use meaningful names, you have many short names or abbreviations, which is difficult to read. For example, ls makes me think of a list, which could be simply named list, but apparently you are working with vectors, so maybe vec or vector?

 (let ((l (length ls))
       (x (aref ls (floor (length ls) 2))))

If you want to reuse the length l defined in the same let, you can use a let* instead, and write l instead of the second occurrence of (length ls).

       (labels (binsearch (ls fpred l m)

The syntax for labels is a list of bindings (name (<args>) <body>), so you need to add another pair of parentheses, like (labels ((binsearch (<args>) <body>)) ...

Addditionally, you do not need to pass fpred as a parameter, it does not change from one invocation of binsearch to another. You can just refer to bin-search's fpred parameter from inside your local function.

                (case (funcall #'fpred (aref ls m))

When you write #'fpred, which is equivalent to (function fpred), you are looking for fpred in the function namespace. Here you want to access the function associated with the variable named fpred, and so you can drop the #' part.

                 (-1 (binsearch (ls fpred l (floor (- m l) 2))))

When you write (binsearch (ls fpred ...)), that means: call binsearch with one value, obtained by calling function ls with arguments fpred, .... Parentheses are significant, and you need to remove them here.

                 (0 (return-from binsearch m))
                 (1 (binsearch (ls fpred m (+ m (floor (- m l) 2)))))))
 (binsearch ls fpred 0 l))))

Upvotes: 5

Related Questions