"Wolf fence" algorithm: Edward Gauss described this simple but very useful and now famous algorithm in a 1982 article for communications of the ACM as follows: "There's one wolf in Alaska; how do you find it? First build a fence down the middle of the state, wait for the wolf to howl, determine which side of the fence it is on. Repeat process on that side only, until you get to the point where you can see the wolf."[10] This is implemented e.g. in the Git version control system as the command git bisect, which uses the above algorithm to determine which commit introduced a particular bug.

[https://en.wikipedia.org/wiki/Debugging]

So now you know what that thing you always end up doing is called :)

I.e. if I asked you to find a squeaky noise coming from somewhere in your house. Does it make sense to "binary search" your 3D 3-story house?

Wolf fencing makes more sense.. stand on floor 2, see if it is on your floor. Or is it coming from the stairwell to floor 3, or the starwell to floor 1? You just used 1 step to narrow your search space down by 1/3.

How would you sort your house so you can binary sort it?

And the bit about cutting the search space to a third (which is what I believe you meant, instead of cutting it /by/ a third) is something you can also do when searching a list, but IIRC halving is preferred because it has better worst-case time-complexity. You can always split a list into 1/3 + 2/3 instead of 1/2 + 1/2, but you risk having to search the 2/3 every time, etc.

In both cases you could argue that you are "cheating" because there is a computational process of some kind doing at least O(N) work each time (the computer in the debugging example, the universe in the wolf example), giving O(NlnN)+ overall, strictly worse than an O(N) linear search. However, you have to ask yourself in this case if it makes sense to equate the time taken by the computer/universe to run one unit of its computation with the time taken to run one unit of your* search, and in many cases it doesn't. In the end it's just a model and it's up to you to choose what to measure, approximate, and exclude.

If someone tries to argue that there is fundamental philosophical truth that makes one model better than the other, start digging down into the physics of the CPU -- how much O(N^N) quantum computation did the universe have to do in order to bring you a single CPU cycle? God only knows, but the time it takes is nearly constant, so it makes sense to ignore. Even the most hard-core theoretical algorithms expert is just as "guilty" of this kind of approximation as you are :-)

As per analogy, you're not checking an animal in Alaska to see if it is a wolf, you are waiting till the wolf howls (side effect of wolf-existence) then focusing your efforts in that area.

So you can't really use wolf-fencing to say... find a number in an array; it makes no sense.

So apply a binary search to an effect instead of a value.

It seems to be used only in the context of debugging. While with git bisect, we are also repeatedly ~halving the remaining search space, the list of commits isn't "sorted" like the precondition for binary search.

You could argue that commits are sorted against time. But I would say that's different because we don't know which commit hash we're looking for -- we just want to find the point in time when our code stopped working, not that I've ever had to use it before ;).

Good point.

One may think that in some sense, it is sorted: The history is sorted into "good" commits (before the bug was introduced), which are followed by "bad" commits (after the bug was introduced).

However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced).

This works because bisection doesn't require a sorted list, it just needs a continuous function. And any sequence is just a special case of that.

I don't understand this comment. Need for sorting the list is essentially the same in both cases, because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later". A binary search makes the assumption of sorting because it's premised on the idea, "Whatever number I find, every number that comes after it will be larger". Same with bug-finding in a git history, it assumes "If I find a point in the history where the problematic behavior exists, it exists at all points after that for the same reason."

If you had an "unsorted" history where a bug was fixed and then reintroduced in another way, your binary search may fail to find the immediate cause of your problems in the same way that an "unsorted" binary search would fail to find what it's looking for.

Yes, and this is perfectly okay for "git bisect".

> Need for sorting the list is essentially the same in both cases.

No, bisection does not require sorting, it just needs a continuous range whose endpoints have different signs. Then, it will always find one point where the signs on both sides differ. (In real analysis, this means finding a zero. In discrete maths, it means find the introduction of a sign change.)

In other words, when starting with a range from an old "good" commit to the current "bad" commit, it will always find a "good" commit directly followed by a "bad" commit.

This is why "bisection" is a good term for this Git algorithm, while "binary search" would be misleading. (Even though bisection and binary search are almost identical algorithms. They mostly differ in their input assumptions and output guarantees.)

Bisection makes no assumtion on any sort order, but guarantees to find one point of bug introduction in logarithmic time. It does not give any guarantee to find the lastest point of bug introduction -- unless, of course, your history does have just one such point.

> If R is the continent of Africa and we select R_n as that subregion which contains the biggest lion in Africa, we have an algorithm for capturing a big lion—we simply build a cage around point z_0.

This problem is significantly worse in Haskell than in most other languages. Usually you lose at most a constant factor in performance if the compiler doesn't optimize as much as you expected, but the lazy evaluation can actually change the asymptotic memory complexity. I have been bitten by lazy evaluation several times by writing code that I expect to run in constant space and then finding it require linear amount of memory because of the evaluation order.

This is really a serious issue. The only other language where I ever had this issue was SQL. I had a project where we have lots of nested Views. We had to rephrase the SQL in sometimes very non-obvious ways, introducing intermediate Array results, CTEs, switching between sub SELECTs and JOINs -- all this just to convince the Query Planner to use a different Query Plan. That made a difference between < 1 second or a few minutes.

In the end, this is why I prefer languages OCaml or SML over Haskell. (Rust on the horizon)

Roughly speaking, in Haskell you can prove "just" correctness, while in OCaml you can prove correctness as well as performance.

It seems to me that there is some connection/analogy with garbage collection. Garbage collection also makes reasoning about space usage of programs difficult, since it happens in some future, yet unspecified, time. Yet GC is almost always regarded as good (although historically there was a lot of fight against it), yet lazy evaluation is regarded as bad by many. Maybe the issue really is "good enough compilers"?

As an example, I wanted to accumulate a list of summary data as I iterated through a recursive function. Through a coding error, the elements of the list (although not the list itself) were not evaluated until all the iterations were complete. This meant that, instead of a list of structs, which I thought I had, I had a list of zero-argument functions that, when called, would yield structs, _each of which contained a reference to a large array computed at an earlier iteration of the computation_.

So, I hemorrhaged space. This was a fuck-up, not a missed optimization.

Additionally if you expect me to 'write, build, run, repeat' just to test my code, then you better hope you have a fast compiler else I'm going to start associating using your language with the same amount of interest as watching paint dry.

What does that even mean in a language with no explicit model for code sequencing?