Fuzz me wrong – How QuickCheck destroyed my favourite theory

https://thma.github.io/posts/2021-01-30-How-QuickCheck-destroyed-my-favourite-theory.html

by lrngjcb • 5 years ago

126 57 5 years ago

thma.github.io

tonetheman• 5 years ago

Another article that I am too stupid to understand... how do you get anything done in Haskell...

Hitton• 5 years ago

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.

smlckz• 5 years ago

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.

mopierotti• 5 years ago

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.

I found this interesting paper on the subject of non-commutative reducers: "Nondeterminism in MapReduce Considered Harmful?" https://www.microsoft.com/en-us/research/wp-content/uploads/...

an_ko• 5 years ago

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.

k__• 5 years ago

Why is Haskell like this?

I don't have that feeling when using other FP languages like Lisp or OCaml.

SloopJon• 5 years ago

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.

rowanG077• 5 years ago

This comment makes me really sad. It's not that you are stupid. It's just that this article is littered with terminology unfamiliair to you(I assume).

the_af7• 5 years ago

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.

ljm• 5 years ago

Worth noting that some articles may also feel inaccessible because so many examples are written in terms of formulae.

There's plenty of Haskell out there that is easier to pick up on without looking at what seems to be a jumble of letters that imparts deep meaning.

    frobnicateM :: M a b => b -> a -> f (b a) a

You might get to that stage at some point but books like writing a scheme in 48 hours will show you a much more accessible and elegant side.

andrepd• 5 years ago

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?

the_af7• 5 years ago

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).

jcelerier• 5 years ago

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

mjaniczek• 5 years ago

You don't need to use the advanced features of Haskell to be productive with Haskell.

On my latest project I'm writing Haskell in a largely Elm style, and it's glorious.

rkangel• 5 years ago

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.

dan-robertson3• 5 years ago

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.

jgilias• 5 years ago

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.

dan-robertson3• 5 years ago

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.

maweki• 5 years ago

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.

dan-robertson3• 5 years ago

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.

lupire• 5 years ago

3. A day of implementation can save 20minutes of design .

gampleman• 5 years ago

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.

yakubin• 5 years ago

I think if one thinks of mapreduce as an operation on sets not lists, it should be obvious that the monoid must be commutative.

If anything, you could think of it as an operation on multisets, but not sets. Sets don't have repeated elements.

leblancfg• 5 years ago

That’s a great article! I have no background in either Haskell or CS but was captivated to read until the end. Great job!

Nit: I think this would read better if the author replaced “personal theory” with “hypothesis”.

PartiallyTyped• 5 years ago

'Conjecture' could also work.

dreamcompiler4• 5 years ago

To me this says the parallel library the author described isn't as efficient as it could be because it's enforcing an unexpected ordering constraint.

jerf• 5 years ago

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.)

Aissen• 5 years ago

There was a great introduction to QuickCheck and many other interesting concepts at 36c3: https://www.youtube.com/watch?v=_2tK9G7rKQQ

I'd recommend it if you don't understand much of the article.

millstone• 5 years ago

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.

massysett• 5 years ago

That’s a semigroup.

dwenzek• 5 years ago

Indeed, the identity is only required to deal with an empty input.

rmorey• 5 years ago

oh, so not the convenience store...

Fuzz me wrong – How QuickCheck destroyed my favourite theory

Related Stories