- Haskell-Cafe - Haskell.org

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

13 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 13 Jul '11

13 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

ANN: unification-fd: simple generic unification
by wren ng thornton 12 Jul '11

12 Jul '11

-------------------------------------------- -- unification-fd 0.5.0 -------------------------------------------- The unification-fd package offers generic functions for first-order structural unification (think Prolog programming or Hindley--Milner type inference). I've had this laying around for a few years, so I figured I might as well publish it. An effort has been made to try to make this package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[1]: Rank2Types MultiParamTypeClasses FunctionalDependencies FlexibleContexts FlexibleInstances UndecidableInstances [1] With the exception of fundeps which are notoriously difficult to implement. However, they are supported by Hugs and GHC 6.6, so I don't feel bad about requiring it. Once the API stabilizes a bit more I plan to release a unification-tf package which uses type families instead, for those who feel type families are easier to implement or use. -------------------------------------------- -- Description -------------------------------------------- The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type PureTerm = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked (or Nothing if this level doesn't match). class (Traversable t) => Unifiable t where zipMatch :: t a -> t b -> Maybe (t (a,b)) The choice of which variable implementation to use is defined by similarly simple classes Variable and BindingMonad. We store the variable bindings in a monad, for obvious reasons. In case it's not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating the cost of naively applying bindings eagerly. There are currently two implementations of variables provided: one based on STRefs, and another based on a state monad carrying an IntMap. The former has the benefit of O(1) access time, but the latter is plenty fast and has the benefit of supporting backtracking. Backtracking itself is provided by the logict package and is described in Kiselyov et al. (2005). In addition to this modularity, unification-fd implements a number of optimizations over the algorithm presented in Sheard (2001)--- which is also the algorithm presented in Cardelli (1987). * Their implementation uses path compression, which we retain. Though we modify the compression algorithm in order to make sharing observable. * In addition, we perform aggressive opportunistic observable sharing, a potentially novel method of introducing even more sharing than is provided by the monadic bindings. Basically, we make it so that we can use the observable sharing provided by the previous optimization as much as possible (without introducing any new variables). * And we remove the notoriously expensive occurs-check, replacing it with visited-sets (which detect cyclic terms more lazily and without the asymptotic overhead of the occurs-check). A variant of unification which retains the occurs-check is also provided, in case you really need to fail fast for some reason. * Finally, a highly experimental branch of the API performs *weighted* path compression, which is asymptotically optimal. Unfortunately, the current implementation is quite a bit uglier than the unweighted version, and I haven't had a chance to perform benchmarks to see how the constant factors compare. Hence moving it to an experimental branch. I haven't had a chance to fully debug these optimizations, though they pass some of the obvious tests. If you find any bugs, do be sure to let me know. Also, if you happen to have a test suite or benchmark suite for unification on hand, I'd love to get a copy. -------------------------------------------- -- References -------------------------------------------- Luca Cardelli (1987) /Basic polymorphic typechecking/. Science of Computer Programming, 8(2):147--172. Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) /Efficient Functional Unification and Substitution/, Technical Report UU-CS-2008-027, Utrecht University. <http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf> Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) /Backtracking, Interleaving, and/ /Terminating Monad Transformers/, ICFP. <http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf> Tim Sheard (2001) /Generic Unification via Two-Level Types/ /and Paramterized Modules/, Functional Pearl, ICFP. <http://web.cecs.pdx.edu/~sheard/papers/generic.ps> Tim Sheard & Emir Pasalic (2004) /Two-Level Types and/ /Parameterized Modules/. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples. <http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps> Wouter Swierstra (2008) /Data types a la carte/, Functional Pearl. JFP 18: 423--436. <http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf> -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unification-fd Darcs: http://community.haskell.org/~wren/unification-fd Haddock (Darcs version): http://community.haskell.org/~wren/unification-fd/dist/doc/html/unification… -- Live well, ~wren

1 0

Re: [Haskell-cafe] [Haskell] Call for GUI examples - Functional Reactive Programming
by Paul Liu 12 Jul '11

12 Jul '11

Hi James, I think you meant to reply to the list. For one, I wouldn't consider GUI programming based on HTML as declarative, since more often than not, the format says nothing about its behavior, and when it does, it's through javascript, which is hardly declarative. Regards, Paul Liu On Tue, Jul 12, 2011 at 5:17 AM, James Deng <cnjamesdeng(a)gmail.com> wrote: > These days, more and more GUI programming are done in declarative, such as > HTML(jQuery), Mozilla XUL, android UI XML. > > Haskell is an excellent declarative language, so should have the advantages > of constructing GUI in declarative, intuitive and powerful way. But so far, > there is not such a GUI library intuitive like Html, powerful like XUL. > > I expect something like html to layout GUI, and a haskell GUI engine would > render the user interfaces files. > Where is the gap lying? > > On 07/12/2011 05:51 AM, Paul Liu wrote: > > You guys might want to checkout the recent work on Euterpea at Yale > CS. In particular: > > 1. Paul Hudak is writing a new book. > http://plucky.cs.yale.edu/cs431/reading.htm > 2. It uses FRP and arrows for sound synthesis. > 3. It combines FRP signals with monadic (which recently gets > re-written in arrows) GUI composition. > 4. New novel techniques is being developed to handle I/O within arrows > framework. > > The code can be obtained through darcs, details at > http://plucky.cs.yale.edu/cs431/software_resources.htm > > Notably, the way it handles GUI is that the composition of widgets are > static, but the signals flowing between them are dynamic. This closely > follows Conal Elliott's Phooey approach, and greatly reduces the > complexity of GUI programming. > > Disclaimer: I was an ex-student who worked on this project. > > Regards, > Paul Liu > > On Thu, Jul 7, 2011 at 11:08 PM, Heinrich Apfelmus > <apfelmus(a)quantentunnel.de> wrote: > > Dear Haskellers, > > Can GUI programming be liberated from the IO monad? > > > Regards, > -- > James Deng > http://cnjdeng.appspot.com -- Regards, Paul Liu

1 0

Inconsistent trailing comma in export list and record syntax
by L Corbijn 12 Jul '11

12 Jul '11

Hello, I'm wondering why the trailing comma is allowed in export syntax, but not in record syntax, here an example module Foo ( export1, -- is allowed ) where data Type = Type { record1 :: Foo, -- is not allowed } To me this seems quite inconsistent and sometimes quite frustrating, imagine the case that you want to temporarily remove the last record: data Type = Type { record1 :: Foo, -- record2 :: Bar } this would fail due to an extra comma that has to be commented out. You could of course say that I'm using a bad style, but it remains that it seems to be inconsistent to allow a trailing comma in one place and not in the other. So is there an reason for this? Lars Corbijn

8 7

External system connections
by Richard Wallace 11 Jul '11

11 Jul '11

Hello all, I'm trying to understand how to properly structure a connection to an external system. I'm writing an application that processes requests (it's an IRC bot - ya, I've looked at lambabot but it's a bit beyond my current understanding and I'm really trying to learn this stuff and find the best way to do that is to write it myself) and sends requests to an external system, via SOAP. The SOAP requests should be sent on separate threads. The SOAP server requires an initial request for authentication be made to obtain a token used on subsequent requests. There are three ways I can structure this. One is to do the authentication with the SOAP server when the application starts up and just use that token for all subsequent requests. This will fall over if the token times out and I'd have to restart the application. Another way is to do authenticate with the server and get a new token for each request. This is obviously really inefficient. What I'd like to do is something a bit smarter. When a request to the SOAP server is to be made, if we have a token then we try and use it. If it fails, we reauthenticate and get a new token. When establishing a new token, other threads trying to send SOAP requests should block until a new token is available. There are other conditions that should be handled - such as an exponential back-off when the SOAP server can't be reached - but I feel like reestablishing the authentication token is really the key concern here. Unfortunately, I have no idea right now how to write this in Haskell. Any pointers would be awesome. Thanks! Rich

9 12

Fwd: The Typeable class is changing
by Alberto G. Corona 11 Jul '11

11 Jul '11

What to do when the data has been defined in other package and provides no Typeable instance? 2011/7/11 Yitzchak Gale <gale(a)sefer.org> > 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 > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1