To implement best-first search we need to add one more piece of information: a cost function that gives an estimate of how far a given state is from the goal.

For the binary tree example, we will use as a cost estimate the numeric difference from the goal. So if we are looking for 12, then 12 has cost 0,8 has cost 4 and 2048 has cost 2036. The higher-order function d i f

f, shown in the following, returns a cost function that computes the difference from a goal. The higher-order function sorter takes a cost function as an argument and returns a combiner function that takes the lists of old and new states, appends them together, and sorts the result based on the cost function, lowest cost first. (The built-in function sort sorts a list according to a comparison function. In this case the smaller numbers come first. sort takes an optional : key argument that says how to compute the score for each element. Be careful-sort is a destructive function.)

(defun diff (num)