Archive:
In this section: Subtopics:
Comments disabled |
Mon, 31 Oct 2022 Content warning: something here to offend almost everyone A while back I complained that there were no emoji portraits of U.S. presidents. Not that there a Chester A. Arthur portrait would see a lot of use. But some of the others might come in handy. I couldn't figure them all out. I have no idea what a Chester Arthur emoji would look like. And I assigned 🧔🏻 to all three of Garfield, Harrison, and Hayes, which I guess is ambiguous but do you really need to be able to tell the difference between Garfield, Harrison, and Hayes? I don't think you do. But I'm pretty happy with most of the rest.
Honorable mention: Benjamin Franklin 🪁 Dishonorable mention: J. Edgar Hoover 👚 If anyone has better suggestions I'm glad to hear them. Note that I considered, and rejected 🎩 for Lincoln because it doesn't look like his actual hat. And I thought maybe McKinley should be 🏔️ but since they changed the name of the mountain back I decided to save it in case we ever elect a President Denali. (Thanks to Liam Damewood for suggesting Harding, and to Colton Jang for Clinton's saxophone.) [ Addendum 20221106: Twitter user Simon suggests emoji for UK prime ministers. ] [ Addendum 20221108: Rasmus Villemoes makes a good suggestion of 😼 for Garfield. I had considered this angle, but abandoned it because there was no way to be sure that the cat would be orange, overweight, or grouchy. Also the 🧔🏻 thing is funnier the more it is used. But I had been unaware that there is CAT FACE WITH WRY SMILE until M. Villemoes brought it to my attention, so maybe. (Had there been an emoji resembling a lasagna I would have chosen it instantly.) ] [ Addendum 20221108: January First-of-May has suggested 🌷 for Maarten van Buren, a Dutch-American whose first language was not English but Dutch. Let it be so! ] [ Addendum 20221218: Lorrie Kim reminded me that an old friend of ours, a former inhabitant of New Orleans, used to pass through Jackson Square, see the big statue of Andrew Jackson, and reflect gleefully on how he was covered in pigeon droppings. Lorrie suggested that I add a pigeon to the list above. However, while there is a generic "bird" emoji, it is not specifically a pigeon. There are also three kinds of baby chicks; chickens both male and female; doves, ducks, eagles, flamingos, owls, parrots, peacocks, penguins, swans and turkeys; also single eggs and nests with multiple eggs. But no pigeons. ] [Other articles in category /history] permanent link Sun, 30 Oct 2022A while back, discussing Vladimir Putin (not putain) I said
Today I remembered Frances Trollope and her son Anthony Trollope. Where does the name come from? Surely it's not occupational? Happily no, just another coincidence. According to Wikipedia it is a toponym, referring to a place called Troughburn in Northumberland, which was originally known as Trolhop, “troll valley”. Sir Andrew Trollope is known to have had the name as long ago as 1461. According to the Times of London, Joanna Trollope, a 6th-generation descendant of Frances, once recalled
I guess the common name "Hooker" is occupational, perhaps originally referring to a fisherman. [ Frances Trollope previously on this blog: [1] [2] ] [ Addendum: (Wiktionary says that Hooker is occupational, a person who makes hooks. I find it surprising that this would be a separate occupattion. And what kind of hooks? I will try to look into this later. ] [Other articles in category /lang] permanent link Sun, 23 Oct 2022
This search algorithm is usually called "group testing"
Yesterday I described an algorithm that locates the ‘bad’ items among a set of items, and asked:
The answer is: this is group testing, or, more exactly, the “binary splitting” version of adaptive group testing, in which we are allowed to adjust the testing strategy as we go along. There is also non-adaptive group testing in which we come up with a plan ahead of time for which tests we will perform. I felt kinda dumb when this was pointed out, because:
Oh well. Thanks to everyone who wrote in to help me! Let's see, that's Drew Samnick, Shreevatsa R., Matt Post, Matt Heilige, Eric Harley, Renan Gross, and David Eppstein. (Apologies if I left out your name, it was entirely unintentional.) I also asked:
Wikipedia is quite confident about this:
Eric Harley said:
Yeah, now I wonder too. Surely there must be some coin-weighing puzzles in Sam Loyd or H.E. Dudeney that predate Dorfman? Dorfman's original algorithm is not the one I described. He divides the items into fixed-size groups of n each, and if a group of n contains a bad item, he tests the n items individually. My proposal was to always split the group in half. Dorfman's two-pass approach is much more practical than mine for disease testing, where the test material is a body fluid sample that may involve a blood draw or sticking a swab in someone's nose, where the amount of material may be limited, and where each test offers a chance to contaminate the sample. Wikipedia has an article about a more sophisticated of the binary-splitting algorithm I described. The theory is really interesting, and there are many ingenious methods. Thanks to everyone who wrote in. Also to everyone who did not. You're all winners. [ Addendum 20221108: January First-of-May has brought to my attention section 5c of David Singmaster's Sources in Recreational Mathematics, which has notes on the known history of coin-weighing puzzles. To my surprise, there is nothing there from Dudeney or Loyd; the earliest references are from the American Mathematical Monthly in 1945. I am sure that many people would be interested in further news about this. ] [Other articles in category /prog] permanent link Fri, 21 Oct 2022
More notes on deriving Applicative from Monad
A year or two ago I wrote about what you do if you already have a Monad and you need to define an Applicative instance for it. This comes up in converting old code that predates the incorporation of Applicative into the language: it has these monad instance declarations, and newer compilers will refuse to compile them because you are no longer allowed to define a Monad instance for something that is not an Applicative. I complained that the compiler should be able to infer this automatically, but it does not. My current job involves Haskell programming and I ran into this issue again in August, because I understood monads but at that point I was still shaky about applicatives. This is a rough edit of the notes I made at the time about how to define the Applicative instance if you already understand the Monad instance.
Now suppose we
have
or equivalently:
And in fact there is at least one other way to define it is just as good:
( I had run into this previously
and written a blog post about it.
At that time I had wanted the second The issue came up again in August because, as an exercise, I was trying to
implement the I had written this weird piece of code: instance Applicative f => Applicative (StateT s f) where pure a = StateT $ \s -> pure (s, a) stf <*> stv = StateT $ \s -> let apf = run stf s apv = run stv s in liftA2 comb apf apv where comb = \(s1, f) (s2, v) -> (s1, f v) -- s1? s2? It may not be obvious why this is weird. Normally the definition of
This runs Or one could just as well run the two state-changing computations in the opposite order:
which lets I had been unsure of whether I wanted to run stf <*> stv = StateT $ \s0 -> let (sf, f) = run stf s0 let (sv, v) = run stv s0 in (sf, f v) Trying to sneak around the problem, I was caught immediately, like a
small child hoping to exit a room unseen but only getting to the
doorway. I could run the computations ⸢simultaneously⸣ but on the
very next line I still had to say what the final state was in the end:
the one resulting from computation My co-worker Brandon Chinn
opined that this must
violate one of the
applicative functor laws.
I wasn't sure, but he was correct.
This implementation of
Suppose My proposed implementation of (Of course we can't rescue this by yielding Stack Overflow discussionI worked for a while to compose a question about this for Stack Overflow, but it has been discussed there at length, so I didn't need to post anything:
That first thread contains this enlightening comment:
That middle dictum provides another way to understand why my idea of running the effects ⸢simultaneously⸣ was doomed: one of the loops has to be innermost. The second thread above (“How arbitrary is the Another answer there sketches a proof that if the applicative
”interchange” law holds for some applicative functor [Other articles in category /prog/haskell] permanent link Thu, 20 Oct 2022Last week I was in the kitchen and Katara tried to tell Toph a secret she didn't want me to hear. I said this was bad opsec, told them that if they wanted to exchange secrets they should do it away from me, and without premeditating it, I uttered the following:
I suppose this is tautological. But it's not any sillier than Tarski's observation that "snow is white" is true exactly if snow is white, and Tarski is famous. I've been trying to think of more examples that really work. The best I've been able to come up with is:
I'm trying to decide if the nesting can be repeated. Is this grammatical?
I think it isn't. But if it is, what does it mean? [ Previously, sort of. ] [Other articles in category /lang] permanent link Wed, 19 Oct 2022
What's this search algorithm usually called?
Consider this problem: Input: A set !!S!! of items, of which an unknown subset, !!S_{\text{bad}}!!, are ‘bad’, and a function, !!\mathcal B!!, which takes a subset !!S'!! of the items and returns true if !!S'!! contains at least one bad item: $$ \mathcal B(S') = \begin{cases} \mathbf{false}, & \text{if $S'\cap S_{\text{bad}} = \emptyset$} \\ \mathbf{true}, & \text{otherwise} \\ \end{cases} $$ Output: The set !!S_{\text{bad}}!! of all the bad items. Think of a boxful of electronic components, some of which are defective. You can test any subset of components simultaneously, and if the test succeeds you know that each of those components is good. But if the test fails all you know is that at least one of the components was bad, not how many or which ones. The obvious method is simply to test the components one at a time: $$ S_{\text{bad}} = \{ x\in S \mid \mathcal B(\{x\}) \} $$ This requires exactly !!|S|!! calls to !!\mathcal B!!. But if we expect there to be relatively few bad items, we may be able to do better:
In the worst case this takes (nearly) twice as many calls as just calling !!\mathcal B!! on the singletons. But if !!k!! items are bad it requires only !!O(k\log |S|)!! calls to !!\mathcal B!!, a big win if !!k!! is small compared with !!|S|!!. My question is: does this technique have a name? If I wanted to tell someone to use it, what would I say? It's tempting to say "binary search" but it's not very much like binary search. Binary search finds a target value in a sorted array. If !!S!! were an array sorted by badness we could use something like binary search to locate the first bad item, which would solve this problem. But !!S!! is not a sorted array, and we are not really looking for a target value. Is the history of this algorithm lost in time, or do we know who first invented it, or at least wrote it down? I think it sometimes pops up in connection with coin-weighing puzzles. [ Addendum 20221023: this is the pure binary-splitting variation of adaptive group testing. I wrote a followup. ] [Other articles in category /prog] permanent link Tue, 18 Oct 2022In Perl I would often write a generic tree search function:
For example, see Higher-Order Perl, section 5.3. To use this, we provide two callback functions.
Many variations of this are possible. For example, replacing I wanted to do this in Haskell, and my first try didn’t work at all:
There are two problems with this. First, the But the larger problem is that in most cases this function will compute
forever without producing any output at all, because the call to Here’s the palindrome example in Haskell:
This yields a big fat !!\huge \bot!!: it does nothing, until memory is exhausted, and then it crashes. My next attempt looked something like this: search2 :: (n -> Bool) -> (n -> [n]) -> n -> [n] search2 isGood childrenOf root = filter isGood $ s [root] where s nodes = do n <- nodes n : (s $ childrenOf n) The The
It’s doing a depth-first search, charging down the leftmost branch to
infinity. That’s because the list returned from I needed to convert the search to breadth-first, which is memory-expensive but at least visits all the nodes, even when the tree is infinite: search3 :: (n -> Bool) -> (n -> [n]) -> n -> [n]
search3 isGood childrenOf root = filter isGood $ s [root]
where
s nodes = nodes ++ (s $ concat (map childrenOf nodes))
This worked. I got a little lucky here, in that I had already had the
idea to make
While I was writing this version I vaguely wondered if there was something that combines search3' :: (n -> Bool) -> (n -> [n]) -> n -> [n]
search3' isGood childrenOf root = filter isGood $ s [root]
where
s nodes = nodes ++ (s $ concatMap childrenOf nodes)
So this worked, and I was going to move on. But then a brainwave hit me: Haskell is a lazy language. I don’t have to generate and filter the tree at the same time. I can generate the entire (infinite) tree and filter it later:
This is much better because it breaks the generation and filtering into independent components, and also makes clear that searching is nothing more than filtering the list of nodes. The interesting part of this program is the breadth-first tree traversal, and the tree traversal part now has only two arguments instead of three; the filter operation afterwards is trivial. Tree search in Haskell is mostly tree, and hardly any search! With this refactoring we might well decide to get rid of
And then I remembered something I hadn’t thought about in a long, long time:
That's exactly what I was doing and what I should have been doing all along. And it ends:
(”Why Functional Programming Matters”, John Hughes, 1990.) I felt a little bit silly, because I wrote a book about lazy functional programming and yet somehow, it’s not the glue I reach for first when I need glue. [ Addendum 20221023: somewhere along the way I dropped the idea of
using the list monad for the list construction, instead using explicit
I don't think this is an improvement on just using [Other articles in category /prog/haskell] permanent link Thu, 13 Oct 2022Today I realized I'm annoyed by the word "stethoscope". "Scope" is Greek for "look at". The telescope is for looking at far things (τῆλε). The microscope is for looking at small things (μικρός). The endoscope is for looking inside things (ἔνδον). The periscope is for looking around things (περί). The stethoscope is for looking at chests (στῆθος). Excuse me? The hell it is! Have you ever tried looking through a stethoscope? You can't see for shit. It should obviously have been called the stethophone. (It turns out that “stethophone” was adopted as the name for a later elaboration of the stethoscope, shown at right, that can listen to two parts of the chest at the same time, and deliver the sounds to different ears.) Stethophone illustration is in the public domain, via Wikipedia. [Other articles in category /lang/etym] permanent link |