Readit News logoReadit News
housecarpenter commented on Unification (2018)   eli.thegreenplace.net/201... · Posted by u/asplake
cubefox · 7 days ago
Where do you need full type unification rather only type pattern matching?
housecarpenter · 7 days ago
Consider the identity function f, which just takes an argument and returns it unchanged, and has the polymorphic type a -> a, where a is a type variable. What's the type of f(f)?

Obviously, since f(f) = f it should be a -> a as well. But to infer it without actually evaluating it, using the standard Hindley-Milner algorithm, we reason as follows: the two f's can have different specific types, so we introduce a new type variable b. The type of the first f will be a substitution instance of a -> a, the type of the second f will be a substitution instance of b -> b. We introduce a new type variable c for the return type, and solve the equation (a -> a) = ((b -> b) -> c), using unification. This gives us the substitution {a = (b -> b), c = (b -> b)}, and so we see that the return type c is b -> b.

But if we use pattern matching rather than unification, the variables in one of the two sides of the equation (a -> a) = ((b -> b) -> c) are effectively treated as constants referring to atomic types, not variables. Now if we treat the variables on the left side as constants, i.e. we treat a as a constant, we have to match b -> b to the constant a, which is impossible; the type a is atomic, the type b -> b isn't. If we treat the variables on the right side as constants, i.e. we treat b and c as constants, then we have to match a to both b -> b and c, and this means our substitution will have to make b -> b and c equal, which is impossible given that c is an atomic type and b -> b isn't.

housecarpenter commented on Why are there so many rationalist cults?   asteriskmag.com/issues/11... · Posted by u/glenstein
rpcope1 · 13 days ago
Even the real progenitors of a lot of this sort of thought, like E.T. Jaynes, expoused significantly more skepticism than I've ever seen a "rationalist" use. I would even imagine if you asked almost all rationalists who E.T. Jaynes was (if they weren't well versed in statistical mechanics) they'd have no idea who he was or why his work was important to applying "Bayesianism".
housecarpenter · 12 days ago
It would surprise me if most rationalists didn't know who Jaynes was. I first heard of him via rationalists. The Sequences talk about him in adulatory tones. I think Yudkowsky would acknowledge him as one of his greatest influences.
housecarpenter commented on Writing a good design document   grantslatton.com/how-to-d... · Posted by u/kiyanwang
chromatin · 21 days ago
The author makes the following assertion:

    Let me illustrate a common code organization issue some programmers run into on their first day. The novice writes

    terminal.print("Hello world")

    Then they decide they want to make the text red, so they edit their program to

    
    terminal.print("Hello world")

    terminal.setPrintColor("red")
        
    And then they're confused that it didn't come out red. They haven't internalized that the first line of code happens before the second. They just get a soup of code on the screen that kind of has the ingredients for a program, and expect the computer to do what they want.

I find this _extremely_ surprising???

housecarpenter · 20 days ago
What do you find surprising---the fact that it doesn't come out red, or the fact that people are confused by this behaviour?
housecarpenter commented on A list is a monad   alexyorke.github.io//2025... · Posted by u/polygot
4ad · 2 months ago
Learning category theory to the level of understanding monads should take half an hour at most, and would constitute real understanding of what a monad is, versus this C++ explanation which is handwavy even in terms of C++. C++ can't even encode monads accurately!

But one doesn't even need to learn category theory. I assume that everybody has learned abstract algebra in high school, monoid, rings, groups, vector spaces and all that. A monad is just another kind of a structure like that. If you have studied abstract algebra in school then it should take 5 seconds to read the definition of a monad, a minute to understand it, and perhaps 10 minutes to see how various things such as errors or lists form monads.

Learning category theory, or indeed any sort of math from Wikipedia is an absolute futile endeavour.

housecarpenter · 2 months ago
At least in my country (the UK), people generally do not learn abstract algebra in high school. That's a university-level topic.

