## Functional Programming

Planet Haskell - Sun, 03/29/2015 - 06:00

Planet Haskell - Sun, 03/29/2015 - 06:00
Yesterday, which happened to be my 30th birthday, a small package got delivered to my office: The printed proceedings of last year's “Trends in Functional Programming” conference, where I published a paper on Call Arity (preprint). Although I doubt the usefulness of printed proceedings, it was a nicely timed birthday present. Looking at the rather short table of contents – only 8 papers, after 27 presented and 22 submitted – I thought that this might mean that, with some luck, I might have chances to get the “Best student paper award”, which I presumed to be announced at the next iteration of the conference. For no particular reason I was leisurely browsing through the book, and started to read the preface. And what do I read there? Among the papers selected for these proceedings, two papers stood out. The award for Best Student Paper went to Joachim Breitner for his paper entitled Call Arity, and the award for Best Paper Overall went to Edwin Brady for his paper entitled Resource-dependent Algebraic Effects. Congratulations! Now, that is a real nice birthday present! Not sure if I even would have found out about it, had I not have thrown a quick glance at page V... I hope that it is a good omen for my related ICFP'15 submission. 2015-03-28T13:13:15Z Joachim Breitner mail@joachim-breitner.de

### Algebraic side effects

Planet Haskell - Sun, 03/29/2015 - 06:00
Haskell differentiates itself from most other functional languages by letting you reason mathematically about programs with side effects. This post begins with a pure Haskell example that obeys algebraic equations and then generalizes the example to impure code that still obeys the same equations.AlgebraIn school, you probably learned algebraic rules like this one:f * (xs + ys) = (f * xs) + (f * ys)Now let's make the following substitutions:Replace the mathematical multiplication with Haskell's map functionReplace the mathematical addition with Haskell's ++operatorThese two substitutions produce the following Haskell equation:map f (xs ++ ys) = (map f xs) ++ (map f ys)In other words, if you concatenate the list xs with the list ys and then map a function named f over the combined list, the result is indistinguishable from mapping f over each list individually and then concatenating them.Let's test this equation out using the Haskell REPL:>>> map (+ 1) ([2, 3] ++ [4, 5])[3,4,5,6]>>> (map (+ 1) [2, 3]) ++ (map (+ 1) [4, 5])[3,4,5,6]Evaluation orderHowever, the above equation does not hold in most other languages. These other languages use function evaluation to trigger side effects, and therefore if you change the order of evaluation you change the order of side effects.Let's use Scala to illustrate this. Given the following definitions:>>> def xs() = { print("!"); Seq(1, 2) }>>> def ys() = { print("?"); Seq(3, 4) }>>> def f(x : Int) = { print("*"); x + 1 }.. the order of side effects differs depending on whether I concatenate or map first:>>> (xs() ++ ys()).map(f)!?****res0: Seq[Int] = List(2, 3, 4, 5)>>> (xs().map(f)) ++ (ys().map(f))!**?**res1: Seq[Int] = List(2, 3, 4, 5)One line #1, the two lists are evaluated first, printing "!" and "?", followed by evaluating the function f on all four elements, printing "*" four times. On line #2, we call f on each element of xs before beginning to evaluate ys. Since evaluation order matters in Scala we get two different programs which print the punctuation characters in different order.The solutionHaskell, on the other hand, strictly separates evaluation order from side effect order using a two-phase system. In the first phase you evaluate your program to build an abstract syntax tree of side effects. In the second phase the Haskell runtime executes the tree by interpreting it for its side effects. This phase distinction ensures that algebraic laws continue to behave even in the presence of side effects.To illustrate this, we'll generalize our original Haskell code to interleave side effects with list elements and show that it still obeys the same algebraic properties as before. The only difference from before is that we will:Generalize pure lists to their impure analog, ListTGeneralize functions to impure functions that wrap side effects with liftGeneralize (++) (list concatenation) to (<|>) (ListT concatenation)Generalize map to (=<<), which streams elements through an impure functionThis means that our new equation becomes:-- f * (xs + ys) = (f * xs) + (f * ys) f =<< (xs <|> ys) = (f =<< xs) <|> (f=<< ys)You can read this as saying: if we concatenate xs and ys and then stream their values through the impure function f, the behavior is indistinguishable from streaming each individual list through f first and then concatenating them.Let's test this equation out with some sample definitions for xs, ys, and f that mirror their Scala analogs:>>> import Control.Applicative>>> import Pipes>>> let xs = do { lift (putChar '!'); return 1<|> return 2 }>>> let ys = do { lift (putChar '?'); return 3<|> return 4 }>>> let f x = do { lift (putChar '*'); return (x + 1) }>>> runListT (f =<< (xs <|> ys)) -- Note:runListT discards the result!**?**>>> runListT ((f =<< xs) <|> (f =<< ys))!**?**>>>The resulting punctuation order is identical. Many people mistakenly believe that Haskell's mathematical elegance breaks down when confronted with side effects, but nothing could be further from the truth.ConclusionHaskell preserves algebraic equations even in the presence of side effects, which simplifies reasoning about impure code. Haskell separates evaluation order from side effect order so that you spend less time reasoning about evaluation order and more time reasoning about your program logic.

