[Haskell-cafe] A Thought: Backus, FP, and Brute Force Learning

[Albert Y. C. Lai]

On 13-03-20 06:54 PM, OWP wrote:
> For me personally, one thing I enjoy about a typical procedural program
> is that it allows me to "Brute Force Learn".
[...]

1. I believe that you can also stare at functional programs and figure 
out as much as what you can with procedural programs.

It only requires knowing the language and the libraries. And you can no 
longer argue that functional languages are more declarative or higher 
level than procedural languages. Once upon a time, it was true, with 
parametricity, algebraic data types, higher-order functions, and list 
comprehensions; now procedural languages have them too or competitive 
alternatives.

2. I doubt how much you can learn from staring, be it functional 
programs or procedural programs.

I posit that at most you're just reading aloud in your native tongue how 
to execute the program. But then you're just competing with a computer 
at its job. You barely know what requirement the program satisfies, much 
less why the program satisfies that requirement.

(With the exception that the program contains no iteration or recursion, 
or contains just boring iteration or recursion such as walking over an 
array.)

I do not mean that you lack jargons like "gradient" and "matrix", no. 
You can explain in your own words, if you know the right idea but just 
not the jargon. I am positing this: apart from telling me how to execute 
the program, you cannot explain the purpose of the program, not even in 
your own words, because you do not know.

Here is an example I learned recently. It is ingenious.

Let A, B be arrays of the same length N. Their elements are numbers. 
They use 0-based indexing. They are the input.

int h=0, i=0, j=0;
bool answer;

while (h<N && i<N && j<N) {
     int Aih = A[(i+h) % N], Bjh = B[(j+h) % N];

     if (Aih == Bjh) {
         h = h + 1;
     } else if (Aih > Bjh) {
         i = i + h + 1;
         h = 0;
     } else { /* Aih < Bjh */
         j = j + h + 1;
         h = 0;
     }
}
answer = (h >= N);

answer is the output. What does answer say about the input?

The algorithm is no different in Haskell (it makes me use lowercase a, 
b, n):

answer = go 0 0 0
go h i j =
     if h<n && i<n && j<n then
         case compare (a!((i+h) `mod` n)) (b!((j+h) `mod` n)) of
             EQ -> go (h+1) i j
             GT -> go 0 (i+h+1) j
             LT -> go 0 i (j+h+1)
     else h>=n

3. I completely refuse to believe that you literally do not know what 
you're doing before you start.

If it were true, it must be like this: You throw dice 500 times to 
generate a 500-character file. If the compiler doesn't like it, you 
throw dice more times to decide what to mutate in that file. Eventually 
the compiler surrenders. Now, and only now, you stare at the file for a 
few minutes, and discover: it implements doubly linked list! It will be 
useful when you write your own web browser later, it can help provide 
the "back" button and the "forward" button...

No, it has to be the other way round. You have to decide to attempt a 
web browser project or whatever in the first place. You are vague about 
details, what not to include, what to include, how to do them... but you 
know vaguely it's a web browser. After some time, you have to decide 
which part, however small, you start to code up. Maybe you decide to 
code up a doubly linked list first. Now you type up something. You type 
up something knowing that the short term goal is doubly linked list, and 
the long term goal is some kind of web browser or whatever project it 
is. This much you know. And while you type, every key you type you 
strive to get closer to a doubly linked list in good faith. Maybe 
sometimes you're creative, maybe sometimes you make mistakes, maybe you 
write clever code and I can't understand it, but it is not random 
typing, you know the purpose, you have reasons, you understand, and you 
don't just stare.