recursion schemes that prune
I think my comment was a little cryptic, so let me unpack. The key intuition behind hylomorphisms is that they let you reify the call graph as a data structure. You unfold a datastructure to build a representation of the call graph, and then you fold over the intermediate structure to consume and finish the computation. 

Lists are a little misleading, because in a recursive algorithm over a list, the call graph will also form a list. However, in general this will not be the case: the call graph will have a different shape than your input data, and so you'll need to introduce a new datatype to represent it. As an example. here's your binary search example. I'll use Ocaml, since I'm more familiar with it, but it should be fairly easy to transcribe it to Haskell. 

First, let's introduce a datatype of binary search trees. We'll just assume they maintain the invariant in a node Node(l, x, r) that the left subnode l contains the elements smaller than x and the right subtree r contains the elements bigger than x.  

type tree = Leaf | Node of tree * int * tree


Now, let's introduce a datatype to represent the call graph of a binary search. A binary search will finish with failure if the tree is a Leaf, finish with success if you have a Node whose value is what you're looking for, and keep going otherwise. 

We'll represent this with a datatype result that is either a Done b, where b is a boolean with success or failure, or else gives you a Next thunk with a computation which will give you a new result. (In Haskell, you wouldn't need the unit -&gt; 'a thing because all datatypes are lazy.)

We'll split result into a functor resultF, and tie the recursive knot in this datatype explicitly, so that we can easily program the map functional for functor.

type 'a resultF = Done of bool | Next of (unit -&gt; 'a)
type result = Rec of result resultF

let map_resultF f v =
  match v with
  | Done b -&gt; Done b
  | Next thunk -&gt; Next (fun () -&gt; f (thunk()))   


Now, we can define a fold operation for the result type. 

(* val fold_result : ('a resultF -&gt; 'a) -&gt; result -&gt; 'a *)
let rec fold_result f (Rec result) =
  f (map_resultF (fold_result f) result)


Here's a function that uses the fold function to force all the Next steps until you get to the boolean final answer.     

(* val finish : result -&gt; bool *)
let finish  = 
  fold_result 
    (fun r -&gt; 
       match r with 
       | Done b -&gt; b 
       | Next thunk -&gt; thunk())


We finally get to the interesting part. Here's the unfold operation for the result type: 

(* val unfold_result : ('a -&gt; 'a resultF) -&gt; 'a -&gt; result *)
let rec unfold_result f  seed =
  Rec (map_resultF (unfold_result f) (f seed))


Now, you can see how to use an integer and a tree to construct a result: 

(* val mem' : int -&gt; tree -&gt; result *)
let mem' x =
  unfold_result
    (fun seed -&gt; 
      match seed with 
      | Leaf -&gt; Done false
      | Node(l, y, r) -&gt;
          if       x &lt; y then Next (fun () -&gt; l)
          else if  x &gt; y then Next (fun () -&gt; r)
          else                Done true)


The really critical is that we're using the unfold to incrementally take the input, and building a result which we use to control the shape of the computation. This is where the pruning is taking place, and you can change it to whatever you like. Also, note that if you want to do something fancy (e.g., use intermediate estimates to control the pruning), you can change the result type to contain it, and update your unfold to compute it. 

Finally, you can see the mem function as the fold followed by an unfold, of the result type:

(* val mem : int -&gt; tree -&gt; bool *)
let mem x tree = finish (mem' x tree)