Functional Programming, Abstraction, and Names
stephendiehl.com
stephendiehl.com
For example, to motivate groups, you could introduce the concept of a symmetry as a mapping from an object to itself that doesn't change its properties, introduce the idea of an isomorphism as a mapping with an inverse (where f and g being inverse means they compose to identity maps), put them together and postulate that a reasonable formalization of a symmetry is an automorphism (isomorphism from an object to itself), note that isomorphisms are closed under composition, and arrive at the definition of a group by considering sets of symmetries closed under finite composition (thinking of identity maps as the composition of 0 morphisms).
I'm sure there's a similarly conceptual way to motivate monads in functional programming. Hyland and Power have papers on algebraic theories of "effectful" operations and how they give rise to (finitary) monads, as one starting point.
There's some quote to the effect of: "Just as with men, a group is known by its actions." This was the only reference I could find off the top of my head https://gowers.wordpress.com/2011/11/06/group-actions-i/, but I've definitely heard the sentiment repeated in a couple different texts.
The sentiment expressed in this article might useful to hear if you're solely interested in learning how to use monad transformers or whatever in Haskell, eg, I know a fair amount of math, but very little category theory, and manage use monads just fine without any deep intuition as to why they're an important formalism. But if you want to develop your problem-solving skills, for example, I think "quiet contemplation" of axioms is pretty much always worse than working through several examples and absorbing some good exposition.
Here's a recent article that I found very though-provoking: http://cognitivemedium.com/invisible_visible/invisible_visib.... They quote some mathematicians discussing their visual intuition for one property of groups.
So not all the "groupiness" is captured by actions.
Also, Bill Thurston's beautiful "On Proof and Progress in Mathematics" [1] contains several ways to understand the derivative, in addition to it being a look into what a very distinguished mathematician thought of the nature of the mathematical pursuit. Pretty similar ideas, explored in depth.
Edit: Apparently this is linked to in TFA :)
I agree with the author that there is a danger of "dumbing down" concepts which risks casting a lower ceiling on our capacity for lofty thoughts. There is another risk, though, that as someone becomes overfamiliar with a subject, they lose the ability to empathise with people who cannot immediately grasp the same concept. See [0] for a mathematician's reflections on revisiting his own DPhil thesis five years on.
I would counter that making abstract concepts accessible, broadens the reach of concepts which allows for the greater potential of new concepts being synthesised. Put in another way, the more people that have some grasp of an idea, the more humanity will progress.
Using Group Theory (strictly Point Groups) as an example, there are plenty of Chemists out there who are doing great work building catalytic organometallic compounds who use Group Theory. I'm sure plenty of them wouldn't be able to tell you what a Group was nor even express what the general basis of a Group are.
So yes, while there is a need to push ourselves our capacity to think increasingly abstract, we should also not be afraid to ruthlessly simplify as the world is big enough that individuals will derive benefit from diluted concepts for generations to come. What's more is that as concepts get simplified, the next generation can short-circuit their learning to achieve greater understanding at an earlier stage in their lives.
As I've always thought: if every human is born roughly equal, thank god we haven't had to "re-derive" making fire every generation otherwise how would we ever have time in our lifespans to learn about quantum mechanics and more.
[0]https://medium.com/@fjmubeen/ai-no-longer-understand-my-phd-...
Mathematics is one of those fields where it is difficult to simplify. Period. But in addition, the practitioners often actively resist this simplification. Mathematics is firmly rooted in proof, but not all mathematics education needs to be firmly rooted in proofs, and for that matter, not all mathematics education must be rooted in mechanistic repetition of solution techniques. There is perhaps a way to endow people with these concepts when they couldn't otherwise arrive at them through rigorous proving.
Indeed it would be great if there is such a way. But sadly, without proofs, these concepts are half baked and are thus harmful as they give a false sense of understanding and thence the more harmful overconfidence.
I remember the great thought that applies to entire math education (and also to education in general) - "There is no royal road to geometry." [1]
[1] https://en.wikipedia.org/wiki/Royal_Road#A_metaphorical_.E2....
Actually, coming up with proofs often requires creativity. If anything, the emphasis on memorizing formulas and solution procedures comes from an aversion to teaching proofs.
I am coming to believe that computational thinking != mathematical thinking.
I'm able to reason logically in code because I'm able to reason logically about things in the real world and natural language supports that. I was able to code (early teens) and think computationally long before I ever knew there was such a thing as formal logic and truth tables and all that.
And let's consider names. In Ruby I knew what the module Enumerable did before I ever read the docs. Monoid? I don't think so. And I have some math background. What about all the potentially very talented programmers that have a non-math background? I don't buy that we need the beginnings of 3rd-level math to be decent programmers. In fact, I'll go further. I think think that the programming landscape is too math-oriented. I know someone who had a curiosity about recursion so I started explaining the concept via factorials as one does. Said person gets little panic attack. Our default explanations oughtn't involve math. Our names should avoid high-level math concepts divorced from everyday speech and concepts. By all means use aliases if you want but give the rest of us something to hang our conceptual hats on.
If they don't know what something means, they can educate themselves. I learned about monoids in my first course in linear algebra at the university in the first month. My math background at that point was "finished highschool". Just because it has a name that does not appear in everyday language (unlike enumerable) it does not mean the concept is difficult to grasp.
You just proved my point.
I'm not in any way anti-math.† Imagine that monads were a part of Scratch (the children's programming environment), and I was trying to explain them to my young daughter. If she couldn't get it should I say to her, "this is only high-school math plus a bit more, come on, don't use the fact that you're 11 as an excuse". The other day somebody pointed out that in Tufts they have shown that children as young as five can think computationally. This is the level I'm talking about. I'm talking about being able to teach programming to people who are normally (for whatever reason) math-phobic.
(† I took three years of 3rd-level math.)
Re: Reflection and metaprogramming. I guess you're suggesting teaching her some variant of Lisp? In the Coder Dojo I brought her too they/we were doing either HTML/CSS/JS or Scratch or Python. And all simple examples. I guess a version of reflection and metaprogramming exist in Python (I don't know off the cuff (I'm a Rubyist) but I presume so).
I had to Google object identity. Is this [http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes...] what you mean?
I wasn't talking about Lisp specifically. Many libraries and frameworks written in “mundane” languages like Python and Ruby make use of metaprogramming facilities to great effect. Now, you can't say with a straight face that monoids are scary but metaprogramming is not.
> I had to Google object identity.
In most object-oriented programming languages, every object has a unique identity, which is assigned when the object is constructed, and from then onwards can't be mutated. The uniqueness of these object identities can get in the way when you want to program with compound values, for example, the Java expression `new Point2D(2,3) == new Point2D(2,3)` evaluates to `false`, simply because the objects have different identities.
> Is this [http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes...] what you mean?
Yes.
How exactly are you defining “computational thinking”? Is it “running the calculation yourself, as if you were the computer”? “Putting yourself in the computer's shoes”? “Empathizing with the computer”?
> And let's consider names. In Ruby I knew what the module Enumerable did before I ever read the docs. Monoid? I don't think so.
Every technical discipline has a jargon, precisely because their practitioners need to express ideas that can't be conveyed using only everyday language. Programming is not an exception.
And you picked a particularly bad example, because, while there exist mathematical objects whose definitions are very obscure and hard to get an intuition for, monoids aren't among them.
> I know someone who had a curiosity about recursion so I started explaining the concept via factorials as one does.
Recursion is just self-reference. For example, you could've told said person “your ancestors are your parents and their ancestors” - a perfectly good example of a recursive definition.
If I didn't know about functions your explanation of “your ancestors are your parents and their ancestors” would give me some insight into the nature of recursion but not a whole lot.
This is a contradiction in terms. By definition, jargon isn't ordinary language. It consists of words that either don't exist in ordinary language (e.g., “metaobject”), or whose technical meaning is different from the ordinary one (e.g., “kind”).
> If I didn't know about functions
Are you talking about mathematical functions or procedures in computer programming? If the latter, I insist: recursion is not limited to procedures, it can be any form of self-reference. For example:
(0) A list is either empty, or has a first element and a tail list.
(1) A binomial tree of rank r has a root element and, for every 0 <= q < r, a child tree of rank q.
(2) The sum of a list of numbers is 0 if the list is empty, otherwise it's the first element plus the sum of the rest.
In fact, one of the major lessons of functional programming is that recursive procedures are naturally defined on recursive data structures - they always go hand in hand.
> your explanation of “your ancestors are your parents and their ancestors” would give me some insight into the nature of recursion but not a whole lot.
It wasn't an “explanation”, just an example. But if you think a transitive closure (namely, of the parenthood relation) isn't a good example of recursion, arguably you don't understand recursion.
I don't need your pointless definitions, nor do I need your corrections, your insults neither.
Perhaps where we were at cross-purposes is that when I said recursion I meant recursive procedure but you were thinking of recursive data structures (and possibly also of recursive procedures). Why I contradicted you was that I didn't think your parent/ancestor example was a good explanation for recursive procedures but, yes, I now see that it is a good explanation of a recursive data structure. In fact, as you well know, in a tree data structure we call the node upstream from the current node the parent, and the node(s) downstream the child(ren). Your dismissal of my knowledge felt like an insult. I probably shouldn't be so thin-skinned.
† I know, I know, who am I that I get to decide who is proper or not. But I once gave grinds to this guy who was forced to do computing by his folks and he had no interest and I couldn't get him interested and he didn't seem to be able to wrap his head around simple programming constructs. Maybe more a reflection on my ability to convey knowledge than his ability, sure.
If you thought the only recursive thing in existence is recursive procedures, yes, arguably you didn't understand recursion. (Which is fine, by the way - you can be a very successful programmer without understanding recursion.)
> Perhaps where we were at cross-purposes is that when I said recursion I meant recursive procedure but you were thinking of recursive data structures (and possibly also of recursive procedures).
When anyone says recursion, I understand recursion. Limiting your idea of “recursion” to recursive procedures is like limiting your idea of “black” to black T-shirts.
> Why I contradicted you was that I didn't think your parent/ancestor example was a good explanation for recursive procedures but, yes, I now see that it is a good explanation of a recursive data structure.
My parent/ancestor example was an example of a recursively defined relation, not a data structure. (I deliberately picked an example that most programmers wouldn't relate to code.) In Prolog it could be written:
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Z) :- parent(X,Y), ancestor(Y,Z).
To use a lever do I have to understand physics?
No, the point of abstraction can be to be vague, and to delimit the boundary of a concept that is not quite clear (yet). It is not a mathematical abstraction then, but something you are experimenting with to find the right kind of laws that are supposed to govern that concept. Most real-world programs contain many such concepts for which either no good mathematical abstraction exists, or for which nobody has had yet the time and money to find a good mathematical abstraction.
https://github.com/fantasyland/fantasy-land
Also - does anyone show me a practical usecase of the reader monad ? cant you just use partial functions ?
if I am not mistaken isn't reader monad just :
foobar.config ({'name':'hello'});
foobar.run ({'age':'34'});
function f() {
var m = getState().chain(state => {
// ...
})
return m;
}
var f = wrapped(function* () {
var state = yield getState();
// ...
return;
});
var m = f();
m.runWith({currentUser: request.user})
All the other analogies in this thread are wrong in terms of what the real API looks like. The real API looks almost exactly like Promises, with `chain` instead of `then`.
This in turn also explains why monad transformers are so important. Having access to just the current user w/o passing it around isn't very useful if e.g. you can't do IO, but having both - now we're talking!
It seems the reader monad just delays execution of some code until you call 'runWith' and you can define state variables throughout your code before calling runWith.
var result = m.runWith(...)
var m = [1,2,3]
.chain(x => [x, x * 10])
.chain(y => y < 2 ? [] : [y])
Same API (monad), totally different functionality.
so anything that is like this :
values = ['coffee','water']
AfterWebSocket = values.sendToWebSocket()
AfterWebSocket.compute (eachValue => x*2)
is that it ?
For array chain takes a function that returns an array. For promises, chain takes a function that returns a promise object. For Reader, chain takes a function that returns another reader object.
Here is a complete class Reader:
class Reader {
constructor(computation) {
this.computation = computation;
}
runWith(data) {
return this.computation(data)
}
chain(readerReturningFn) {
return new Reader(data => readerReturningFn(this.computation(data))
.runWith(data))
}
static of(val) {
return new Reader(data => val)
}
static getState() {
return new Reader(data => data)
}
}
var r = Reader.of(5).chain(x => Reader.getState().chain(y => Reader.of(x + y)))
r.runWith(2)
> 7
And yes, monads in programming are this simple. Mathematical monads are a wider generalisation of computing monads (just like Iterable would be something more general in the real world, not "things with a next() method that acts like this"), but in terms of programming its a shared API (chain) that acts in a certain way (chains to another object of the same type and flattens one level, whatever that means for the concrete implementation)
More like a specs that if people follow the world would be a better place ?
what is a monad transformer ?
I understand your code - but fail to see why its so useful :(
For example there can be a GraphQL monad. Instead of Promise.all you would use GraphQL.parallel(otherMonads), and the implementation can transform that to a single request to the server instead of multiple ones.
Similarly there can be an ORM monad that avoids the n+1 queries problem. parallel(Users.get(id)).chain(users => ...) will transform the parallel query to a single SELECT ... IN query.
Also, have you tried passing the current user around in server side code, everywhere? Its really tedious to do, and Reader solves that!
A monad transformer is (more or less) a function that takes a monad class and returns a new monad class (yes thats the class object, not an instance). So if for example Future were a monad, and you wanted to add Reader functionality, you would create a new class PromiseWithReader:
var FutureWithReader = ReaderT(Future)
function getUserPosts() {
return getState()
.chain(state => Posts.getForUserId(state.user.id)) // cheating a bit here
}
getUserPosts.runWith({user: req.currentUser})
.fork(posts => res.json(posts))
p.s. Future implementation, based on robotlolita's minimal Future class: https://gist.github.com/spion/b433a665ca51d6c38e9f
I read your post and sent you some messages on gitter, it seems you do not use gitter a lot :(
Here is an implementation of ReaderT, how it can transform a Future to provide "local readonly state", and a usage example:
https://gist.github.com/spion/b433a665ca51d6c38e9f
Since its JS, I also added automatic lifting, just to annoy Haskell programmers ;)
Basically, you have some computation/object that isn't complete without some "setup info" which, from the point of view of the code being written, is "just there". Like if you had a program that needed access to a particular interface, but you didn't want to manually pass it to every function that cares about it; instead you'd make an object with that interface as its state and write your program as methods on that object. That's just Reader in disguise.
In fact, C++ methods are basically in the Reader monad; they all have an implicit "this" argument which the compiler plumbs around for you.
You use the reader monad the thread the same input to multiple functions that may also take additional intput, and also have their own outputs.
You have to keep in mind that since Monads are so common and useful, many languages have syntactic support for them. C#'s LINQ query syntax, scala for expressions and haskell 'do' are all 'monadic comprehension'.
The resulting class can also have other variables and inputs.
Is that a correct analogy ?
Inheritance is more similar to monad transformers.
But partial functions are not always as clean as you think they are. When composing with pure functions for example, you'll save a lot of boilerplate lambdas if you use the monad.
> This style of designing abstractions is often quite foreign in programming in the large, and other schools of thought (see Gang of Four) actively encourage weaving cryptic metaphors and anthropomorphising code as a means to convey structure.
The GoF didn't try to anthropomorphize, all they wanted to do is put names on things. Sometimes, these names have some meaning (e.g. Factory pattern) and other times, they have none (e.g. the Flyweight pattern).
The important concept that the GoF book introduced was to name things. What word was used for these names matters little.
In other words, similar to what the author of this piece is trying to achieve (and he does so pretty convincingly).
They could've called it “handrolled hash consing”, which is exactly what it is.
The first option (intrinsic names) has advantage in reusability, the other option (extrinsic names) has advantage in readability for particular application.
Maybe because I started studying pure math later in life and I had to be more conscious about it, I have thought a lot about what it means to understand and think well about mathematical concepts. I think the author misses the point of the question, "What is a group, actually?" after giving the formal definition of a group. The student was asking, "How am I to understand groups?" And more generally, understand mathematical concepts. Here are some tools I learned for understanding groups:
- The informal definition. What's a group trying to model?
- The formal definition.
- Standard examples. What's the simplest? What are the "canonical examples"? Mathematicians love this question. See, for example (more links inside):
http://mathoverflow.net/questions/3242/canonical-examples-of...
http://mathoverflow.net/questions/4994/fundamental-examples
- What happens if we remove parts of the definition? Inverses? You get a monoid. Identity, too? A semigroup. What if you add additional properties? You get things like commutative groups, rings, etc. You'll want examples of these other structures, too.
- The motivating history of groups. Who defined them, and why?
- When mathematicians encounter a new object, the their first instinct is to classify it. Can we classify all groups? (No.) Are subclasses of groups that can be classified? Yes! Finite simple groups, finitely generated commutative and Lie groups are all hugely important examples.
- Related to classification, what are the general properties of groups? What can you prove about them? This help develop an intuition for "how they behave".
- The goal of math is to prove theorems. What are groups good for? What can you prove with them? This sets group theory in relation to other mathematical subfields.
- As mathematical objects go, groups are relatively concrete, but for many objects, it can be a challenge to describe actual examples. How do you describe examples of groups? Tables, presentations (generators and relations). When do two presentations describe the same group? (Hard.)
- What constructions exist on groups? Products, quotients, semi-direct (twisted) products, free products, fibered products, etc. Category theory suggests we should study not only groups, but relations between them. Groups form a category. What kind of category? What universal constructions hold in the category of groups?
- What are the kinds of groups? Commutative, finite, finitely generated, Lie, matrix, simple, etc. All the above questions apply again! Canonical examples, history, informal definition, constructions, classifications, categories, etc.
I.e.:
Identity For any element a in G there is an element e where e⋆a = a⋆e = a.
Invertibility For each element a in G there is an element b where a⋆b = b⋆a = e, where e is the identity.
Invertibility: given any a, there is b such that a⋆b = b⋆a = e. For two different a's you get two different b's.
As example let G be a set of all strings and the operation is appending. There is element e == "". For any string a it holds that if you append empty string to any side, you get the original string back. However there is no inverse. You can not append two string to form an empty string. Apparently, strings with appending do not form a group.
Group example: let G be a set of all integers and the operation is addition. Then e is 0, as for all a it holds that a + 0 = 0 + a = a, and for each a you can find -a such that a + (-a) = (-a) + a = 0.
If you want an example, think Z (integers) and "+": there is an element of Z, namely zero (0), where the identity rule tells us that x + 0 = 0 + x = x and the invertibility rule says that for any x in Z, there is an y in z such that x + y = 0
Invertibility is existence of Yin for a Yang, superhero for a supervillain, north pole for a south and combining them creates a neutral.