zodiac

That's a good point.

I wonder if the problem is that efficient persistent arrays aren't in racket's standard library (there are some third-party libraries implementing them though). Since racket isn't a "pure FP" language, they include cons-arrays and mutable vectors, and I imagine they felt that there wasn't a need to include efficient persistent arrays in addition to those.

Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se).

Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manipulate that state"). Then, if you translated that Haskell directly into Racket (something like: use the exact same functions, just delete the type annotations), what would be the run-time of the solution?

(Not a trick question, I really don't know the answers. I've "understood" how the State, Reader, Writer work in the sense of reading the code, checking the types, and confirming that they do what they claim, but didn't think about how a compiler would compile them before)

Using the interpreter example in the article, would it be accurate to say that the author's inefficient "each instruc­tion copies the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would even­tu­ally be garbage-collected)" is "manipulating the state directly"?

I think the author somewhat explained why FP "suggests" that. In his explanation, it's because when you read tutorials that operate on "numbers and strings and simple lists" (as the author puts it), you do create and destroy those structures willy-nilly.

So when you operate on a large array (as in his example), a natural approach is to also create and destroy it.

Of course after you gain experience you learn not to do that, and techniques that let you not do that, but I don't think he is missing the point.

I love the Purely Functional Data Structures book (so many cool data structures and ideas!) but does really "solve" it? For e.g. I double checked and the PFDS for an array (the author's example) would be a skew-binary random access list with O(log N) cost for random access, whereas an "imperative random access array" is O(1). Of course, the skew-binary random access list has persistence (you get to keep references to old versions of the data if you wish), while the "imperative random access array" does not, but the author's use-case sounds like he doesn't need persistence. So there is still some gap between this particular approach and the "non-functional" one.

I don't think it's possible to divorce "proof" and "application" as cleanly as you'd like.

For instance, let's take a very common "application" of statistic: given a test that has false positive probability p, you can apply the test n times, and the false positive rate of the composite test is p^n. (For e.g. this is used to analyze bloom filters, or the Miller–Rabin primality test, or hash tables). However this is only true if the tests are independent. If you have to apply this result to analyzing (for e.g.) some new data structure you wrote, you'd first have to prove that the tests are independent. And maybe it's just me, but I find that if I use heuristics to check if some events are independent, I really often get it wrong.

Another example: the uniform limit theorem (https://en.wikipedia.org/wiki/Uniform_limit_theorem) is quite useful, but to properly apply it, you have to understand the difference between uniform convergence and pointwise convergence, and maybe it's just me, but I found the difference very unintuitive when I first encountered them (in a standard proofs-based analysis class). Even now, if you gave me some random series of functions, I can't really imagine using heuristics to check it uniformly converges to its pointwise limit, I'd want to try to write down a proof to be sure. So this useful tool is gated behind understanding some (to me) subtle proofs.

From reading the proof, I think he meant “n composite => 2^n - 1 composite” and it’s just a typo

I found this article with some breakdowns of the CBR assets in a few ways (e.g. by country, by denominating currency, by asset type) (some of it based on old data): https://www.ft.com/content/526ea75b-5b45-48d8-936d-dcc3cec10...

> Because every single transaction in USD must result in a credit and debit to an account at the US Federal Reserve

If I understand it correctly, in this case, isn't the thing prohibiting that transaction the US sanctions (i.e. https://home.treasury.gov/news/press-releases/jy0612), rather than exclusion from SWIFT?

But "completeness" already has a (different) definition, like when we say the reals are complete but the rationals are not

edit: to match with existing terminology you might call the reals the "completes" and the complex numbers the "algebraically-closeds" but... meh.

But all algorithms that deterministically play a finite combinatorial game can be represented as a decision tree. (there may be other, far more succinct representations)

I think people are downvoting you because you seem like you're attacking a strawman. We all agree that 1) it's an interesting math problem 2) for real-life instances, the FP64 solution is good enough.

For e.g. when you say "anything beyond that is likely unnecessary gold plating", I know you mean "exact algorithms (like the PSPACE algorithm) are unnecessary for solving real-life instances", but without context it sounds like you're saying "there is no conceivable reason people should care about the exact algorithms"

But the article presents it as an interesting pure math problem, and doesn't claim that the FP64 solution isn't good enough.

I should add that the people who write state of the art "practical" TSP solvers spend a lot of time thinking about the "theoretical" complexity of it too. Turns out it's a good way to engineer those "good enough" algorithms, provide bounds etc

You can still do IOI style contests very regularly as an adult, check out AtCoder or codeforces. Actually the US national olympiad (USACO) is open for everyone too :)

https://codeforces.com/blog/entry/20548 is old but pretty good. for e.g. #2 is specific cases: "you get a problem for a tree. Consider its variant where the tree degenerates into a path".

I am well aware of the "disadvantages" (to put it mildly) of hypothetical neutrino-based communications and I never suggested that they could viably replace EM-based communication

> If there were a way to reliably detect neutrinos in sufficient quantities they'd be ideal since you could send messages through the earth and at near light speed, I suppose.

> As opposed to how we communicate now globally?

From this interaction I thought you'd missed the point that "send messages through the earth" is something we're currently not doing. Of course you're right that the "if there were a way to reliably detect neutrinos" is doing a lot of work.

Let the radius of the earth be R. Say you want to send a message from the north pole to the south pole.

If you use radio waves that travel around the earth, the shortest distance they can travel is πR ≈ 20,000km.

If you use neutrinos that travel through the earth, the shortest distance is 2R ≈ 12,700km.

So the advantage is about 7,300km (or in time units, 25ms ≈ 7,300km / (the speed of light))

Communication via EM waves travel around the earth, not through it. (eg radio waves, fibre optic cables, satellite...)

Or you're a pro athlete

IC = individual contributor (as opposed to manager, etc)

Haha, I kind of had the opposite history (played Go first, got more into chess later and found it more interesting)

Still love the community and experience of both games though

I think the "answer to q2" here (https://mathoverflow.net/questions/199097/which-unfoldings-o...) is what you want!

Speaking only for myself, off the top of my head, I use it to look up stuff for work (software engineering), for several of my hobbies, and to learn more about local news / events, and I feel like it works equally well or better than a few years ago

I think the Chandy-Lamport snapshot algorithm tries to do something like this for all distributed systems (in their model, and it tries to get any consistent snapshot, not allowing you to specify the "time"); not sure if it's actually useful IRL though

You can modify the question to be well-defined and not suffer those measurement problems, eg "the total number of videos uploaded before midnight UTC on 2021-04-29"

Here's how I want encryption to work: it should be unbreakable when it's used to encrypt communication between journalists and their sources, but it should be breakable when used to encrypt communications between terrorists. I really "want [this thing] to be true". So why doesn't it work like this?

What if they disabled trading, the stock slowly lost value, and people who were long the stock couldn't exit their position?

Someone's gonna complain and ask "why didn't they just disallow buying but allow selling".

ios layout (autolayout) is like that. I generally prefer it to css, but it's not perfect either.

> in natural language, 'and' usually implies set union

well, sometimes it can be syntactically ambiguous too, right?

e.g. "I welcome big and small dogs" vs "I welcome well-behaved and properly groomed dogs"