July 2011 - Haskell-Cafe

Paid work available in functional web programming
by Adam Chlipala 13 Jul '11

13 Jul '11

First, I apologize in advance if this post is deemed off-topic. It's about Ur/Web, a statically typed, pure functional programming languages that is much influenced by Haskell. For instance, Ur/Web includes monadic IO and type classes. I write to mention briefly that I'm looking for people interested in writing Ur/Web programs for pay. Ur/Web is a DSL for building modern web applications, and I believe it is truly a secret weapon for that domain, and one that should appeal to many Haskell fans. I have one customer now for whom I'm leading a project to develop a particular web application, and I'd like to have more. The current project would benefit from more programming help, and I would also like to develop a network of people interested in future projects. More information on Ur/Web can be found here: http://www.impredicative.com/ur/ So, are you interested in being paid at least market rates to develop real web applications in a cool Haskell-like language, thus helping to push functional programming further into the real world? Might you have any leads for possible customers for this kind of work, possibly including start-ups that want to do in-house development using a cool language with close support from the language creator (which happens to be me!)? I would love to receive reply e-mails with positive answers to either question!

5 5

Splitting Hackage Packages and re-exporting entire modules (with same module name)
by Thomas DuBuisson 13 Jul '11

13 Jul '11

All, I have decided it would be beneficial to split System.Crypto.Random and the rest of crypto-api into different packages. Is there I way I can create a package, "entropy", with System.Crypto.Random but continue to expose that module from crypto-api (allowing people who use that module some time to move)? If so, how? If not, does anyone else see value in this and how it can be added to the infrastructure? Cheers, Thomas

3 3

Seeking Don Stewart
by wren ng thornton 13 Jul '11

13 Jul '11

Hello all, Sorry for the spam. I'm trying to get ahold of Don Stewart, but it looks like there's some hiccup at Galois. When I mail him I get: <dons(a)galois.com>: host mail.galois.com[69.30.63.196] said: 550 5.1.1 <dons(a)galois.com>... User unknown (in reply to RCPT TO command) Does anyone know what's up, or if there's another (non-emergency) way to get in touch with him? -- Live well, ~wren

6 5

Baffling Hackage build log
by wren ng thornton 13 Jul '11

13 Jul '11

As a dutiful package maintainer I just checked to make sure unification-fd built correctly on Hackage. Unfortunately it didn't, and it gives this inscrutable error log: cabal: There is no package named unification-fd. Perhaps you need to run 'cabal update' first? Something awry on Hackage? -- Live well, ~wren

4 3

Re: [Haskell-cafe] Type checking oddity -- maybe my own confusion
by oleg＠okmij.org 13 Jul '11

13 Jul '11

Ryan Newton wrote: > The desired goal was that everywhere I construct a value using the Assign > constructor, that the resulting value's type to be tainted by the AssignCap > constraint. Your code essentially accomplishes the goal: > data E m where > Assign :: AssignCap m => V -> E m -> E m -> E m > Varref :: V -> E m > -- ... Every time you construct the value of the type (E m) with the Assign constructor, you have to constructively prove -- provide evidence for -- that the type m is a member of AssignCap. That evidence is stored within the E m value and so can be reused whenever it is needed later. Let us modify the example slightly: > class AssignCap m > class MutateCap m > > data E m where > Assign :: AssignCap m => V -> E m -> E m -> E m > Mutate :: MutateCap m => V -> E m -> E m -> E m > Varref :: V -> E m > -- ... > > type V = String > > -- test1 :: E t -> E t > test1 (Assign v x1 x2) = Assign v x1 x2 > > -- test2 :: MutateCap t => E t -> E t > test2 (Assign v x1 x2) = Mutate v x1 x2 To use the constructor Assign, we need the evidence that AssignCap m holds. The deconstructed value (Assign v x1 x2) provides such an evidence (as a `hidden' field of the data type). Therefore, the inferred type for test1 has no constraints. In contrast, in test2 nothing provides Mutate with the evidence that MutateCap m holds. Therefore, the inferred type has the MutateCap m constraint. If storing the evidence is not desired, then one should use ordinary ADT with smart constructors: > -- Data constructors should not be exported > data E1 m = Assign1 V (E1 m) (E1 m) | Varref1 V > isAssign (Assign1 v x1 x2) = Just (v,x1,x2) > isAssign _ = Nothing > > assign :: AssignCap m => V -> E1 m -> E1 m -> E1 m > assign = Assign1 > > -- test3 :: AssignCap m => E1 m -> E1 m > test3 e | Just (v,x1,x2) <- isAssign e = assign v x1 x2 OCaml has a so-called private constructors, which permit deconstruction but prohibit construction. They are quite handy, saving us trouble writing the views like isAssign. > Actually... to go a bit further, I thought there was some way to arrange > this so that, upon GHC type-checking the case statement, it would realize > that certain cases are forbidden based on the type, and would consider the > pattern match complete without them (or issue an error if they are present). The key word in the phrase ``certain cases are forbidden based on the type'' is _type_ -- rather than a type class. If you wish to use this special GADT feature, you have to `invert' your design. Rather than specifying what is _required_ to construct an (E m) value, you should specify what is _provided_. > data E2 m where > Assign2 :: V -> E2 m -> E2 m -> E2 IOT > Varref2 :: V -> E2 PureT > > test4 :: E2 IOT -> E2 IOT > test4 (Assign2 v x1 x2) = Assign2 v x1 x2 > test4 (Varref2 _) = undefined The compiler complaints Couldn't match type `IOT' with `PureT' Inaccessible code in a pattern with constructor Varref2 :: V -> E2 PureT, in an equation for `test4' In the pattern: Varref2 _ In an equation for `test4': test4 (Varref2 _) = undefined as desired.

