Unfortunately, you're in bad shape as soon as you have your data in a Haskell list, since it's a linked list. It's suitable for small things, but if you want to go larger than that, you're going to need to use arrays or something. Haskell lists aren't just ordered in principle, they're ordered structurally as well because you can't randomly access them at all.
That said, for anything that fits in memory, it's so easy for a parallel map to preserve order that it probably should anyhow, and if it doesn't fit in memory it's still not that hard and probably a better default. (If you've got some sort of map with wildly variable compute times per element, then you could starve the thing that finally emitting them in order if you hit a very expensive particular element, and you could potentially have gotten better throughput if the rest of the system could just keep working around it and ignoring order. But I'd still expect order-preservation to be the default such that I'd have to tell my parallel map that it's OK to ignore order.)
It seems like the monoid-thinking just obscures. Positive integers under addition are not a monoid (no identity) but you can still map-reduce their sum of squares. All that you really need is associativity, and associative operations are associative.
There seems to be a lot of work to get not very much. Maybe the point of this article is more about faffing around with quickcheck but the conclusion should basically be:
1. Parallel [efficient] MapReduce requires a commutative monoid for deterministic results
2. A naive implements of parallel MapReduce in haskell using par doesn’t because it will only do reduce operations in a certain order. Imagine if the map for every second element took 0s and the others took 10s. In normal mapreduce, you would reduce together the fast half of the results as they come in but in this haskell implementation you would need to sit on them and wait until the other adjacent elements come in. In the article’s very naive implementation, you can’t even reduce together the first two elements together until you’ve reduced everything after them (modulo some weirdness around lazy evaluation)
I think if one thinks of mapreduce as an operation on sets not lists, it should be obvious that the monoid must be commutative.
I think the main point of the article is that you can use property based testing not as a software quality tool, but as a very quick way to verify/disprove your assumptions. The MapReduce stuff is just a simple enough example to illustrate the point.
I've used property tests the exact same way many times. In complex algorithms assumptions can be hard to think through, but a property testing tool can find counterexamples shockingly quickly.
But that's basically what the conclusion is, isn't it? The author set out with 'obviously the monoid must be commutative', fuzzed it and came to the second point you mention. This all may be very obvious to some, but I found it an interesting read that reminds that one should never fail to question one's assumptions and understanding.
I think that confusion stems from thinking about an operation that ought to be defined on sets, mapreduce, as one defined on lists. Your monoid obviously needs to be commutative for the former and not the latter. And the implementations are pretty similar in serial but quite different in performance in parallel.
I think the efficiency then hinges on the distribution of your slowness. Is there a slow mapping step for some elements? Then it should be fine having them all near each other. All fast-mapped values before and after can be reduced in the time the slow data is mapped. Only if somehow every second value is slowly mapped you have to wait for reduce to even start.
If your reduce is slow for some inputs, its better to have those inputs near each other, as all consecutive values before and after can be reduced during that time.
And if every step is somewhat constant time, I don't think reordering (that's basically the same as combining random elements instead of consecutive ones) the input does anything.
There’s two parts of the efficiency. One is memory: if you have a bunch of partial results hanging around for adjacent elements to reduce with, they will use memory. The other is the time and yes, if you have a map reduce on lists implementation that (unlike the author’s) reduces any two adjacent mapped elements then you’ll only be harmed by more pathological cases like the one I described, but I don’t think it’s that obvious that that case is unlikely (eg let’s say you’re processing some logs. You get one file per day from a system that runs from 9am to 5pm and one from a run from 5pm to 9am. It seems likely that one file would typically take longer than the other to process) And reordering your elements to optimise around this means that you’ll get different results, unless you’re using a commutative monoid! If your monoid isn’t commutative then reordering likely isn’t an option.
I don't get these kinds of comments. Have you spent any time learning any of this? If not, then why do you say that "this is very complicated and I'm too stupid"?
If you find a text in German and you don't understand a word, because you have never studied German, do you think you are too stupid to speak German?
I think the mistake is the assumption that there must be a quick and easy analogy to a language with C-style syntax (I'm simplifying a bit, but you get the idea).
This is sort of like PG's Blub paradox: the reader opens an article, sees a bunch of seemingly bizarre syntax and novel terminology, can't easily map it to something he/she knows from C/Java/Python/Javascript, and panics.
For some reason people don't assume the same about natural languages. No Western reader will take a peek at a webpage written in Japanese and cry "I can't understand how people speak this language". (Not in this day and age, at least).
I'm guessing it's because most people spend very nearly their entire careers nestled comfortably within a single programming language family. So one maybe gets used to the idea that one should be able to decipher an unfamiliar programming language just by reading it carefully, without needing to do any background study first.
It's most pronounced with lisp and ml-style languages, but I've also seen Java lifers bounce off of things as innocuous as Python's list comprehensions.
I get a little bit wistful when I see people bouncing off of exotic languages. Where's the delight in a chance to discover something new, and the excitement of a new thing to wrap one's mind around? It makes me wonder if some magic has been lost, or isn't being passed along like it should be.
> For some reason people don't assume the same about natural languages.
As mumblemumble says, I think this is due to a blinkered understanding of programming, combined with the mistaken belief that if you know one programming language it's pretty straightforward to learn any other language.
If someone knows Java, Python, and JavaScript, and their idea of exotic languages are Rust and Go, then they have no appreciation of how diverse programming languages really are. Lisp, Haskell, Forth, Prolog, and assembly, will strike them as completely alien, which should be fine except they're under the impression that it's meant to be easy to learn another language.
> ...and yet children can do it. Use that as a lesson.
Children? No, it takes them up to middle school to get somewhat proficient with Kanji knowledge for daily life, but they can still not read a lot of Kanji at that point.
Trust me you can learn this too on the same time span and semi-full immersion if you started now.
> This is sort of like PG's Blub paradox: the reader opens an article, sees a bunch of seemingly bizarre syntax and novel terminology, can't easily map it to something he/she knows from C/Java/Python/Javascript, and panics.
I analogize Blub more to Legal Latin: you're using an uncommon reference point to explain the material that could be explained perfectly well without it. The example I'd give is call/cc; I'm sure I could give a thorough description of how call/cc works, and leave a lot of programmers in the dust by doing so. Or I could explain how the yield operator works, and most of those some programmers would suddenly understand what I'm talking about. But they're basically the same thing (the only real difference being that yield continuation magic can only operate within its generator function, whereas call/cc works across function boundaries).
> you're using an uncommon reference point to explain the material that could be explained perfectly well without it
Should Haskell practitioners cater to C-like developers? If so, why bother with Haskell at all? This is one step removed from saying "just write an improved C and forget about Haskell", and in fact there have been attempts at it! It's just that they aren't Haskell.
Is it too much to ask of people trying to understand Haskell code to learn about it first?
While true, there's a certain level of "we must use math concepts to describe things", which while true sometimes just seems unnecessarily silly. "The Monoid 'Natural Numbers under Addition' is associative" => "putting brackets in any place when adding >2 numbers doesn't change the result".
It adds to the perception of "I need to understand masters level maths to use Haskell".
Associative - nothing. But "Monoid 'Natural Numbers under Addition'" is a fancy name for adding numbers since we don't really care about the concept of monoid in this case.
But we do care. Once you put a name to something, you realize it can generalize beyond numbers and addition. If you don't name it, you don't see the generalization. And these generalizations matter a lot because Haskell is built out of them.
Besides, learning what a "monoid" is is not harder than learning what a for-loop is or a hash map. They aren't natural concepts, but they are easy to learn by programmers.
I don't think it matters in this specific case. (and if the generalisation really matters, why would we restrict it to natural numbers?) Sure, every single concept mentioned is simple in isolation - but put enough of them together and it's starting to become an effort to process unless you're used to that kind of communication.
To compare it to spoken communication, there's a threshold where very formal queen's English from an extremely eloquent person makes them sound like an obnoxious showoff rather than fancy and serious. I feel like posts about Haskell often touch that threshold without a good reason. But that's my very subjective opinion.
We don't, that's the point. We abstract it above numbers, so that we can find that lists and natural numbers and many other things share the same "shape" when looked at from certain perspectives.
It's not about showing off, but about finding generalizations -- finding the "shape" of things -- that allow us to use the same abstractions over them.
And to talk about these shapes, we must use the appropriate vocabulary. It's shorter and more precise. Just like you say "function" instead of explaining what it means in lots of words every time you mean function.
> Have you spent any time learning any of this? If not, then why do you say that "this is very complicated and I'm too stupid"?
not all things require the same amount of effort to be understood at an adequate level.
> If you find a text in German and you don't understand a word, because you have never studied German, do you think you are too stupid to speak German?
there are definitely people that are able to look at a german text without having ever studied german before and make sense of it in a rough way
> there are definitely people that are able to look at a german text without having ever studied german before and make sense of it in a rough way
Sure, by knowing both English and Swedish, German has sufficiently little "uniqueness" left to it that I can often get a rough idea of a German text despite never studying it. But how is this different from reading Haskell when you've previously worked in Scala and Rust?
How do you get anything done in Haskell, you ask? Here are some steps:
1. Read a Haskell book and/or tutorials online, some of which are free.
2. Try writing simple software and reading other people's code. Ask for help when you get stuck. The Haskell community tends to be friendly and helpful.
3. Write your own non-toy code, hit real world problems and solve them.
The path is very similar to other languages, except that because Haskell doesn't share the same lineage than C/C++/Java/Javascript, you won't be able to "wing it" by skipping the steps above. That's likely the source of your confusion: you can't as easily draw analogies to the languages you're already familiar with.
Note that learning Haskell from exploratory articles which are meant for an audience already familiar with the language is not the best way to go about it. This is like trying to learn Java from an article describing the subtleties of the garbage collector in some interesting corner cases: it'll just confuse you and it won't have any practical lessons for the novice.
People can and do write actual production Haskell code, so it can't be that hard.
That jumble of letters does impart deep meaning. In this case it tells me very precisely that you banged on your keyboard at random, because that's got an infinite kind error in it.
Documentation is powerful stuff, especially when it's machine-checked the way Haskell type signatures are.
Don't be too hard on yourself. It's not stupidity but unfamiliarity. Haskell's roots are pretty distinct from most other popular programming languages, so it's normal if your existing notions from unrelated programming languages don't translate. Like if the article were written in Finnish.
Haskell programmers have delved the deepest and furthest in the mines of a certain kind of Truth. Decades under the earth gives them strange language and strange ideas - the monoid, applicators, all sorts of things.
You can follow them to their deep dark places - but they have travelled far, and finding them in their tunnels is a journey of many moons. To the Haskell programmer, us surface dwellers are all confused - missing the essential True Names of programming. Don’t despair - you can travel where you will; but know that discovering the hidden truths will humble and age the best of us. Why? I know not. Perhaps realising we’re small and stupid is the cost of staring into the abyss of Math.
Haskell is what happens when you take the idea of pure functions (i.e. no side effects) _really_ seriously, and try to create a programming language that works in that world (modulo mechanisms for doing the side effects you _need_ such as I/O).
It turns out that when you do that, all sorts of stuff that simply doesn't fly in other languages "just works", particularly around representing things using structures otherwise rarely seen outside of mathematical logic and category theory. This is all very powerful and elegant, but it means the landscape is unfamiliar, confusing, and intimidating to programmers who don't have that background or the inclination to learn about it.
Hence all the monad tutorials — not because monads are particularly special, but because beginners encounter them quickly due to IO, so they need some sort of explanation (it's like how if you teach a beginning programmer Java, there's loads of ceremony to explain around classes and public and so on just to do "hello world")... whereas you can get away with using haskell for longer without learning about, say, functors and monoids — though it somewhat misses the point of the language if you do so.
It's because Haskell is more functional than Lisp. (Can't speak to OCaml). Lisp doesn't do automatic currying; Haskell does. When you finally grok the implications of partial evaluation and laziness everywhere then you begin to understand that descriptions of the inputs and outputs of functions, while remaining ordered in time, become fully associative: You can group them however you like.
In Prolog there is another kind of revelation about inputs and outputs: There's no distinction between inputs and outputs and they aren't even necessarily ordered in time any more.
Firstly, I suspect you might mean partial appplication; many functional languages in that family support implicit partial application, so that if f is a three argument function, f a b c is be regarded as the partial applications ((f a) b) c).
Currying is a mechanism of representing all functions with two or more arguments using functions of only one argument; with currying we can "bootstrap" functions of higher arities in a substrate like a lambda calculus that has only one argument functions.
This arrangement of implicit partial application is a syntactic sugar.
Syntactic sugar for partial application is not partial application itself. Manual partial application is just as "functional". Functions are being applied, and passed around as values.
Implicit partial application can be obtained with Lisp macros, but that can never be fully general for at least two reasons.
One is that Lisps support something very useful, namely variadic functions, and functions with optional arguments. Variadic functions mean that you don't need ugly shims like "zipwith3" in a Lisp.
However, implicit partial application also requires static typing. In order to know that f is a three argument function being called with two arguments, and therefore reduced to a partially applied one-argument function, our syntactic sugar processor needs complete arity information about f.
In a Lisp, f can be redefined at run-time from having three arguments to having four.
In principle, in spite of that, all function calls could be treated as partial applications in a very generic way, but it would be horribly, horribly inefficient --- and the diagnostics when things go wrong would be pretty terrible.
Agree with all your points, and I did mean partial application, not partial evaluation.
And yes currying is not the same thing but it's common in informal settings to say "Haskell has automatic currying" and everybody knows you're talking about automatic partial application.
Lisp can of course do partial application and currying but not automatically; as you say you'd have to write special macros and sacrifice variadic functions to make it work (and I have done so). And it's really not that necessary in Lisp because we have parentheses; Haskell is the only example I've yet found of a Lisp-like language that has successfully removed most of the parentheses, and it succeeded because of its implicit partial application. But it had to sacrifice variadic functions.
When I first started using Haskell I lamented not having macros, and then I realized that many of my use cases for macros in Common Lisp weren't necessary in Haskell because of its laziness.
CL is still my daily-use language. But Haskell expanded how I think about programming almost as much as Lisp did all those years ago; that happened because Haskell took the functional metaphor to an extreme. I now write better Lisp programs because of my exposure to Haskell.
Read $ as <| and . as an empty space and it parses fine as F#. This article relies more on the underlying algebraic set theory than anything in particular about Haskell (sans the conclusion, which is an implementation detail - stick to your commutative monoids in f#'s PSeq.reduce please!).
The takeaway for me, which agrees with my experience, is that QuickCheck is a great way to start testing. It's pretty amazing what you can find just by checking a few properties or invariants with a hundred random inputs each. It's kind of the seven-minute-a-day workout of testing.
Nah, that's just author over complicating simple thing (quite common among Haskell programmers). If he thought for a moment before starting Haskell, he would find out that associativity is enough for map reduce operation.
Different people learn differently. Something that is obvious to you might not be obvious to someone else. The author learnt in that way and shared that, which is a good thing.
Sometimes, Haskell seems to be more mathematics than programming.
However some map-reduce implementations implicitly expect reducers to be commutative, which the author became appropriately suspicious of because of the "typical examples" of map-reduce.
While I do agree with you about Haskell's close association with maths (and an assumption about the users), in this case the author is pursuing a mathematical proof (or rather, a counterexample to a mathematical hypothesis). The use of Haskell here is just as a tool to that end. It is therefore reasonable to expect a greater than normal amount of mathematical notation.
I'd recommend it if you don't understand much of the article.