tl;dr: It’s not possible without adjustments to the definition of PT. Here’s the core problem: you’ll be running your stateful computation in the context of some sort of storage medium, but said storage medium has to know how to store arbitrary types. This isn’t possible without packaging up some sort of evidence into the MkRef … Read more
luqui’s answer is excellent but I’m going to offer another explanation of forall b. (a -> b) -> b === a for a couple reasons: First, because I think the generalization to Codensity is a bit overenthusiastic. And second, because it’s an opportunity to tie a bunch of interesting things together. Onwards! z5h’s Magic Box … Read more
There are a number of Haskell heap implementations in an appendix to Okasaki’s Purely Functional Data Structures (pdf). (The source code can be downloaded at the link. The book itself is well worth reading.) None of them are binary heaps, per se, but the “leftist” heap is very similar. It has O(log n) insertion, removal, … Read more
To answer your first question, mathematical functions have often been described as “pure” in terms of some specified variables. e.g.: the first term is a pure function of x and the second term is a pure function of y Because of this, I don’t think you’ll find a true “first” occurrence. For programming languages, a … Read more
Because throwing an exception inside a function doesn’t make that function’s result dependent on anything but the argument values and the definition of the function; the function remains pure. OTOH catching an exception inside a function does (or at least can) make that function no longer a pure function. I’m going to look at two … Read more
Speaking as someone who came from Java, and for whom Scala was a gateway drug to Haskell, I happen to think this is a great idea (learn Haskell first)! Haskell is conceptually a much simpler language than Scala, and if your goal is to learn how to program functionally, you can’t help but do so … Read more
Relative to other managed languages like Java and C#, purely functional languages allocate like crazy. They also allocate objects of different sizes. The fastest known allocation strategy is to allocate from contiguous free space (sometimes called a “nursery”) and to reserve a hardware register to point to the next available free space. Allocation from the … Read more
Purely functional (aka persistent or immutable) data structures give you several advantages: you never have to lock them, which extremely improves concurrency. they can share structure, which reduces memory usage. For example, consider list [1, 2, 3, 4] in Haskell and some imperative language like Java. To produce new list in Haskell you only have … Read more
If I gather in one place any three theorists of my acquaintance, at least two of them disagree on the meaning of the term “referential transparency.” And when I was a young student, a mentor of mine gave me a paper explaining that even if you consider only the professional literature, the phrase “referentially transparent” … Read more