I not disagreeing with you at all. My point is that on
Chessboard() you have 64 mostly independent variables. It’s much more efficient to represent the game move and mutating 2 of those variables, rather than creating a new state that is a copy of 62 and a new version of 2.
((And Yeah for the Chess pedants out there I’m ignoring castling where more than two change)
(And for the programming pedants out there I’m ignoring the possible compressions where you don’t create a state for empty squares at all, so 64 isn’t necessary)
The point still stands that mutating drops overhead significantly over a stubborn insistence on immutability)
Actually… well, Haskell’s definition of filter just uses list comprehension.
filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [ x | x <- xs, p x]
This literally reads “filter takes a function p, and a list xs. It returns a list that contains all elements, x, such that x is in xs and p(x) is true”.
That’s as far down the rabbit hole the code goes. I assume Scala is similar.
This means “length takes a list of stuff, and returns an integer.” "If the list is not empty, split the list into two parts: the first element (which we ignore) and a list containing everything after the first element, we’ll call this “xs”. Recursively call this function with this list called “xs”. Add one to this result.
How about I walk you though a method to count all of the prime numbers in a list, but without using any of the higher order functions, but using recursion. That might be instructive.
(First, note that the bit of code “1 to n” in Scala is just shorthand for “1.to(n)” where “to” is a method on the Int class that constructs a list of all the ints from 1 to n, so for now, take it for granted that we can construct a list from 1 to n easily).
We can write a function that counts all of the primes in a list as
def countPrimes(xs:List[Int]) = {
if (xs.isEmpty) 0
else if (isPrime(xs.head)) 1 + countPrimes(xs.tail)
else countPrimes(xs.tail)
}
To break this down, the function looks at the list and determines three cases:
[ul]
[li]If the list is empty, clearly there are no primes in it.[/li][li]If the list is non-empty and first element of the list is prime, the number of primes in the list is one greater than the number or primes in the tail of the list.[/li][li]If the list is non-empty and first element of the list is *not *prime, the number of primes in the list is just the number or primes in the tail of the list.[/li][/ul]
which are all manifestly true statements.
Note that this function does not have any vars and is entirely referentially transparent. If we want a function that counts primes up to a certain n, we can just put:
def countPrimes(n:Int) = countPrimes((1 to n).toList)
You could also write the function in another way that makes it a bit clearer where the accumulator is going, by using a second parameter in the function to indicate “number of primes we’ve seen already” to get:
def countPrimes(xs:List[Int], numWeveSeen:Int) = {
if (xs.isEmpty) numWeveSeen
else if (isPrime(xs.head)) countPrimes(xs.tail, numWeveSeen + 1)
else countPrimes(xs.tail, numWeveSeen)
}
def countPrimes(n:Int) = countPrimes((1 to n).toList, 0)
In this the cases change slightly:
[ul]
[li]If the list is empty, clearly there are no primes in it, so the number of primes is the number we have seen already.[/li][li]If the list is non-empty and first element of the list is prime, the number of primes in the list is the number or primes in the tail of the list, plus the number we have seen already, plus one.[/li][li]If the list is non-empty and first element of the list is *not *prime, the number of primes in the list is just the number or primes in the tail of the list, plus the number we have seen already.[/li][/ul]
I include this way of writing it because it makes it obvious that the accumulator has been replaced with a parameter that gets passed through the call stack, but still no vars.
I’m going to read it a few more times to make sure, but I think this explains everything. Thank you for that!
I’m a philosophy teacher. Someone once said about philosophy types that they “worry that what works in practice won’t work in theory.” I think you may have just assuaged my theoretical worries.
Out of wonder, does Scala have the same conceit as Haskell – that all functions only take a single argument (or no arguments)?
Because in Haskell, while I didn’t want to say it earlier,
filter prime [1…n]
Is technically two steps:
evaluate “filter prime” which returns an anonymous function of the type “[a] -> [a]”
Call this anonymous function on the list [1…n]
It looks like Scala just flat out uses multiple arguments instead of having the “all functions are uniform, multiple arguments are just tuples or currying”, is that the case or is the syntax sneaky?
Well, and the Haskell list comprehension implementation is obviously more complex and implemented in the compiler ;).
I only know regular expressions in the sense that I’m fairly good at proving things about finite state automata. These Ruby/Perl style regular expressions may as well be magic to me.
The only reason Prolog makes me cry is because it pretends it’s first order logic like a jerk and then makes you actually care about the order of your predicates. Literally 90% of all Prolog bugs I’ve ever had have been infinite recursion because I put one predicate before another.
.)
) and can have functions of more than one variable.