pref search prefix here fun var rest =
  case search of
    ConsSym{hd = t, tl = ts, rest = ts1} ->
      case prefix of
        ConsSym{hd = u, tl = us, rest = us1} ->
          -- Check the search term against the prefix.
          case (t, u) of
            (_, Var _) ->
              -- Prefix contains a variable - if there is a match, the
              -- variable will be bound to t.
              pref ts us here fun var rest
            (App f _, App g _) | f == g ->
              -- Term and prefix start with same symbol, chop them off.
               pref ts1 us1 here fun var rest
            _ ->
              -- Term and prefix don't match.
              rest
        _ ->
          -- We've exhausted the prefix, so let's descend into the tree.
          -- Seems to work better to explore the function node first.
          case t of
            App f _ ->
              case (fun ! fun_id f, var) of
                (Nil, Nil) ->
                  rest
                (Nil, Index{}) ->
                  step ts var rest
                (idx, Nil) ->
                  step ts1 idx rest
                (idx, Index{}) ->
                  step ts1 idx (Frame ts var rest)
            _ ->
              case var of
                Nil -> rest
                _ -> step ts var rest
    Empty ->
      case prefix of
        Empty ->
          -- The search term matches this node.
          case here of
            [] -> rest
            _ -> Yield here rest
        _ ->
          -- We've run out of search term - it doesn't match this node.
          rest

-- | An empty index.
pref search prefix here fun var rest =
  case search of
    ConsSym{hd = t, tl = ts, rest = ts1} ->
      case prefix of
        ConsSym{hd = u, tl = us, rest = us1} ->
          -- Check the search term against the prefix.
          case (t, u) of
            (_, Var _) ->
              -- Prefix contains a variable - if there is a match, the
              -- variable will be bound to t.
              pref ts us here fun var rest
            (App f _, App g _) | f == g ->
              -- Term and prefix start with same symbol, chop them off.
               pref ts1 us1 here fun var rest
            _ ->
              -- Term and prefix don't match.
              rest
        _ ->
          -- We've exhausted the prefix, so let's descend into the tree.
          -- Seems to work better to explore the function node first.
          case t of
            App f _ ->
              case (fun ! fun_id f, var) of
                (Nil, Nil) ->
                  rest
                (Nil, Index{}) ->
                  step ts var rest
                (idx, Nil) ->
                  step ts1 idx rest
                (idx, Index{}) ->
                  step ts1 idx (Frame ts var rest)
            _ ->
              case var of
                Nil -> rest
                _ -> step ts var rest
    Empty ->
      case prefix of
        Empty ->
          -- The search term matches this node.
          case here of
            [] -> rest
            _ -> Yield here rest
        _ ->
          -- We've run out of search term - it doesn't match this node.
          rest

-- | An empty index.
pref search prefix here fun var rest =
  case search of
    ConsSym{hd = t, tl = ts, rest = ts1} ->
      case prefix of
        ConsSym{hd = u, tl = us, rest = us1} ->
          -- Check the search term against the prefix.
          case (t, u) of
            (_, Var _) ->
              -- Prefix contains a variable - if there is a match, the
              -- variable will be bound to t.
              pref ts us here fun var rest
            (App f _, App g _) | f == g ->
              -- Term and prefix start with same symbol, chop them off.
               pref ts1 us1 here fun var rest
            _ ->
              -- Term and prefix don't match.
              rest
        _ ->
          -- We've exhausted the prefix, so let's descend into the tree.
          -- Seems to work better to explore the function node first.
          case t of
            App f _ ->
              case (fun ! fun_id f, var) of
                (Nil, Nil) ->
                  rest
                (Nil, Index{}) ->
                  step ts var rest
                (idx, Nil) ->
                  step ts1 idx rest
                (idx, Index{}) ->
                  step ts1 idx (Frame ts var rest)
            _ ->
              case var of
                Nil -> rest
                _ -> step ts var rest
    Empty ->
      case prefix of
        Empty ->
          -- The search term matches this node.
          case here of
            [] -> rest
            _ -> Yield here rest
        _ ->
          -- We've run out of search term - it doesn't match this node.
          rest

-- | An empty index.