### The basics of coinduction

Planet Haskell - Sun, 03/29/2015 - 06:00
I don’t remember when I first heard the terms “coinduction” and “corecursion” but it must have been quite long ago. I had this impression that they are yet another of these difficult theoretical concepts and that I should learn about them one day. That “one day” happened recently while reading chapter 5 of “Certified Programming […]

### Qualified Goals in the Cabal Solver

Planet Haskell - Sun, 03/29/2015 - 06:00
When you ask cabal-install to install one or more packages, it needs to solve a constraint satisfaction problem: select a version for each of the packages you want to install, plus all their dependencies, such that all version constraints are satisfied. Those version constraints come both from the user [...]

### MinGHC for GHC 7.10

Planet Haskell - Sun, 03/29/2015 - 06:00

### Value vs Monomorphism Restriction

Planet Haskell - Sun, 03/29/2015 - 06:00

### Schrödinger’s Box

Planet Haskell - Sun, 03/29/2015 - 06:00
In Objective-C, NSValue provides a universal container that can hold scalars and value types in addition to references. Conversely, in Swift, we quickly learnt to appreciate Box as a wrapper to embed (cyclic) references in enums and structs (especially due to limitations in the initial versions of the Swift compiler): final public class Box { public let unbox: T public init(_ value: T) { self.unbox = value } } NSValue is also useful to wrap reference. For example, if we want to turn a strong reference into a weak reference (possibly to store it in a collection, such as NSArray), we can create an NSValue with +valueWithNonretainedObject. How do we achieve that in Swift without losing type information, as using NSValue would? We use Schrödinger’s Box: final public class WeakBox { private weak var box: T? public var unbox: T? { get { return box } } public init(_ value: T) { self.box = value } } You can put something into Schrödinger’s Box, which will or will not be gone by the time you try to retrieve it. It enables, for example, to build a typed collection of weakly referenced objects (to avoid retain cycles). NB: The definition of WeakBox is fine with the latest Swift 1.2 compiler. However, the Swift 1.1 compiler can only handle it with -Onone; otherwise, it crashes. 2015-03-26T23:43:21Z

### New website with new talks

Planet Haskell - Sun, 03/29/2015 - 06:00
My website is now located at ndmitchell.com and has a few new talks on it:Slides and Video from Gluing things together with Haskell given at Code Mesh 2014. I argue that shell script should die, and talk about how Shake, NSIS and Bake are helping that happen. Slides from Building stuff with Shake given at FP Days 2014 - an introduction to Shake through a series of examples.My old website at community.haskell.org is going to stop being updated, and I'll be putting in redirections shortly. That server is going to stop hosting websites, so I bought myself a domain name and setup a GitHub pages website. The repo is here, including all the data, metadata, templates and scripts. 2015-03-26T22:01:00Z Neil Mitchell noreply@blogger.com

### Our composable community infrastructure

Planet Haskell - Sun, 03/29/2015 - 06:00

### FP Complete's Hackage mirror

