17 ms·
Fuzz me wrong – How QuickCheck destroyed my favourite theory
- deleted 6y ago[deleted]
- tonetheman 6y agoAnother article that I am too stupid to understand... how do you get anything done in Haskell...
- the_af 6y agoHow 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 6y agoWorth 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.
- chowells 6y agoThat 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.
- andrepd 6y agoI 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_af 6y agoI 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).
- dreamcompiler 6y agoAnd Haskell syntax is much easier to learn than Japanese syntax. (And Japanese syntax is itself easier than you might think.)
- mumblemumble 6y agoI'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.
- FartyMcFarter 6y agoProlog can also be pretty mind-bending at first, for people used to imperative programming.
- Hitton 6y agoNah, 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 6y agoDifferent 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 6y agoHowever 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/2016/02/icsecomp14seip-seipid15-p.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- an_ko 6y agoDon'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__ 6y agoWhy is Haskell like this? I don't have that feeling when using other FP languages like Lisp or OCaml.
- josephg 6y agoHaskell 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.
- MaxBarraclough 6y agoThe acolytes of laziness dug too eagerly and too deep.
- the_af 6y agoA lot of people complain about all the parens in Lisp. I don't agree with that complaint either. Different people find different things confusing.
- freeone3000 6y agoRead $ 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!).
- SloopJon 6y agoThe 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 6y agoThis 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).
- mjaniczek 6y agoYou 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 6y agoWhile 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-robertson 6y agoThere 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 6y agoBut 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-robertson 6y agoI 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 6y agoI 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.
- leblancfg 6y agoThat’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 6y ago'Conjecture' could also work.
- dreamcompiler 6y agoTo 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 6y agoUnfortunately, 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 6y agoThere was a great introduction to QuickCheck and many other interesting concepts at 36c3: https://www.youtube.com/watch?v=_2tK9G7rKQQ https://www.youtube.com/watch?v=_2tK9G7rKQQ I'd recommend it if you don't understand much of the article.
- millstone 6y agoIt 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.
- rmorey 6y agooh, so not the convenience store...