February 2012 - Haskell-Cafe

Fundeps and overlapping instances
by Simon Peyton-Jones 09 Jun '12

09 Jun '12

Oleg points out, and Martin also mentions, that functional dependencies appear to interact OK with overlapping instances, but type families do not. I this impression is mistaken, and I'll try to explain why in this message, in the hope of exposing any flaws in my reasoning. We can't permit overlap for type families because it is unsound to do so (ie you can break "well typed programs don't go wrong"). But if it's unsound for type families, it would not be surprising if it was unsound for fundeps too. (I don't think anyone has done a soundness proof for fundeps + local constraints + overlapping instances, have they?) And indeed I think it is. So the short summary of this message is: if it works for fundeps it works for type families, and vice versa. (NB this equivalence is not true about GHC's current implementation, however. GHC doesn't support the combination of fundeps and local constraints at all.) Such an equivalence doesn't argue against fundeps; I'm only suggesting the that the two really are very closely equivalent. I much prefer type families from a programming-style point of view, but that's a subjective opinion. Simon Imagine a system "FDL" that has functional dependencies and local type constraints. The big deal about this is that you get to exploit type equalities in *given* constraints. Consider Oleg's example, cut down a bit: class C a b | a -> b instance C Int Bool newtype N2 a = N2 (forall b. C a b => b) t2 :: N2 Int t2 = N2 True We end up type-checking (True :: forall b. C Int b => b). From the functional dependency we know that (b~Bool), so the function should typecheck. GHC rejects this program; FDL would not. But making use of these extra equalities in "given" constraints is quite tricky. To see why look first at Example 1: module X where class C a b | a -> b data T a where MkT :: C a b => b -> T a module M1 where import X instance C Int Char where ... f :: Char -> T Int f c = MkT c module M2 where import X instance C Int Bool g :: T Int -> Bool g (MkT x) = x module Bad where import M1 import M2 bad :: Char -> Bool bad = g . f This program is unsound: it lets you cast an Int to a Bool; result is a seg-fault. You may say that the problem is the inconsistent functional dependencies in M1 and M2. But GHC won't spot that. For type families, to avoid this we "eagerly" check for conflicts in type-family instances. In this case the conflict would be reported when compiling module Bad, because that is the first time when both instances are visible together. So any FDL system should also make this eager check for conflicts. What about overlap? Here's Example 2: {-# LANGUAGE IncoherentInstances #-} module Bad where import X -- Overlapping instances instance C Int Bool -- Instance 1 instance C a [a] -- Instance 2 f :: Char -> T Int f c = MkT c -- Uses Instance 1 g :: T a -> a g (MkT x) = x -- Uses Instance 2 bad :: Char -> Int bad = g . f Again, a seg fault if it typechecks. But will it? When typechecking 'g', we get a constraint (C a ?), where 'a' is a skolem constant. Without IncoherentInstances GHC would reject the program on the grounds that it does not know what instance to choose. But *with* IncoherentInstances it would probably go through, which is unsound. So IncoherentInstances has moved from causing varying dynamic behaviour to causing seg faults. Very well, so FDL must get rid of IncoherentInstances altogether, at least for classes that have functional dependencies (or that have superclasses that do). But at the moment GHC makes an exception for *existentials*. Consider Example 3: class C a b | a -> b -- Overlapping instances instance C Int Bool -- Instance 1 instance C a [a] -- Instance 2 data T where MkT :: C a b => a -> b -> T f :: Bool -> T f x = MkT (3::Int) x -- Uses Instance 1 g :: T -> T g (MkT n x) = MkT n (reverse x) -- Uses Instance 2 bad :: Bool -> T bad = g . f In the pattern match for MkT in g we have the constraint (C a b), where 'a' is existentially bound. So under GHC's current rules it'll choose the (C a [a]) instance, and conclude that (b ~ [a]). So it's ok to reverse x. But it isn't; see function bad! So to avoid unsoundness we must not choose a particular instance from an overlapping set unless we know, absolutely positively, that the other cases cannot match. (GHC's exception for existentials was introduced in response to user demand. Usually, overlapping instances are somehow semantically coherent, and with an existential we are *never* going to learn more about the instantiating type, so choosing the best available seems like a good thing to do.) But even nuking IncoherentInstances altogether is not enough. Consider this variant of Example 3, call it Example 4: module M where class C a b | a -> b instance C a [a] -- Instance 2 data T where MkT :: C a b => a -> b -> T g :: T -> T g (MkT n x) = MkT n (reverse x) -- Uses Instance 2 module Bad where import M instance C Int Bool -- Instance 1 f :: Bool -> T f x = MkT (3::Int) x -- Uses Instance 1 bad :: Bool -> T bad = g . f This is nasty. In module M we have only one instance declaration for C, so there's no overlap, and function g typechecks fine. Now module Bad adds an overlapping instance declaration and 'f' uses it; moreover, it's clear that the new instance declaration is the right one to use. It's not clear how to fix this. The only way I can think of is to insist that all the instances appear in a single module, so that you cannot add more "later". But that loses part of the point of overlap in the first place, namely to provide a generic instance and then later override it. So FDL must * embody eager checking for inconsistent instances, across modules * never resolve overlap until only a unique instance can possibly match * put all overlapping instances in a single module Type families already implement the first of these. I believe that if we added the second and third, then overlap of type families would be fine. (I may live to eat my words here.) I'd be interested to know what Chameleon does on these examples.

6 18

Offer to mirror Hackage
by Dan Knapp 24 Apr '12

24 Apr '12

With Hackage down, now seemed like a good time to push this issue again. It's such an important site to us that it's really rather a shame there are no mirrors of it. I have a personal-and-business server in a data center in Newark, with a fair chunk of bandwidth, which I'd like to offer for a permanent mirror. Is there interest in this? Who do I need to talk to for it to happen? Strategy-wise, I think the best approach is round-robin DNS, since that's transparent to the end user - everything would still appear at the URL it's at now, but behind-the-scenes magic would let things keep working when one or the other site is down. I haven't personally set up such a system before but I'm willing to take on the burden of figuring it out. So I have a better idea of what I'm signing up for, can anyone tell me how much disk space and how much bandwidth per month Hackage uses? I have a fair chunk of both, as I say, but I'd like to know in advance to ensure that things go smoothly. As for what I'd want in return for this, really nothing. I wouldn't say no to an unobtrusive mention somewhere on the site, but I'd be happy just knowing I'd given something back to the Haskell community, which has given a lot to me. -- Dan Knapp "An infallible method of conciliating a tiger is to allow oneself to be devoured." (Konrad Adenauer)

21 53

Fwd: Now Accepting Applications for Mentoring Organizations for GSoC 2012
by Johan Tibell 20 Apr '12

20 Apr '12

Hi all, Anyone interested in acting as an admin for haskell.org this year? I'm afraid I won't have time. It's not that much work (filling in some information, sending out some emails, making sure things happen in time.) ---------- Forwarded message ---------- From: Carol Smith <carols(a)google.com> Date: Mon, Feb 27, 2012 at 11:47 AM Subject: Now Accepting Applications for Mentoring Organizations for GSoC 2012 To: Google Summer of Code Announce < google-summer-of-code-announce(a)googlegroups.com> Hi all, We're pleased to announce the applications for mentoring organizations for GoogleSummer of Code 2012 are now being accepted [1]. Please go Melange [2] to apply on behalf of your organization. Please note that the application period [3] closes on 9 March at 23:00 UTC. We will not accept any late applications for any reason. [1] - http://google-opensource.blogspot.com/2012/02/mentoring-organization-applic… [2] - http://www.google-melange.com [3] - http://www.google-melange.com/gsoc/events/google/gsoc2012 Cheers, Carol -- You received this message because you are subscribed to the Google Groups "Google Summer of Code Announce" group. To post to this group, send email to google-summer-of-code-announce(a)googlegroups.com. To unsubscribe from this group, send email to google-summer-of-code-announce+unsubscribe(a)googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-summer-of-code-announce?hl=en.

3 7

Conduits: Is Source a valid instance of Monad?
by Aristid Breitkreuz 04 Apr '12

04 Apr '12

Hi all, As you may have noticed, Michael Snoyman has been working on an alternative approach to I/O, called conduits. You can find it here: https://github.com/snoyberg/conduit When looking at the Source type (explained here: http://www.yesodweb.com/blog/2011/12/conduits) I noticed that they seem to behave "like lists", and naturally wondered if I could write a Monad instance for them. But first, let's have a brief look at the definition of Source: data SourceResult a = Open a | Closed data PreparedSource m a = PreparedSource { sourcePull :: ResourceT m (SourceResult a) , sourceClose :: ResourceT m () } newtype Source m a = Source { prepareSource :: ResourceT m (PreparedSource m a) } ResourceT deals with resource acquisition and releasing (making sure that all resources are released), and provides a an abstraction over IORef/STRef. For our purposes here, ResourceT is probably close enough to IO. So now the question again is, can we write a Monad instance for this? I have been able to write join (concatenate) and return (a source with a single non-repeated) element. https://gist.github.com/1525471 I _think_ it behaves properly like a Monad, but I'm not quite sure, and neither was Michael. Greg Weber then suggested bringing the question to this forum. What made the question difficult for me is that this would be a stateful Monad transformer, so I'm not quite sure how to test the Monad laws properly. There's a second part to this question: If Source turns out not to be a Monad, is it possibly a ZipList-like Applicative? And either way, which is more useful: The list-like or the ziplist-like instances (of Applicative/Monad)? Thank you, Aristid

4 4

blog software in Haskell?
by Ketil Malde 30 Mar '12

30 Mar '12

Hi, I just upgraded my server, and set up everything again. Except wordpress, as 1) I'm not too fond of its user interface, and 2) it's a big pile of PHP, difficult to keep updated, and basically a disaster waiting to happen (and in fact, it was hacked at one point). Before I enable it again, is there any alternatives I should consider? Preferably written in Haskell, of course, but other suggestions welcome as well. -k -- If I haven't seen further, it is by standing in the footprints of giants