Planet Haskell - Sun, 03/29/2015 - 06:00
We have been running a mirror of Hackage package repository which we use internally for the FP Complete Haskell Centre's IDE, building Stackage, and other purposes. This has been an open secret, but now we're making it official.To use it, replace the remote-repo line in your ~/.cabal/config with the following:remote-repo: hackage.fpcomplete.com:http://hackage.fpcomplete.com/Then run cabal update, and you're all set.This mirror is updated every half-hour. It is statically hosted on Amazon S3 so downtime should be very rare (Amazon claims 99.99% availability).The mirror does not include the HTML documentation. However, Stackage hosts documentation for a large set of packages.We have also released our hackage-mirror tool. It takes care of efficiently updating a static mirror of Hackage on S3, should anyone wish to host their own. While the official hackage-server has its own support for mirroring, our tool differs in that it does not require running a hackage-server process to host the mirror.HTTPS for StackageOn a tangentially related note, we have enabled TLS for www.stackage.org. Since cabal-install does not support TLS at this time, we have not set up an automatic redirect from insecure connections to the https:// URL.

### Can you trust science?

Planet Haskell - Sun, 03/29/2015 - 06:00
Hardly a week goes by without newspaper writing about new and exciting results from science. Perhaps scientists have discovered a new wonderful drug for cancer treatment, or maybe they have found a physiological cause for CFS. Or perhaps this time they finally proved that homeopathy works? And in spite of these bold announcements, we still don't seem to have cured cancer. Science is supposed to be the method which enables us to answer questions about how the world works, but one could be forgiven for wondering whether it, in fact, works at all. As my latest contribution to my local journal club, I presented a paper by Ioannidis, titled Why most published research findings are false 1. This created something of a stir when it was published in 2005, because it points out some simple mathematical reasons why science isn't as accurate as we would like to believe. The ubiquitous p-value Science is about finding out what is true. For instance, is there a relationship between treatment with some drug and the progress of some disease - or is there not? There are several ways to go about finding out, but in essence, it boils down to making some measurements, and doing some statistical calculations. Usually, the result will be reported along with a p-value, which is a by-product of the statistical calculations saying something about how certain we are of the results. Specifically, if we claim there is a relationship, the associated p-value is the probability we would make such a claim even if there is no relationship in reality. We would like this probability to be low, of course, and since we usually are free to select the p-value threshold, it is usually chosen to be 0.05 (or 0.01), meaning that if the claim is false, we will only accept it 5% (or 1%) of the times. The positive predictive value Now, the p-value is often interpreted as the probability of our (positive) claim being wrong. This is incorrect! There is a subtle difference here, which it is important to be aware of. What you must realize, is that the probability α relies on the assumption that the hypothesis is wrong - which may or may not be true, we don't know (which is precisely why we want to find out). The probability of a claim being wrong after the fact is called the positive predictive value (PPV). In order to say something about this, we also need to take into account the probability of claiming there exists a relationship when the claim is true. Our methods aren't perfect, and even if a claim is true, we might not have sufficient evidence to say for sure. So, take one step back and looking at our options. Our hypothesis (e.g., drug X works against disease Y) can be true or false. In either case, our experiment and analysis can lead us to reject or accept it with some probability. This gives us the following 2-by-2 table: True False Accept 1-β α Reject β 1-α Here, α is the probability of accepting a false relationship by accident (i.e., the p-value), and β is the probability of missing a true relationship -- we reject a hypothesis, even when it is true. To see why β matters, consider a hypothetical really really poor method, which has no chance of identifying a true relationship, in other words, $\beta$=1. Then, every accepted hypothesis must come from the False column, as long as α is at all positive. Even if the p-value threshold only accepts 1 in 20 false relationships, that's all you will get, and as such, they constitute 100% of the accepted relationships. But looking at β is not sufficient either. Let's say a team of researchers test hundreds of hypotheses, which all happen to be false? Then again, some of them will get accepted anyway (sneaking in under the p-value threshold α), and since there are no hypotheses in the True column, again every positive claim is false. A β of 1 or a field of research with 100% false hypotheses are extreme cases2, and in reality, things are not quite so terrible. The Economist had a good article with a nice illustration showing how this might work in practice with more reasonable numbers. It should still be clear that the ratio of true to false hypotheses being tested, as well as the power of the analysis to identify true hypotheses are important factors. And if these numbers approach their limits, things can get quite bad enough. More elaborate models Other factors also influence the PPV. Try as we might to be objective, scientists often try hard to find a relationship -- that's what you can publish, after all3. Perhaps in combination with a less firm grasp of statistics than one could wish for (and scientists who think they know enough statistics are few and far between - I'm certainly no exception there), this introduces bias towards acceptance. Multiple teams pursuing the same challenges in a hot and rapidly developing field also decrease the chance of results being correct, and there's a whole cottage industry of scientist reporting spectacular and surprising results in high-ranking journals, followed by a trickle of failures to replicate. Solving this One option is to be stricter - this is the default when you do multiple hypothesis testing, you require a lower p-value threshold in order to reduce α. The problem with this is that if you are stricter with what you accept as true, you will also reject more actually true hypotheses. In other words, you can reduce α, but only at the cost of increasing β. On the other hand, you can reduce β by running a larger experiment. One obvious problem with this is cost, for many problems, a cohort of a hundred thousand or more is necessary, and not everybody can afford to run that kind of studies. Perhaps even worse, a large cohort means that almost any systematic difference will be found significant. Biases that normally are negligible will show up as glowing bonfires in your data. In practice? Modern biology has changed a lot in recent years, and today we are routinely using high-throughput methods to test the expression of tens of thousands of genes, or the value of hundreds of thousands of genetic markers. In other words, we simultaneously test an extreme number of hypotheses, where we expect a vast majority of them to be false, and in many cases, the effect size and the cohort are both small. It's often a new and exciting field, and we usually strive to use the latest version of the latest technology, always looking for new and improved analysis tools. To put it bluntly, it is extremely unlikely that any result from this kind of study will be correct. Some people will claim these methods are still good for "hypothesis generation", but Ioannidis shows a hypothetical example where a positive result increases the likelihood that a hypothesis is correct by 50%. This doesn't sound so bad, perhaps, but in reality, the likelihood is only improved from 1 in 10000 to 1 in 7000 or so. I guess three thousand fewer trials to run in the lab is something, but you're still going to spend the rest of your life running the remaining ones. You might expect scientists to be on guard for this kind of thing, and I think most scientists will claim they desire to publish correct results. But what counts for your career is publications and citations, and incorrect results are no less publishable than correct ones - and might even get cited more, as people fail to replicate them. And as you climb the academic ladder, publications in high-ranking journals is what counts, an for that you need spectacular results. And it is much easier to get spectacular incorrect results than spectacular correct ones. So the academic system rewards and encourages bad science. Consequences The bottom line is to be skeptical of any reported scientific results. The ability of the experiment and analysis to discover true relationships is critical, and one should always ask what the effect size is, and what the statistical power -- the probability of detecting a real effect -- is. In addition, the prior probability of the hypothesis being true is crucial. Apparently-solid, empirical evidence of people getting cancer from cell phone radiation, or working homeopathic treatment of disease can almost be dismissed out of hand - there simply is no probable explanation for how that would work. A third thing to look out for, is how well studied a problem is, and how the results add up. For health effects of GMO foods, there is a large body of scientific publications, and an overwhelming majority of them find no ill effects. If this was really dangerous, wouldn't some of these investigations show it conclusively? For other things, like the decline of honey bees, or the cause of CFS, there is a large body of contradictory material. Again - if there was a simple explanation, wouldn't we know it by now? And since you ask: No, the irony of substantiating this claim with a scientific paper is not lost on me.↩ Actually, I would suggest that research in paranormal phenomena is such a field. They still manage to publish rigorous scientific works, see this Less Wrong article for a really interesting take.↩ I think the problem is not so much that you can't publish a result claiming no effect, but that you can rarely claim it with any confidence. Most likely, you just didn't design your study well enough to tell.↩ 2015-03-25T20:00:00Z

### GHC Weekly News - 2015/03/24

Planet Haskell - Sun, 03/29/2015 - 06:00

### First impressions of Coq and “Certified Programming with Dependent Types”

Planet Haskell - Sun, 03/29/2015 - 06:00
A simplistic view of strongly typed functional programming ecosystem is that the two most influential languages are Haskell and ML. Haskell is my language of choice so when it came to learning dependently-typed programming I stayed on the Haskell side of the spectrum and went with Agda and Idris. I chose the two over the […]

### Infernu’s type system informal summary – first draft

Planet Haskell - Sun, 03/29/2015 - 06:00
I just finished a first draft describing Infernu’s type system. Target audience is potential users. Comments welcome!

### A Tiny Compiler For A Typed Higher Order Language

Planet Haskell - Sun, 03/29/2015 - 06:00

### Using Facebook's Flux architectural style for game development in Unity 3D

Planet Haskell - Sun, 03/29/2015 - 06:00