1 0

Type checking oddity -- maybe my own confusion
by Ryan Newton 12 Jul '11

12 Jul '11

Hi all, Is there something wrong with the code below? My anticipation was that the type of "test" would include the class constraint, because it uses the Assign constructor. But if you load this code in GHCI you can see that the inferred type was "test :: E m -> E m". Thanks, -Ryan {-# LANGUAGE GADTs #-} class AssignCap m data PureT data IOT instance AssignCap IOT data E m where Assign :: AssignCap m => V -> E m -> E m -> E m Varref :: V -> E m -- ... type V = String -- I expected the following type but am not getting it: -- test :: AssignCap m => E m -> E m test x = case x of Assign v e1 e2 -> Assign v e1 e2 -- And this is the same: Assign v e1 e2 -> x

3 3

Why is (+++) not a functor?
by Felipe Almeida Lessa 12 Jul '11

12 Jul '11

Hey! =) ArrowChoice's (+++) documentation [1] says that "this is in general not a functor" [1]. What does it mean for (+++) to be or not to be a functor? Cheers, [1] http://hackage.haskell.org/packages/archive/base/4.3.1.0/doc/html/Control-A… -- Felipe.

2 1

Re: [Haskell-cafe] How to ensure code executes in the context of a specific OS thread?
by Jason Dagit 12 Jul '11

12 Jul '11

On Jul 5, 2011 1:04 PM, "Jason Dagit" <dagitj(a)gmail.com> wrote: > > On Tue, Jul 5, 2011 at 12:33 PM, Ian Lynagh <igloo(a)earth.li> wrote: > > On Tue, Jul 05, 2011 at 08:11:21PM +0100, Simon Marlow wrote: > >> > >> In GHCi it's a different matter, because the main thread is running > >> GHCi itself, and all the expressions/statements typed at the prompt > >> are run in forkIO'd threads (a new one for each statement, in fact). > >> If you want a way to run command-line operations in the main thread, > >> please submit a feature request. I'm not sure it can be done, but > >> I'll look into it. > > > > We already have a way: -fno-ghci-sandbox > > I've removed all my explicit attempts to forkIO/forkOS and passed the > command line flag you mention. I just tried this but it doesn't > change the behavior in my example. I tried it again and discovered that due to an argument parsing bug in cabal-dev that the flag was not passed correctly. I explicitly passed it and verified that it works. Thanks for the workaround. By the way, I did look at the user guide for options like this and didn't see it. Which part of the manual is it in? Can I still make a feature request for a function to make code run on the original thread? My reasoning is that the code which needs to run on the main thread may appear in a library in which case the developer has no control over how ghc is invoked. The alternative appears to be context specific workarounds. I think that a general solution, if possible, will make gui libraries easier to develop for Ghc. I'm hooping it's as simple as exposing a pthreads call. Thanks, Jason