I think there is a definite "step up" in complexity between the structures of abstract algebra such as monoids, rings, groups and vector spaces, and monads. All of those algebraic structures are basically just sets equipped with operations satisfying some equations. Monads are endofunctors equipped with natural transformations satisfying some equations. "Endofunctor" and "natural transformation" are considerably more advanced and abstract concepts than "set" and "operation", and they are concepts that belong to category theory (so I don't see how you can read and understand the definition of a monad without that basic level of category theory).

Your time estimates also seem wildly optimistic. A common rule of thumb is that reading a maths textbook at your level takes around an hour per page. I think the definition of a monad can be compared to one page of a textbook. So I'd say it'll take on the order of hours to read and understand the definition of a monad, and that's assuming you're already entirely comfortable with the pre-requisite concepts (natural transformations, etc.)

housecarpenter commented on A list is a monad   alexyorke.github.io//2025... · Posted by u/polygot
perlgeek · 2 months ago
I really like my lists to be deterministic.

Seriously, I've read things about lists and nondeterminism a few times in this thread, and I can't help but wonder if "you guys" (functional programming nerds, maybe?) use the word "nondeterministic" different than the rest of the world?

If not, I'd love a good explanation about what makes lists non-deterministic, and why we would want that, and why they seem to be perfectly deterministic in imperative programming languages.

housecarpenter · 2 months ago
It is a particular sense of "nondeterminism", but it's not specific to functional programming, I think it's the usual one theoretical CS as a whole. It's the same sense in which "nondeterminism" is used in P vs NP, for example.

Think of a computation as a process of changing state. At a given point in time, the computer is in a certain state, the current state. The computation can be described in terms of a function that acts on the current state.

In a deterministic computation, the function takes in the current state, and produces a single state as output which will be the state the computer enters on the next tick.

In a non-deterministic computation, the function takes in the current state and produces a set of states as output. These states are all the possible states the computer might enter on the next tick. We don't know (or just don't care) which one of these states it will enter.

You can model a non-deterministic computation as a deterministic one, by using a list `currentStates` to store the set of all possible current states of the computation. At each "tick", you do `currentStates = flatMap(nextStates, currentStates)` to "progress" the computation. In the end `currentStates` will be the set of all possible end states (and you could do some further processing to choose a specific end state, e.g. at random, if you wish, but you could also just work with the set of end states as a whole).

It's in this sense that "a list is a non-deterministic result", although this is really just one thing a list can represent; a list is a generic data structure which can represent all sorts of things, one of which is a non-deterministic result.

housecarpenter commented on First methane-powered sea spiders found crawling on the ocean floor   cnn.com/2025/06/17/scienc... · Posted by u/bookofjoe
schmidtleonard · 2 months ago
Most people can get on board with jumping spiders. Big eyes, recognizable behavior, fuzz like fur, aspect ratios that aren't foreign to mammals. But if they mean knobbly things that look like they came out off the sea floor / out of an alien film, yeah, I'll grant them that they have a special skill if they can find those cute.
housecarpenter · 2 months ago
As a non-arachnophobe, I don't find spiders of any kind to be cute. But I also don't find anything about their appearance or behaviour to be unpleasant or scary. They're just aesthetically unremarkable. Similar to, say, fish---I don't think most people will look at a fish and think either "ooh, so cute" or "weird alien thing, get it away from me", they just see a fish and don't really have any emotions about it.
housecarpenter commented on Interviewing a software engineer who prepared with AI   kapwing.com/blog/what-its... · Posted by u/justswim
ellen364 · 5 months ago
I'm curious about this. When I've hired, I've always wondered how I can actually tell (a) what soft skills are required for the role and (b) whether a candidate has them.

People sometimes think that's a silly thing to ponder: it's obviously obvious! But at most places I've worked, we spend lots of time defining the technical skills required for a job and handwave the rest.

I guess people assume "they'll know it when they see it". But there's a lot of ambiguity. Parent comment suggests that being comfortable sitting in a conference room for an hour is an important part of their job. In some workplaces that would be an odd requirement. I've worked at places where the important thing was being able to go away and make progress on something for a few weeks.

I suspect there are people with autism reading these threads and feeling disheartened. It would be easy to leave with the impression that neurotypical people expect you to make all the effort and they won't try to meet you half way. Some workplaces are like that. But in all the talk about neurotypical vs neurodivergent, it's easy to forget that neurotypical people are a varied lot, just like neurodivergent people. Workplaces are a varied lot too.

