Finding roots by a scan

You will write a small solver that finds every solution of an equation on an interval by scanning for sign changes. It finds only real crossings, so a false root of the algebra never appears. The checker tests it on three equations of this course.

The idea. Write the equation as $f(x) = 0$, where $f$ is the left side minus the right side. A solution is where $f$ changes sign, so scan the interval on a grid and look at each pair of neighbours. Then narrow down the root by halving the interval again and again.

Your tasks.

1. Finish sign_changes(f, xs). Count the neighbouring pairs of points in the array xs where f changes sign.
2. Finish refine(f, a, b). Halve the interval $60$ times, always keeping the half where the sign changes. Return the middle.
3. Finish solve_all(f, lo, hi). Use $2000$ points from lo to hi. Return the list of roots, one for each sign change, found by refine.