6 24

The Typeable class is changing
by Yitzchak Gale 12 Jul '11

12 Jul '11

Simon Marlow has announced[1] on the Haskell Libraries list that the Typeable class is changing. The standard way to create a Typeable instance is just to derive it. If you do that, you will not be affected by this change. But it seems that many packages create Typeable instances by explicitly using mkTyCon. If your package does this, it will eventually break, after a deprecation period. Please respond to this thread if you own a package that will be affected by this change. Can someone who has quick access to the entire contents of Hackage please do a grep and find out exactly which packages on Hackage will be affected? Thanks. -Yitz [1] http://www.haskell.org/pipermail/libraries/2011-July/016546.html

8 9

Fixing Performance Leaks at the Type Level
by Gershom Bazerman 12 Jul '11

12 Jul '11

This post is in literate Haskell. It describes how certain performance leaks are introduced in type level programming. These leaks do not affect program runtimes, but can cause compile times to grow drastically. They exist both with Functional Dependencies and Type Families, but are currently worse with the former, and have grown worse with the new constraint solver in GHC 7. It is intended both as a guide to those encountering these issues, and as a motivation for the GHC development team to address such issues as the constraint solver is developed and improved. > {-# OPTIONS_GHC -fcontext-stack=1000 #-} > {-# LANGUAGE FlexibleContexts, FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, OverlappingInstances, TypeSynonymInstances, TypeOperators, UndecidableInstances, TypeFamilies #-} > module TypePerformance where Our running example, for simplicity's sake, is a type-level map of a single function. For reference, here is the code for a simple value-level map of a single function. > vfoo = id > mapfoo (x : xs) = vfoo x : mapfoo xs > mapfoo [] = [] Because Haskell is a lazy language, this runs in O(n) time and constant stack. We now lift map to the type level, to operate over HLists. First, the basic HList types > infixr 3 :* > data x :* xs = x :* xs deriving Show > data HNil = HNil deriving Show Next, a large boring HList > -- Adds ten cells > addData x = i :* i :* d :* d :* s :* > i :* i :* d :* d :* s :* > x > where i = 1 :: Int > d = 1 :: Double > s = "" > > -- Has 70 cells. > sampleData = addData $ addData $ addData $ addData $ addData $ > addData $ addData $ > HNil Next, a simple polymorphic function to map > class Foo x y | x -> y > where foo :: x -> y > foo = undefined > instance Foo Int Double > instance Foo Double Int > instance Foo String String Now, our map > class HMapFoo1 as bs | as -> bs where > hMapFoo1 :: as -> bs > > instance (Foo a b, HMapFoo1 as bs) => HMapFoo1 (a :* as) (b :* bs) where > hMapFoo1 (x :* xs) = foo x :* hMapFoo1 xs > > instance HMapFoo1 HNil HNil where > hMapFoo1 _ = HNil If we enable the following line, compilation time is ~ 9 seconds. > testHMapFoo1 = hMapFoo1 sampleData Furthermore, playing with the size of sampleData, we see that the time spent in compilation is superlinear -- each additional cell costs a greater amount of time. This is because while Haskell is lazy at the value level, it is strict at the type level. Therefore, just as in a strict language, HMapFoo1's cost grows O(n^2) because even as we induct over the as, we build up a stack of bs. Just as in a strict language, the solution is to make hMapFoo tail recursive through introducing an accumulator. This also reverses the hlist, but never mind that. > class HMapFoo2 acc as bs | acc as -> bs where > hMapFoo2 :: acc -> as -> bs > > instance (Foo a b, HMapFoo2 (b :* bs) as res) => HMapFoo2 bs (a :* as) res where > hMapFoo2 acc (x :* xs) = hMapFoo2 (foo x :* acc) xs > > instance HMapFoo2 acc HNil acc where > hMapFoo2 acc _ = acc If we enable the following line, compilation time is a much more satisfying ~0.5s. > testHMapFoo2 = hMapFoo2 HNil sampleData But wait, there's trouble on the horizon! Consider the following version: > class HMapFoo3 acc as bs | acc as -> bs where > hMapFoo3 :: acc -> as -> bs > > instance (HMapFoo3 (b :* bs) as res, Foo a b) => HMapFoo3 bs (a :* as) res where > hMapFoo3 acc (x :* xs) = hMapFoo3 (foo x :* acc) xs > > instance HMapFoo3 acc HNil acc where > hMapFoo3 acc _ = acc The only difference between hMapFoo2 and hMapFoo3 is that the order of constraints on the inductive case has been reversed, with the recursive constraint first and the immediately checkable constraint second. Now, if we enable the following line, compilation time rockets to ~6s! > testHMapFoo3 = hMapFoo3 HNil sampleData Slowdowns such as those described here are not a purely hypothetical issue, but have caused real problems in production code. The example given above is fairly simple. The constraints used are minimal and easily checked. In real programs, the constraints are more difficult, increasing constant factors significantly. These constant factors, combined with unexpected algorithmic slowdowns due to the type inference engine, can lead (and have lead) to compilation times of HList-style code becoming deeply unwieldy-to-unusable, and can lead (and have lead) to this occuring only well after this code has been introduced and used on smaller cases without trouble. The constraint solver should certainly be smart enough to reduce the compile times of HMapFoo3 to those of HMapFoo2. In fact, with type families, the there is no difference (see below). Could the compiler be smart enough to do the same for HMapFoo1? I'm not sure. Certainly, it could at least knock down its own constant factors a bit, even if it can't improve the big-O performance there. ---- Appendix: Examples with Type Families As the below code demonstrates, the same issues demonstrated with Functional Dependencies also appear with Type Families, although less horribly, as their code-path seems more optimized in the current constraint solver: > class TFoo x where > type TFooFun x > tfoo :: x -> TFooFun x > tfoo = undefined > > instance TFoo Int where > type TFooFun Int = Double > instance TFoo Double where > type TFooFun Double = Int > instance TFoo String where > type TFooFun String = String > > class THMapFoo1 as where > type THMapFoo1Res as > thMapFoo1 :: as -> THMapFoo1Res as > > instance (TFoo a, THMapFoo1 as) => THMapFoo1 (a :* as) where > type THMapFoo1Res (a :* as) = TFooFun a :* THMapFoo1Res as > thMapFoo1 (x :* xs) = tfoo x :* thMapFoo1 xs > > instance THMapFoo1 HNil where > type THMapFoo1Res HNil = HNil > thMapFoo1 _ = HNil The following, when enabled, takes ~3.5s. This demonstrates that slowdown occurs with type families as well. > testTHMapFoo1 = thMapFoo1 sampleData > class THMapFoo2 acc as where > type THMapFoo2Res acc as > thMapFoo2 :: acc -> as -> THMapFoo2Res acc as > > instance (TFoo a, THMapFoo2 (TFooFun a :* acc) as) => THMapFoo2 acc (a :* as) where > type THMapFoo2Res acc (a :* as) = THMapFoo2Res (TFooFun a :* acc) as > thMapFoo2 acc (x :* xs) = thMapFoo2 (tfoo x :* acc) xs > > instance THMapFoo2 acc HNil where > type THMapFoo2Res acc HNil = acc > thMapFoo2 acc _ = acc The following, when enabled, takes ~0.6s. This demonstrates that the tail recursive transform fixes the slowdown with type families just as with fundeps. > testTHMapFoo2 = thMapFoo2 HNil sampleData > class THMapFoo3 acc as where > type THMapFoo3Res acc as > thMapFoo3 :: acc -> as -> THMapFoo3Res acc as > > instance (THMapFoo3 (TFooFun a :* acc) as, TFoo a) => THMapFoo3 acc (a :* as) where > type THMapFoo3Res acc (a :* as) = THMapFoo3Res (TFooFun a :* acc) as > thMapFoo3 acc (x :* xs) = thMapFoo3 (tfoo x :* acc) xs > > instance THMapFoo3 acc HNil where > type THMapFoo3Res acc HNil = acc > thMapFoo3 acc _ = acc The following, when enabled, also takes ~0.6s. This demonstrates that, unlike the fundep case, the order of type class constraints does not, in this instance, affect the performance of type families. > testTHMapFoo3 = thMapFoo3 HNil sampleData --Gershom

2 1