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