5 6

Functional programming podcast
by Christopher Done 15 Mar '12

15 Mar '12

Show of hands, who would be interested in working on a podcast weekly or biweekly and what would you like to provide? Light banter is an acceptable answer. Some points that might be covered on such a podcast might be: * Latest FP conferences/hackathons/etc * Competitions * Interesting papers (new, or old and dug up) * Interesting blog posts or stackoverflow questions * New and interesting libraries/tech released * Developments in the communities, funding, business developments * Interviews with prominent FP chappies This bleeds over a little with Haskell Weekly News, but it's more like FP weekly "interesting stuff", and therefore there would be a lot more news to pack in. It would be something to listen to while you're walking to work with your ipod. On 21 February 2012 15:55, Mats Rauhala <mats.rauhala(a)gmail.com> wrote: > On 15:15 Tue 21 Feb , Christopher Done wrote: >> I recently thought it would be Pretty Cool to make an FP podcast, sort >> of a spoken Haskell Weekly News but covering all FP, blogs, packages, >> conferences, papers, standards, mailing lists, even stackoverflow, >> whatever's interesting in FP. We could use Gtalk or Mumble (both quite >> high quality audio) to conduct it and cut it up in audacity. > > I for one would be an interested listener

6 8

[ANNOUNCE] JuicyPixels 1.1 - image loading library (maintenance release)
by Vincent Berthoux 14 Mar '12

