Krzysztof Gogolewski

if the algebra is free you're the product

@Jonathan_Blow @cmhrrs > are you really doing to do fewer than n evaluations in the probabilistic case Yes. The probabilistic algorithm in the book does 1 evaluation, and for every input it returns the correct answer >=99% chance. If you evaluate at 10 points, then the chance of an error is 1e-20.

Except no, because by the same probabilistic argument they make, your chances of testing all n evaluations is vanishingly small if the polynomials differ. If they are the same, yeah fine, but are you really doing to do fewer than n evaluations in the probabilistic case? Maybe only if n is real real real big, because you are trading certainty for probability. Which would be fine if they said all this.

@Jonathan_Blow @cmhrrs With deterministic algorithms, you cannot argue about "vanishingly small chance"; it has to be correct always, not merely on a huge portion of possible inputs. Either you evaluate on N inputs (and that's slow when the polynomials are equal) or less (and that gives wrong results).

@cmhrrs @Jonathan_Blow That's n evaluations, every one needing n multiplications, so O(n^2).

@monoidal_ @Jonathan_Blow Polynomials of degree n are uniquely determined by their values at any n+1 distinct inputs, so you can check values at 0, 1, ..., n (and even precompute powers of the test inputs as an optimization)

@Jonathan_Blow I don't see any trivial O(n) algorithm for the problem they describe. Can you elaborate? Expanding is to compare coeffs is O(n^2).

I’m just a few pages in but their opening gambit is to give an example of a randomized algorithm for verifying that two polynomials are equal. But it’s trivial to write a non-randomized version that is 100x faster than theirs, and they don’t seem to know this (they don’t mention it at all). I would get it if they said “Hey this is a toy problem for the purposes of introduction, you would never really do this,” but they do not say that, so this just seems like a case of programmers not knowing enough math to realize what they are doing is dumb (and dude if *I* know more math than a couple of CS professors, these are sad days indeed.)

Dr T is the man. He was my phd advisor at @tufts. I strongly recommend his other textbooks, i.e. Differential forms in Algebraic topology, Differential Geometry.

2-3% faster compilation speeds across the board with GHC. @lexi_lambda and @monoidal_ explain how they did it in this blog post: tweag.io/blog/2022-12-2….

Here's @monoidal_'s fun talk about quines from @MuniHac at the weekend! youtube.com/watch?v=Rnji4r…

@acid2 @aspiwack @googleson78 @sjoerd_visscher return and pure give the same effect.

@monoidal_ @aspiwack @googleson78 @sjoerd_visscher Does it work with return instead of pure?

Does this type exist anywhere? newtype OnlyApplicative f a = OnlyApplicative {out :: f a} deriving (Functor, Applicative) Basically, I want to forget about a Monad instance, so `do` notation is forced to be applicative do.

@aspiwack @googleson78 @sjoerd_visscher @acid2 I reported the bug: gitlab.haskell.org/ghc/ghc/-/issu…

@googleson78 @sjoerd_visscher @acid2 It shouldn't, though. I guess that it's not overly serious as you can use such erroring out definitions instead. But it ought to be considered a bug. Applicative do still has some rough edges, and maybe it looks at the `(>>=)` definition even if it doesn't need it.