housecarpenter · 5 months ago
As somebody with autism, one thing I'd say from my experience (I don't know how many people will agree) is that interviewing has felt like a much more severe stress test of my soft skills than anything I've had to do while actually being employed. While employed, the vast majority of my social interactions are oriented around some technical task that I need to work on with other people, and conveying information effectively so as to bring about the completion of this task. This is precisely the kind of social interaction that I feel most competent in--I feel like I'm pretty good at it, actually! What I struggle with are social interactions that are more open-ended, that are more about emotional connections and getting people to like you, and I feel like interviewing is an interaction of the latter type.

In this respect interviewing is a bit like LeetCode. LeetCode problems and writing code to satisfy business requirements are both "coding" but they're quite different kinds of coding; someone being able to do the former is probably good evidence they can do the latter, but there are also plenty of people who can do the latter without being able to do the former. So it is, in my view, with interviewing vs. interacting with people on the job.

housecarpenter commented on Solving SICP   lockywolf.wordpress.com/2... · Posted by u/todsacerdoti
zeckalpha · 6 months ago
There's probably more nuance with 2.29 than is led onto here. The problem appears straightforward and there seems to be simpler solutions out there than the one described in the article.

Did the author overthink it or are the simple solutions not correct?

housecarpenter · 6 months ago
I think the author made a typo, and they actually meant to refer to 2.92, not 2.29. The table preceding the part mentioning 2.29 only includes 2.92. And 2.29 doesn't include the text "This is not easy!”, whereas 2.92 does.
housecarpenter commented on The number line freaks me out (2016)   mathwithbaddrawings.com/2... · Posted by u/mananaysiempre
dr_dshiv · 6 months ago
You can represent pi on a number line but it is absolutely completely impossible to randomly put a dot down on a number line and have it be pi. You can achieve endless measurable precision with decimal rational numbers. So randomly placing a dot on a line will always be a rational number.

Right???

housecarpenter · 6 months ago
> it is absolutely completely impossible to randomly put a dot down on a number line and have it be pi

It's not impossible, it just has zero probability of occurring.

housecarpenter commented on The number line freaks me out (2016)   mathwithbaddrawings.com/2... · Posted by u/mananaysiempre
vishnugupta · 6 months ago
> Since the set of all English sentences is countable

Is it? Where can I read a proof? I have a feeling it’s uncountable set but would be happy to see a proof one way or another.

housecarpenter · 6 months ago
An spoken English sentence is a finite string of phonemes. The set of allowable phonemes is finite. Given a finite set X, the set of all finite strings of elements of X is countable.

(The latter statement holds because for any given n, the set X_n of all strings of length n is finite. So you can count the members of X_0, then count the members of X_1, and so on, and by continuing on in that way you'll eventually count out all members of X. You never run out of numbers to assign to the next set because at each point the set of numbers you've already assigned is finite (it's smaller in size than X_0, ..., X_n combined, for some n).

In fact, even if you allow countably infinitely many phonemes to be used, the X_n sets will still be countable, if not finite, and in that case their union is still countable: to see that, you can take enumerations of each set put them together as columns an a matrix. Even though the matrix is infinite in both dimensions, it has finite diagonals, so you can enumerate its cells by going a diagonal at a time, like this (the numbers reflect the cells' order in the numeration):

    1  3  6  10 15
    2  5  9  14
    4  8  13
    7  12
    11
However if you allow sentences to be countably infinitely long, then even when you only have finitely many phonemes, the set of all sentences will be uncountable, because in that case each countably infinitely long sentence can be mapped to a real number represented as an expansion in some base, and you can apply Cantor's diagonal argument. The "just count out each X_n separately" argument doesn't work in this case because it only applies to the sentences of finite length.)

u/housecarpenter

KarmaCake day170May 15, 2019
About
meet.hn/city/gb-Liverpool

Socials:

- github.com/Andrew-Foote

Interests:

Art, Books, Gaming, Music, Programming, Remote Work, Science, Web Development, Writing

---

View Original