14 Mar '12

Hello list, This is a maintenance release without new functionality, the central change is the switch from Haskell Array to Data.Vector (to ease it's use for OpenGL texture loading). Juicy.Pixels 1.1 change log : - Fixing automatic bitmap decoding, the decodeImage function wasn't trying to decode bitmap - Converting Haskell array types to Data.Vector (thanks to Jason Dagit) - Some tiny documentation enhancement Hackage : http://hackage.haskell.org/package/JuicyPixels GitHub : https://github.com/Twinside/Juicy.Pixels Thanks Vincent Berthoux

1 1

If you'd design a Haskell-like language, what would you do different?
by Robert Clausecker 09 Mar '12

09 Mar '12

Image you would create your own language with a paradigm similar to Haskell or have to chance to change Haskell without the need to keep any compatibility. What stuff would you add to your language, what stuff would you remove and what problems would you solve completely different? Thanks in advance for all answers, yours Robert Clausecker

39 91

Monad.Reader #20 call for copy
by Edward Z. Yang 07 Mar '12

07 Mar '12

I'm pleased to announce that I, Edward Z. Yang, will be taking over Brent Yorgey's role as lead editor of the Monad Reader! Call for Copy: The Monad.Reader - Issue 20 -------------------------------------------- Whether you're an established academic or have only just started learning Haskell, if you have something to say, please consider writing an article for The Monad.Reader! The submission deadline for Issue 20 will be: **Monday, March 5** The Monad.Reader ~~~~~~~~~~~~~~~~ The Monad.Reader is a electronic magazine about all things Haskell. It is less formal than journal, but somehow more enduring than a wiki- page. There have been a wide variety of articles: exciting code fragments, intriguing puzzles, book reviews, tutorials, and even half-baked research ideas. Submission Details ~~~~~~~~~~~~~~~~~~ Get in touch with me if you intend to submit something -- the sooner you let me know what you're up to, the better. Please submit articles for the next issue to me by e-mail (ezyang(a)mit.edu) Articles should be written according to the guidelines available from http://themonadreader.wordpress.com/contributing/ Please submit your article in PDF, together with any source files you used. The sources will be released together with the magazine under a BSD license. If you would like to submit an article, but have trouble with LaTeX please let me know and we'll work something out.

1 1

Does somebody know about these functions?
by Johan Holmquist 03 Mar '12

03 Mar '12

Two functions that I see useful are described here and I would like to know if they are defined in some more or less standard Haskell library. Hoogle (http://www.haskell.org/hoogle) did not reveal anything about that. Function 'inter' applies given function to each succeeding pair of elements of a list. inter :: (a -> a -> b) -> [a] -> [b] inter f [] = [] inter f l = map (uncurry f) $ zip l (tail l) Example usage: and $ inter (<=) l -- checks if 'l' is ordered inter (,) l -- gives succeeding pairs Function 'withPair' takes a pair and applies a function to it's first element, another function to it's second element and finally combines the results with yet another function. withPair :: (a' -> b' -> c) -> (a -> a') -> (b -> b') -> (a,b) -> c withPair f fa fb (a,b) = fa a `f` fb b Example usage: words [] = [] words s = withPair (:) id words (break isSpace $ dropWhile isSpace s) lines [] = [] lines s = withPair (:) id lines (break (== '\n') s) mapPair = withPair (,) This function can abstract away the (in my opinion ugly) pattern (as seen in the examples): foo list = let (a,b) = <somefun> list in <somefun2> a `<combinedWith>` foo b Anyone knows about these two functions or variants thereof? Cheers /Johan

6 10