- Haskell-Cafe - Haskell.org

Semantic web RDF store
by Vasili I. Galchin 12 Jun '09

12 Jun '09

Hello, Currently I am working on re-packaging Swish written by Graham Klyne so that is cabalized... I am chugging along. I am also thinking about writing a FFI for some RDF store API like http://www.rdflib.net/store/ so that Swish could be hooked into a "reliable"persistent store where the store type can be switched out like MySQL dor SQLite, etc. Has any one already done something like this? I don't like reinventing the wheel. Regards, Vasili

1 1

Re: [Haskell-cafe] Building a tree?
by michael rice 12 Jun '09

12 Jun '09

Example understood. Thanks. Is there a module for binary trees? Michael --- On Wed, 6/10/09, wren ng thornton <wren(a)freegeek.org> wrote: From: wren ng thornton <wren(a)freegeek.org> Subject: Re: [Haskell-cafe] Building a tree? To: haskell-cafe(a)haskell.org Date: Wednesday, June 10, 2009, 8:13 PM michael rice wrote: > Here's a function from Data.Tree: > > unfoldTree :: (b -> (a, [b])) -> b -> Tree a > Build a tree from a seed value > > Could someone please give me a brief example of usage. Data.Tree> let t = unfoldTree (\i -> (show i, [i`div`2..i-1])) Data.Tree> putStr . drawTree $ t 8 -- Live well, ~wren _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

6 5

List comprehensions and impredicative rank-N types
by Vladimir Reshetnikov 11 Jun '09

11 Jun '09

Hi, Consider the following definitions: ----------------------------------------------------------- {-# LANGUAGE RankNTypes, ImpredicativeTypes #-} foo :: [forall a. [a] -> [a]] foo = [reverse] bar :: [a -> b] -> a -> b bar fs = head fs ----------------------------------------------------------- According to the Haskell Report, [f | f <- foo] translates to (let ok f = [f]; ok _ = [] in concatMap ok foo), right? So, I wonder why (bar [f | f <- foo]) typechecks, but (bar (let ok f = [f]; ok _ = [] in concatMap ok foo)) and (bar foo) do not typecheck? Thanks, Vladimir

1 0

who's up for a hackathon? (ICFP, late Aug, early Sept)
by Eric Kow 11 Jun '09

11 Jun '09

Dear Haskellers, ICFP 2009 takes place from Monday 31 August to Wednesday 2 September, with the Haskell Symposium following it on 3 September. Would anybody be interested having a Haskell Hackathon during this? My thinking is that to catch people who are only going to the Haskell Symposium, the best time is the following weekend (4-6 September). Otherwise, the weekend before (29-30 August) is also an option and has the benefit of catching people before they get tired :-) Rah, rah, hackathon! 1. If possible, I'd like get a idea if there is any interest in attending such a Hackathon if it were to take place. 2. For rah-rah Hackathon to work, we need people! Could I get one kind (and local) soul to act as an organiser for this? Thanks! -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9

2 1

a cool paper (.pdf) on Cabal?
by Vasili I. Galchin 11 Jun '09

11 Jun '09

Hello, Before I found a really cool paper on Cabal motivation and architecture. I can no longer find this paper. Any ideas/suggestions? Kind regards, Vasili

3 3

Re: [Haskell] ANNOUNCE: testrunner-0.9
by Max Bolingbroke 11 Jun '09

11 Jun '09

2009/6/8 Reinier Lamers <tux_rocker(a)reinier.de>: > I checked out testpack and that did not meet my requirements. I don't know if > I considered test-framework. If I did, it may be that I was turned off by the > fact that the 'home page' link on cabal just goes to a web presentation of the > source tree on github. Reinier, You are quite right that this is a weakness. I've been meaning to put a site together for a while, and your comment gave me the impetus to do it: http://batterseapower.github.com/test-framework/ That's much friendlier! All the best, Max

3 3

ANNOUNCE: Galois is hiring functional programmers
by Don Stewart 11 Jun '09

11 Jun '09

Galois is hiring. Bringing together mathematicians, researchers and technologists, Galois, based in Portland, Oregon, was founded in 1999 with the mission to apply functional languages and formal methods to solve real world problems. Today, over 30 members strong, we’re living the vision, designing and developing advanced technologies for safety and security-critical systems, networks, and applications. Galois technical staff members play a pivotal role in developing advanced software technology. Members work on one or more projects, and are expected to perform in a variety of roles based upon their talents and organizational needs. Technical staff may be called upon to write proposals, gather requirements, and work in all stages of the software development process, from requirements gathering to testing and validation. Additional duties may include project management, technology research and development, and technical infrastructure development. We’re looking for people who can invent, learn, think, and inspire. We reward creativity and thrive on collaboration. We offer great benefits and perks, including a 401K plan, stock options, paid vacation, family health plan, flexible work schedule, a casual work environment, snacks, espresso and foosball. Galois technical staff members usually work in a small team setting (2-5 members), and must successfully interact with clients, partners, and other employees in a highly cooperative, collaborative, and intellectually challenging environment. A Masters or Ph.D. degree in Computer Science is desirable but not required. Additionally, a strong programming background and experience with Haskell or other functional programming languages is preferred but not required. Must work well with customers, including building rapport, identifying needs, and communicating with strong written, verbal and presentation skills. Must be highly motivated and able to self-manage to deadlines and quality goals. To learn more about us, visit http://www.galois.com and http://www.galois.com/company/careers The types of technology we use are covered in our blog: http://www.galois.com/blog/ We’d like to hear from you! Send your cover letter and resume to us at jobs2009(a)galois.com.

1 0

Lightweight type-level dependent programming in Haskell
by Ryan Ingram 11 Jun '09

11 Jun '09

(Literate Haskell post) > {-# LANGUAGE GADTs, RankNTypes, TypeFamilies, ScopedTypeVariables, FlexibleContexts #-} > module Dependent where I recently discovered an interesting way of closing typeclasses while playing with type-level peano naturals: First we build peano integers at the type level: > data Z = Z > newtype S n = S n And a couple of generally useful type-level combinators: > newtype I x = I { unI :: x } > newtype K x y = K { unK :: x } (We could also include the S combinator, under a different name, but I haven't needed it yet...) This representation isn't "closed"; there's nothing forcing the "n" in S n to be Z or S n. But we can make a typeclass easily: class Nat n instance Nat Z where ... instance Nat n => Nat (S n) where ... But again, this typeclass is open. What I recently realized is that it's easy to close the typeclass by requiring instances to provide a simple implementation of "typecase": > class Nat n where > caseNat :: forall r. n -> (n ~ Z => r) -> (forall p. (n ~ S p, Nat p) => p -> r) -> r By parametricity, any non _|_ implementation of caseNat has to prove either (n ~ Z), to call the first branch, or (n ~ S p) for some other natural p, to call the second. > instance Nat Z where > caseNat _ z _ = z > instance Nat n => Nat (S n) where > caseNat (S n) _ s = s n (Interesting side note: the S n pattern match is automatically lazy, since S is a newtype) Somewhat surprisingly, caseNat is sufficient to prove *dependent* induction: > induction :: forall p n. Nat n => n -> p Z -> (forall x. Nat x => p x -> p (S x)) -> p n > induction n z s = caseNat n isZ isS where > isZ :: n ~ Z => p n > isZ = z > isS :: forall x. (n ~ S x, Nat x) => x -> p n > isS x = s (induction x z s) What does this function mean? Through the Curry-Howard lens, it says: If we have a proof of P 0, and a proof of (P x -> P (x+1)) for any natural x, then we can prove P n for any natural n! The proof simply proceeds by case analysis on n; we know that the proof terminates since the recursive step works at a strictly smaller type, and Haskell types are all finite in size. Now, of course, this isn't any different from case analysis on this GADT: > data Peano a where > Pz :: Peano Z > Ps :: Peano n -> Peano (S n) > inductP :: forall n p. Peano n -> p Z -> (forall x. Peano x -> p x -> p (S x)) -> p n > inductP Pz z s = z > inductP (Ps n) z s = s n (inductP n z s) In fact, the whole point of GADT case analysis is to introduce the type-level coercions that caseNat makes explicit. So there's not a huge gain here. There is one interesting benefit that the typeclass answer gives you, however; you can let the compiler derive the proof for you: > witnessNat :: forall n. Nat n => n > witnessNat = theWitness where > theWitness = unI $ induction (undefined `asTypeOf` theWitness) (I Z) (I . S . unI) Then we can optimize the implementation of witness to "unsafeCoerce Z" after the typechecker agrees with our proof. Another useful tool is existentials and witnesses; existentials allow you to do value-level calculation on "Nat"; witnesses allow you to construct a proof of Nat n and return it from a proof; there's no other way to return that something is a member of a typeclass. > data AnyNat where AnyNat :: Nat n => n -> AnyNat > data IsNat n where IsNat :: Nat n => IsNat n > mkNat :: Integer -> AnyNat > mkNat x | x < 0 = error "Nat must be >= 0" > mkNat 0 = AnyNat Z > mkNat x = case (mkNat (x-1)) of (AnyNat n) -> AnyNat (S n) > natToInteger :: Nat n => n -> Integer > natToInteger n = unK $ induction n (K 0) (K . (+1) . unK) > prec_app = 11 > instance Show AnyNat where > showsPrec p (AnyNat n) = showParen (p > prec_app) (showString "mkNat " . shows (natToInteger n)) Fun exercises: > data TEq a b where TEq :: (a ~ b) => TEq a b 1) Write a sized list GADT, and build some lists using combinators on Nat. Here's an example: myReplicate a = induction witnessNat Nil (Cons a) For me, ghc correctly infers this function to have the type myReplicate :: (Nat n) => a -> List a n. It's nice that I don't have to specify n anywhere! Try implementing fold :: Nat n => (forall x. Nat x => a -> p x -> p (S x)) -> List a n -> p n 2) (Easy) Prove that all sized lists have a length that is a natural number: lengthIsNat :: SizedList a n -> IsNat n 3) Prove that equality is decidable on naturals: natEqDec :: forall x y. (Nat x, Nat y) => x -> y -> Maybe (TEq x y) 4) Write the standard "plus" type family, then prove: plusIsNat :: forall x y. (Nat x, Nat y) => IsNat (Plus x y) plusIsComm :: forall x y. (Nat x, Nat y) => TEq (Plus x y) (Plus y x) (While doing this exercise, I was impressed at how good the type coercion prover is) 5) (Challenge) Write definitions for "instance Eq AnyNat" and "instance Num AnyNat"

3 2

Re: FlexibleContexts and FlexibleInstances
by Niklas Broberg 11 Jun '09

11 Jun '09

Hi Claus, What you describe is exactly how I would *want* things to work. It's nice to hear my wishes echoed from a user perspective. :-) On Wed, Jun 10, 2009 at 4:43 PM, Claus Reinke<claus.reinke(a)talk21.com> wrote: > just a few comments from a user (who would really, really, like to be > able to define pragma collections, so that he doesn't have to switch > on half a dozen separate extensions every time;-). > >> The following toy program requires MultiParamTypeClasses OR >> FlexibleContexts in order to be accepted by GHC(i): >> >>> f :: (T a b) => a -> Int >>> f _ = 0 >> >> This of course assumes that we import the definition of T, we *must* >> have MultiParamTypeClasses enabled if we want to declare T. Both >> extensions thus enable classes with more than one argument to appear >> in contexts. > > Only MultiParamTypeClasses does (and neither extension is needed in the > module defining 'f', if 'T' is imported, which suggests that > MultiParamTypeClasses is propagated to importers - this isn't true for > most other extensions). The documentation still points to -fglasgow-exts, so > it doesn't seem to answer these questions.. Right you are - which seems very strange to me. GHC accepts the module defining 'f' with no flags at all, even though it is clearly not Haskell 98. I'd go so far as to say that's a bug (as opposed to just unwanted/unexpected behavior). >>> f :: (T a ()) => a -> Int >>> f _ = 0 >> >> i.e. changing the second argument to T to () instead, means we now >> *must* have FlexibleInstances, in order to allow the non-tyvar >> argument. This is nothing surprising, this is what FlexibleInstances >> are supposed to do. > > You mean FlexibleContexts. Indeed I do. >> Now, FlexibleInstances *also* lifts the restriction on contexts, just >> like FlexibleContexts - but *only* for the contexts of instance >> declarations. > > No. FlexibleInstances is about instance *heads*, FlexibleContexts is about > contexts everywhere (in practice, there are some bugs;-). Right, this is exactly what I *want* should happen, both as a user and as an implementor, but that's not how GHC does it. FlexibleInstances do enable FlexibleContexts for contexts in instance declarations - which I think is a wart. > class T a b -- requires MultiParamTypeClasses instance T a a -- requires > FlexibleInstances instance Eq () => T a [b] -- requires FlexibleContexts > instance Eq [a] => T a b -- requires UndecidableInstances Agreed - but here you avoid the tricky cases like my 'f' above. ;-) What I would want, and what I believe you want as well, is the following: ======================================== ** MultiParamTypeClasses: Enables more than one parameter in class declarations, instance heads and more than one argument to class assertions in contexts everywhere. Formally, it would mean the following changes to the Haskell 98 syntax: topdecl -> class [scontext =>] tycls tyvar1 ... tyvarn [where cdecls] (n >=1) | instance [scontext =>] qtycls inst1 ... instn [where idecls] (n >=1) context -> class | ( class1 , ... , classn ) (n>=0) class -> qtycls cls1 ... clsn (n>=1) cls -> tyvar | ( tyvar atype1 ... atypen ) (n>=1) scontext -> simpleclass | ( simpleclass1 , ... , simpleclassn ) (n>=0) simpleclass -> qtycls scls1 ... sclsn (n>=1) scls -> tyvar ** FlexibleContexts: Enables the use of non-tyvar (or tyvar applied to types) arguments to class assertions in contexts everywhere (orthogonal to whether there can be several arguments or just one). Formally it means the following syntactic changes to Haskell 98: fcontext -> fclass | ( fclass1 , ... , fclassn ) (n>=0) fclass -> qtycls atype1 ... atypen (n>=1) topdecl -> data [fcontext =>] simpletype = constrs [deriving] | newtype [fcontext =>] simpletype = newconstr [deriving] | class [fcontext =>] tycls tyvar [where cdecls] | instance [fcontext =>] qtycls inst [where idecls] gendecl -> vars :: [fcontext =>] type for the single-argument case. (Note that I wrote type in my proposal in the OP, but it should of course be atype.) ** FlexibleInstances: Enables the use of arguments other than type constructors (possibly applied to tyvars) in instances *heads* (orthogonal to whether there can be one or more arguments, and what the context may look like). Formally it means the following syntactic changes to Haskell 98: topdecl -> instance [scontext =>] qtycls inst [where idecls] inst -> atype for the single-parameter standard-context case. (Note again that it should be atype and not type as I wrote in the OP.) ======================================== This of course only touches the syntactic part. It doesn't attempt to track things like 'instance (T a a) => R a b' that would be enabled by FlexibleContexts, nor does it attempt to track things like the Paterson conditions, but the syntax is all I'm interested in at the moment. This is the stance I will use for haskell-src-exts, unless someone protests wildly. If there is any interest, I can also propose these cases as bug reports to GHC. I hesitate to make formal proposals (e.g. for Haskell') regarding these extensions since I'm not sure I have the full story regarding the non-syntactic parts. But if there is a particular interest in that then I might go the extra mile there too. Cheers, /Niklas

1 0

Building a tree?
by michael rice 11 Jun '09

11 Jun '09

Here's a function from Data.Tree: unfoldTree :: (b -> (a, [b])) -> b -> Tree a Build a tree from a seed value Could someone please give me a brief example of usage. Michael

3 3

Hac phi accommodation: register by June 15 for reduced rate!
by Brent Yorgey 11 Jun '09

11 Jun '09

Hi all, This is a quick reminder for people interested in attending Hac phi who have not yet reserved a hotel room: if you'd like to reserve a room at Club Quarters at the reduced rate ($114/night single, $129/night double), we ask that you send a note to Daniel Wagner (daniel(a)wagner-home.com) by this Monday, June 15th. To register, or for more infomation about Hac phi, visit the wiki page [1]. Thanks, and we look forward to seeing you at the hackathon! The Hac phi Team [1] http://haskell.org/haskellwiki/Hac_%CF%86

1 0

Weird and entirely random problem...
by Jeff Heard 11 Jun '09

11 Jun '09

The code that causes it is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5731#a5731 This is the strangest thing. Occasionally, using nothing but gets and puts and frees on a non-full Cache will result in this: Cache { store = fromList [("(\"icons/addBookmark.png\",False)",TextureObject {textureID = 4}) ,("(\"icons/addCircle.png\",False)",TextureObject {textureID = 1}) ,("(\"icons/addContent.png\",False)",TextureObject {textureID = 2}) ,("(\"icons/addElsewhereLink.png\",False)",TextureObject {textureID = 3})] , times = fromList [(61314,"(\"<span font_desc='sans 8'>294.0</span>\",AlignLeft,Nothing,WrapWholeWords,False,0.0,0.0)") ,(61316,"(\"icons/addBookmark.png\",False)"),(61318,"(\"icons/addCircle.png\",False)") ,(61320,"(\"icons/addContent.png\",False)"),(61322,"(\"icons/addElsewhereLink.png\",False)")] , now = 61323 , maxsize = 1024768000 , size = 4 , decimation = 0 } Sometimes the problem is self-correcting. Sometimes it is most certainly not. But I don't understand how my code can possibly allow for this.

2 2

Convert IO Int to Int
by ptrash 10 Jun '09

10 Jun '09

Hi, I am using the System.Random method randomRIO. How can I convert its output to an Int? Thanks... -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23940249.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

16 23

How To Make It Faster?
by paravinicius＠yahoo.com.br 10 Jun '09

10 Jun '09

Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

2 1

How To Make It Faster?
by Diego Souza 10 Jun '09

10 Jun '09

Hi, I come up with the following solution for this easy spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

2 1

nubBy seems broken in recent GHCs
by Cale Gibbard 10 Jun '09

10 Jun '09

According to the Report: nubBy :: (a -> a -> Bool) -> [a] -> [a] nubBy eq [] = [] nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs) Hence, we should have that nubBy (<) (1:2:[]) = 1 : nubBy (<) (filter (\y -> not (1 < y)) (2:[])) = 1 : nubBy (<) [] = 1 : [] However in ghc-6.10.3: Prelude Data.List> nubBy (<) [1,2] [1,2] The order of the parameters to the function which is passed to nubBy is *important* since the function might not be an equivalence relation. nubBy is more generally useful for sieving even when the relation is not symmetric. groupBy, for a similar reason, has applications for grouping beyond those provided by equivalence relations, and I think we should be able to rely on its behaviour. Moreover, I contend that the Report's order is more sensible, since the parameters to the relation stay in the left-to-right order in which they occurred in the list. It would be good if this could get fixed for 6.10.4. - Cale PS: There is actually another implementation of groupBy which would *also* be useful to have, but which is exactly the same for equivalence relations as groupBy, and it compares adjacent elements rather than the first element of a group with successive ones. (groupByAdjacent or something would be a reasonable name.) An implementation of it can be found here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5595

4 4

help with a question
by haonan21 10 Jun '09

10 Jun '09

I'm very new to haskell hugs and would appreciate it if someone could help me out here. I've been giving 2 questions. 1.) A and B are two sets of integers. Implement a function to obtain the integers that belong to both sets. Test your function fully. 2.) Define and test a function f, which, if A is a set of {x, y, z} then f(A) = {{},{x}, {y}, {z}, {x, y}, {x,z}, {y,z}, {x, y, z}} Manage to get the first one. interset::[Int]->[Int]->[Int] interset x [] = [] interset [] y = [] interset x@(xs:xt) y@(ys:yt) = if xs == ys then as:(interset at yt) else interset at y Totally have no clue for the 2nd question. could someone help me out ? Many thanks! -- View this message in context: http://www.nabble.com/help-with-a-question-tp23946402p23946402.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

I love purity, but it's killing me.
by Tom Hawkins 10 Jun '09

10 Jun '09

I've been programming with Haskell for a few years and love it. One of my favorite applications of Haskell is using for domain specific languages. However, after designing a handful of DSLs, I continue to hit what appears to be a fundamental hurdle -- or at least I have yet to find an adequate solution. My DSLs invariably define a datatype to capture expressions; something like this: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Using the datatype Expression, it is easy to mass a collections of functions to help assemble complex expressions, which leads to very concise programs in the DSL. The problem comes when I want to generate efficient code from an Expression (ie. to C or some other target language). The method I use invovles converting the tree of subexpressions into an acyclic graphic to eliminate common subexpressions. The nodes are then topologically ordered and assigned an instruction, or statement for each node. For example: let a = Add (Constant 10) (Variable "i1") b = Sub (Variable "i2") (Constant 2) c = Add a b would compile to a C program that may look like this: a = 10 + i1; b = i2 - 2; c = a + b; The process of converting an expression tree to a graph uses either Eq or Ord (either derived or a custom instance) to search and build a set of unique nodes to be ordered for execution. In this case "a", then "b", then "c". The problem is expressions often have shared, equivalent subnodes, which dramatically grows the size of the tree. For example: let d = Add c c e = Add d d -- "e" now as 16 leaf nodes. As these trees grow in size, the equality comparison in graph construction quickly becomes the bottleneck for DSL compilation. What's worse, the phase transition from tractable to intractable is very sharp. In one of my DSL programs, I made a seemingly small change, and compilation time went from milliseconds to not-in-a-million-years. Prior to Haskell, I wrote a few DSLs in OCaml. I didn't have this problem in OCaml because each "let" expression was mutable, and I could use the physical equality operator to perform fast comparisons. Unfortunately, I have grown to love Haskell's type system and its lack of side effects, and could never go back. Is there anything that can be done to dramatically speed up comparisons, or is there a better approach I can take to extract common subexpressions? I should point out I have an opportunity to get Haskell on a real industrial application. But if I can't solve this problem, I may have to resort to far less eloquent languages. :-( Thanks for any and all help. -Tom

17 36

Re: [Haskell-cafe] please comment on my parser, can I do this cleaner?
by Thomas Hartman 10 Jun '09

10 Jun '09

Thanks. It seems my original parser also works against FOO,BAR,BAZ if you only modify atom = string "," <|> ( many1 $ noneOf "()<>," ) -- add , Indeed, what to call the "thingies" in a parser is a source of some personal consternation. What is a token, what is an atom, what is an expr? It all seems to be somewhat ad hoc. > 2009/6/9 Daniel Fischer <daniel.is.fischer(a)web.de>: >> Am Dienstag 09 Juni 2009 20:29:09 schrieb Thomas Hartman: >>> All I want to do is split on commas, but not the commas inside () or <> >>> tags. >>> >>> I have been wanting to master parsec for a long time and this simple >>> exercise looked like a good place to start. >>> >>> The code below does the right thing. Am I missing any tricks to make >>> this simpler/neater? >>> >>> Thanks, thomas. >>> >>> thartman@ubuntu:~/perlArena>cat splitEm. >>> splitEm.hs splitEm.hs~ splitEm.pl splitEm.pl~ >>> thartman@ubuntu:~/perlArena>cat splitEm.hs >>> {-# LANGUAGE ScopedTypeVariables #-} >>> import Text.ParserCombinators.Parsec >>> import Text.ParserCombinators.Parsec.Char >>> import Text.PrettyPrint (vcat, render, text) >>> import Data.List.Split hiding (sepBy, chunk) >>> import Text.ParserCombinators.Parsec.Token >>> >>> import Debug.Trace >>> import Debug.Trace.Helpers >>> >>> -- this works, but is there a neater/cleaner way? >>> main = ripInputsXs (toEof splitter) "splitter" [ goodS, badS ] >>> >>> -- I need a way to split on commas, but not the commas inside '<>' or >>> '()' characters >>> goodS = "<*2>FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >>> badS = "<*2)FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >>> -- the first < matches a ), so reject this >>> >>> >>> splitter = do >>> chunks :: [String] <- toEof (many chunk) >>> let pieces = map concat $ splitOn [","] chunks >>> return pieces -- chunks >>> where >>> atom = string "," >>> <|> ( many1 $ noneOf "()<>" ) >>> chunk = parenExpr <|> atom >> >> I think that does not do what you want. >> >> For input "FOO,BAR,BAZ", chunks is ["FOO,BAR,BAZ"], that won't be split; as far as I can >> see, it splits only on commas directly following a parenExpr (or at the beginning of the >> input or directly following another splitting comma). >> >>> parenExpr :: GenParser Char st [Char] >>> parenExpr = let paren p = betweenInc (char '(' ) (char ')' ) p >>> <|> betweenInc (char '<' ) (char '>' ) >>> p >>> in paren $ option "" $ do ps <- many1 $ parenExpr <|> atom >>> return . concat $ ps >>> >>> betweenInc o' c' p' = do >>> o <- o' >>> p <- p' >>> c <- c' >>> return $ [o] ++ p ++ [c] >>> >>> toEof p' = do >>> r <- p' >>> eof >>> return r >>> >>> >>> >>> >>> >>> >>> ripInputs prs prsName xs = mapM_ (putStrLn . show . parse prs prsName ) xs >>> ripInputsXs prs prsName xs = mapM_ (putStrLn . showXs . parse prs prsName ) >>> xs where showXs v = case v of >>> Left e -> show e >>> Right xs -> render . vcat . map text $ xs >> >> I can offer (sorry for the names, and I don't know if what that does is really what you >> want): >> >> >> keepSepBy :: Parser a -> Parser a -> Parser [a] >> keepSepBy p sep = (do >> r <- p >> (do s <- sep >> xs <- keepSepBy p sep >> return (r:s:xs)) <|> return [r]) >> <|> return [] >> >> twain :: Parser a -> Parser a -> Parser [a] -> Parser [a] >> twain open close list = do >> o <- open >> l <- list >> c <- close >> return (o:l++[c]) >> >> comma :: Parser String >> comma = string "," >> >> simpleChar :: Parser Char >> simpleChar = noneOf "<>()," >> >> suite :: Parser String >> suite = many1 simpleChar >> >> atom :: Parser String >> atom = fmap concat $ many1 (parenExp <|> suite) >> >> parenGroup :: Parser String >> parenGroup = fmap concat $ keepSepBy atom comma >> >> parenExp :: Parser String >> parenExp = twain (char '<') (char '>') parenGroup >> <|> twain (char '(') (char ')') parenGroup >> >> chunks :: Parser [String] >> chunks = sepBy atom comma >> >> splitter = do >> cs <- chunks >> eof >> return cs >> >> goodS = "<*2>FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >> badS = "<*2)FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >> >> goodRes = parse splitter "splitter" goodS >> badRes = parse splitter "splitter" badS >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >

1 0

Incremental XML parsing with namespaces?
by John Millikin 10 Jun '09

10 Jun '09

I'm trying to convert an XML document, incrementally, into a sequence of XML events. A simple example XML document: <doc xmlns="org:myproject:mainns" xmlns:x="org:myproject:otherns"> <title>Doc title</title> <x:ref>abc1234</x:ref> <html xmlns="http://www.w3.org/1999/xhtml"><body>Hello world!</body></html> </doc> The document can be very large, and arrives in chunks over a socket, so I need to be able to "feed" the text data into a parser and receive a list of XML events per chunk. Chunks can be separated in time by intervals of several minutes to an hour, so pausing processing for the arrival of the entire document is not an option. The type signatures would be something like: type Namespace = String type LocalName = String data Attribute = Attribute Namespace LocalName String data XMLEvent = EventElementBegin Namespace LocalName [Attribute] | EventElementEnd Namespace LocalName | EventContent String | EventError String parse :: Parser -> String -> (Parser, [XMLEvent]) I've looked at HaXml, HXT, and hexpat, and unless I'm missing something, none of them can achieve this: + HaXml and hexpat seem to disregard namespaces entirely -- that is, the root element is parsed to "doc" instead of ("org:myproject:mainns", "doc"), and the second child is "x:ref" instead of ("org:myproject:otherns", "ref"). Obviously, this makes parsing mixed-namespace documents effectively impossible. I found an email from 2004[1] that mentions a "filter" for namespace support in HaXml, but no further information and no working code. + HXT looks promising, because I see explicit mention in the documentation of recording and propagating namespaces. However, I can't figure out if there's an incremental mode. A page on the wiki[2] suggests that SAX is supported in the "html tag soup" parser, but I want incremental parsing of *valid* documents. If incremental parsing is supported by the standard "arrow" interface, I don't see any obvious way to pull events out into a list -- I'm a Haskell newbie, and still haven't quite figured out monads yet, let alone Arrows. Are there any libraries that support namespace-aware incremental parsing? [1] http://www.haskell.org/pipermail/haskell-cafe/2004-June/006252.html [2] http://www.haskell.org/haskellwiki/HXT/Conversion_of_Haskell_data_from/to_X…

5 8

FlexibleContexts and FlexibleInstances
by Niklas Broberg 10 Jun '09

10 Jun '09

Dear all, This post is partly a gripe about how poor the formal documentation for various GHC extensions is, partly a gripe about how GHC blurs the lines between syntactic and type-level issues as well as between various extensions, and partly a gripe about how the Haskell 98 report is sometimes similarly blurred where syntax is concerned (or not). All these things make the life of a poor parser implementor quite miserable at times. All in good jest of course, but with an edge of truth, especially regarding (lack of) formal documentation. The issue at hand which has caused my frustration is the FlexibleContexts [1] and FlexibleInstances [2] extensions, which lift restrictions imposed by Haskell 98 on the forms of contexts and instances that may be defined. Great extensions both of them - but what do they do, really really? The following toy program requires MultiParamTypeClasses OR FlexibleContexts in order to be accepted by GHC(i): > f :: (T a b) => a -> Int > f _ = 0 This of course assumes that we import the definition of T, we *must* have MultiParamTypeClasses enabled if we want to declare T. Both extensions thus enable classes with more than one argument to appear in contexts. Changing the program to > f :: (T a ()) => a -> Int > f _ = 0 i.e. changing the second argument to T to () instead, means we now *must* have FlexibleInstances, in order to allow the non-tyvar argument. This is nothing surprising, this is what FlexibleInstances are supposed to do. But the question is, is this a syntactic issue or a typing issue? In GHC proper this doesn't really matter much, as long as it is caught *somewhere* then all is dandy. GHC's parser lets everything pass, and it's the type checker that balks at this program. But for someone like me with *only* a parser, this is a question that needs a clear answer. Looking at the online report, the productions regarding contexts are context -> class | ( class1 , ... , classn ) (n>=0) class -> qtycls tyvar | qtycls ( tyvar atype1 ... atypen ) (n>=1) qtycls -> [ modid . ] tycls tycls -> conid tyvar -> varid Ok, so clearly the () is a syntactic extension enabled by FlexibleContexts, as it is not a tyvar nor a tyvar applied to a sequence of types. So this is something that a parser should handle. FlexibleContexts also enables similar parses of contexts in other places, for instance in class declarations, for which the Haskell 98 report says topdecl -> class [scontext =>] tycls tyvar [where cdecls] scontext -> simpleclass | ( simpleclass1 , ... , simpleclassn ) (n>=0) simpleclass -> qtycls tyvar The difference here is that the simpleclass doesn't allow the tyvar applied to a sequence of types bit. FlexibleContexts lifts that restriction too, so there should be no difference between the two kinds of contexts. So the new formal productions for flexible contexts should be something like fcontext -> fclass | ( fclass1 , ... , fclassn ) (n>=0) fclass -> qtycls type1 ... typen (n>=1) topdecl -> data [fcontext =>] simpletype = constrs [deriving] | newtype [fcontext =>] simpletype = newconstr [deriving] | class [fcontext =>] tycls tyvar [where cdecls] | instance [fcontext =>] qtycls inst [where idecls] gendecl -> vars :: [fcontext =>] type Does this seem correct? Now let's turn to FlexibleInstances, which similarly lifts restrictions, only to instance declarations instead of contexts. The Haskell 98 report says on instance declarations: topdecl -> instance [scontext =>] qtycls inst [where idecls] inst -> gtycon | ( gtycon tyvar1 ... tyvark ) (k>=0, tyvars distinct) | ( tyvar1 , ... , tyvark ) (k>=2, tyvars distinct) | [ tyvar ] | ( tyvar1 -> tyvar2 ) (tyvar1 and tyvar2 distinct) Note the re-appearance of scontext, which is the same as above. The instance head must be a type constructor, possibly applied to a number of type variables, or one of three built-in syntactic cases. This is where I consider the Haskell 98 report blurry - the fact that the tyvars must be distinct, is that truly a syntactic issue? It might be, it's certainly something that could be checked syntactically. But when you take into account that with the proper extensions, they no longer need to be distinct, at what level would we expect such a check to happen? My gut feeling is that this check for distinctness is something that a type checker might do better than a parser, though it's not clear cut by any means. But since I don't do any other kind of name resolution or checking in my parser even if it would be possible (e.g. multiple declarations of the same symbol), I would find it a bit anomalous to check this too. Turning on FlexibleInstances, we shouldn't need to follow any of the above restrictions on inst. In other words, the flexible production should simply be something like finst -> type Right? Now, FlexibleInstances *also* lifts the restriction on contexts, just like FlexibleContexts - but *only* for the contexts of instance declarations. This may seem like a reasonable thing, but it certainly gives me some headaches. It means I could not treat the contexts uniformly, but would need to have separate syntactic categories (or rather post-parse checks) that look different between instance contexts and other contexts (including class). So with FlexibleInstances on, there are *three* different kinds of contexts allowed: scontext for class declaration, fcontext for instance declarations, and context for all other uses of contexts (type signatures, data/newtype declarations). Just a small headache, since I already apparently needed two categories from Haskell 98, but still. I'm not sure I find it reasonable, that flexible instances are enabled just for instance declarations but not elsewhere, but I'm sure a lot of thought was given to that. If it was up to *me* though, I would leave the flexible contexts with FlexibleContexts entirely, which means you would have to use both flags if you wanted both in your instance declarations. Would that be a bad thing? Separation of concern seems desirable to me (and no, I'm not saying that just because it would be easier to implement in the parser)... At any rate, to make a long rant short: * Are my interpretations of the lifted restrictions by FlexibleContexts and FlexibleInstances correct? * Is it reasonable that the issue of checking that tyvars are distinct should not be considered syntactic? * Would it also be reasonable to make the separation of concern between FlexibleContexts and FlexibleInstances more clean? Thanks for reading, and please give me input! Cheers, /Niklas [1] http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensio… [2] http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensio…

1 0

How to improve below code?
by Andy Stewart 10 Jun '09

10 Jun '09

Hi all, I have below source code, i use Dynamic for `pageBuffer`. In implement of function `pageClone`, after `case pt of`, i need write like this, and this code looks ugly, if `PageTyep` have 100 type, i need write those ugly code 100 times. case pt of TStringBuffer -> pageBufferClone (x :: StringBuffer) TImageBuffer -> pageBufferClone (x :: ImageBuffer) TVideoBuffer -> pageBufferClone (x :: TVideoBuffer) TMixBuffer -> pageBufferClone (x :: TMixBuffer) So have a better solution to avoid write above ugly code? Someone suggestion me use GADTs instead, but i don't know how to write correct GADTs code replace current version, if GADTs is best way, someone can explain it detail? It's better if someone give me demo code. ------------------------------> Source Code start <------------------------------ data PageType = TStringBuffer | TImageBuffer | TVideoBuffer | TMixBuffer deriving (Eq, Show, Read) data Page = Page {pageName :: IORef String ,pageId :: Int ,pageType :: PageType ,pageBuffer :: Dynamic ,pageBox :: VBox } class PageBuffer a where pageBufferClone :: a -> IO (Dynamic, VBox) -- | Page clone interface. pageClone :: Page -> IO Page pageClone page = do -- Get common information for clone page. name <- pageGetName page let id = pageId page pt = pageType page pb = pageBuffer page -- Get clone information for dynamic interface. (pBuffer, pBox) <- case fromDynamic pb of Just x -> case pt of TStringBuffer -> pageBufferClone (x :: StringBuffer) TImageBuffer -> pageBufferClone (x :: ImageBuffer) TVideoBuffer -> pageBufferClone (x :: TVideoBuffer) TMixBuffer -> pageBufferClone (x :: TMixBuffer) Nothing -> pageCloneEmpty -- Return clone page. pageNewInternal name id pt pBuffer pBox ------------------------------> Source Code end <------------------------------ Thanks! -- Andy

3 2

please comment on my parser, can I do this cleaner?
by Thomas Hartman 10 Jun '09

10 Jun '09

All I want to do is split on commas, but not the commas inside () or <> tags. I have been wanting to master parsec for a long time and this simple exercise looked like a good place to start. The code below does the right thing. Am I missing any tricks to make this simpler/neater? Thanks, thomas. thartman@ubuntu:~/perlArena>cat splitEm. splitEm.hs splitEm.hs~ splitEm.pl splitEm.pl~ thartman@ubuntu:~/perlArena>cat splitEm.hs {-# LANGUAGE ScopedTypeVariables #-} import Text.ParserCombinators.Parsec import Text.ParserCombinators.Parsec.Char import Text.PrettyPrint (vcat, render, text) import Data.List.Split hiding (sepBy, chunk) import Text.ParserCombinators.Parsec.Token import Debug.Trace import Debug.Trace.Helpers -- this works, but is there a neater/cleaner way? main = ripInputsXs (toEof splitter) "splitter" [ goodS, badS ] -- I need a way to split on commas, but not the commas inside '<>' or '()' characters goodS = "<*2>FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" badS = "<*2)FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" -- the first < matches a ), so reject this splitter = do chunks :: [String] <- toEof (many chunk) let pieces = map concat $ splitOn [","] chunks return pieces -- chunks where atom = string "," <|> ( many1 $ noneOf "()<>" ) chunk = parenExpr <|> atom parenExpr :: GenParser Char st [Char] parenExpr = let paren p = betweenInc (char '(' ) (char ')' ) p <|> betweenInc (char '<' ) (char '>' ) p in paren $ option "" $ do ps <- many1 $ parenExpr <|> atom return . concat $ ps betweenInc o' c' p' = do o <- o' p <- p' c <- c' return $ [o] ++ p ++ [c] toEof p' = do r <- p' eof return r ripInputs prs prsName xs = mapM_ (putStrLn . show . parse prs prsName ) xs ripInputsXs prs prsName xs = mapM_ (putStrLn . showXs . parse prs prsName ) xs where showXs v = case v of Left e -> show e Right xs -> render . vcat . map text $ xs

2 1

Re: [Haskell-cafe] Applying Data.Map
by michael rice 09 Jun '09

09 Jun '09

In the import statements, it wasn't clear to me that I could import types as well as functions, and Map is a type. All clear now. Thanks. Michael --- On Tue, 6/9/09, Thomas ten Cate <ttencate(a)gmail.com> wrote: From: Thomas ten Cate <ttencate(a)gmail.com> Subject: Re: [Haskell-cafe] Applying Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Tuesday, June 9, 2009, 9:40 AM On Tue, Jun 9, 2009 at 15:23, michael rice<nowgate(a)yahoo.com> wrote: > import Data.Map (Map) (fromList,!) ??? > import qualified Data.Map as Map (fromList,!) ??? Because ! is an operator, you need to enclose it in parentheses. Also, the (Map) in the import is already the list of things you are importing; you can just add to that. So do the following: Import these without qualification: > import Data.Map (Map, fromList, (!)) Import everything else (actually including Map, fromList and (!)) with qualification "Map": > import qualified Data.Map as Map Cheers, Thomas

1 0

Re: [Haskell-cafe] Applying Data.Map
by michael rice 09 Jun '09

09 Jun '09

Hi Toby, Thanks for the helpful comments. I'd gotten used to arithmetic operator sections (+2), (*2), etc. but hadn't picked up on the generality of using them with *any* infix function. I can also see the benefit of using List.Group. However, I'm uncertain about how to import just fromList and ! from with the imports I'm using import Data.Map (Map) (fromList,!) ??? import qualified Data.Map as Map (fromList,!) ??? Michael --- On Mon, 6/8/09, Toby Hutton <toby.hutton(a)gmail.com> wrote: From: Toby Hutton <toby.hutton(a)gmail.com> Subject: Re: [Haskell-cafe] Applying Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 8:57 PM Although in this example using Data.Map is overkill, if the alphabet was very large then Data.Map probably would be the way to go. In that case I'd use: map head . group . sort instead of nub . sort since it's noticeably quicker for large lists. This is because nub needs to preserve the order of input, removing redundancies, but you're sorting it anyway. Also, in map (\c -> m Map.! c) s you can use the 'section' (m Map.!) instead. e.g., map (m Map.!) s The Map.! is ugly though. As you're only using fromList and (!) from Data.Map, I'd just import those explicitly since they don't clash with Prelude. Then you'd have map (m !) s Toby. On Tue, Jun 9, 2009 at 4:59 AM, michael rice <nowgate(a)yahoo.com> wrote: I wrote a Haskell solution for the Prolog problem stated below. I had written a function SQUISH before discovering that NUB does the same thing. While the solution works, I thought maybe I could apply some functions in the Data.Map module, and so wrote a second version of SERIALIZE, one no longer needing TRANSLATE. Using the Data.Map module is probably overkill for this particular problem, but wanted to familiarize myself with Map type. Suggestions welcome. Prolog code also included below for those interested. Michael =========== {- From "Prolog By Example", Coelho, Cotta, Problem 42, pg. 63 Verbal statement: Generate a list of serial numbers for the items of a given list, the members of which are to be numbered in alphabetical order. For example, the list [p,r,o,l,o,g] must generate [4,5,3,2,3,1] -} {- Prelude> :l serialize [1 of 1] Compiling Main ( serialize.hs, interpreted ) Ok, modules loaded: Main. *Main> serialize "prolog" [4,5,3,2,3,1] *Main> -} ===========Haskell code========== import Data.Char import Data.List import Data.Map (Map) import qualified Data.Map as Map {- translate :: [Char] -> [(Char,Int)] -> [Int] translate [] _ = [] translate (x:xs) m = (fromJust (lookup x m)) : (translate xs m ) -} {- serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] in translate s (zip c n) -} serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] m = Map.fromList $ zip c n in map (\c -> m Map.! c) s ============Prolog code============ serialize(L,R) :- pairlists(L,R,A),arrange(A,T), numbered(T,1,N). ? <- typo? pairlists([X|L],[Y|R],[pair(X,Y)|A]) :- pairlist(L,R,A). pairlists([],[],[]). arrange([X|L],tree(T1,X,T2)) :- partition(L,X,L1,L2), arrange(L1,T1), arrange(L2,T2). arrange([],_). partition([X|L],X,L1,L2) :- partition(L,X,L1,L2). partition([X|L],Y,[X|L1],L2) :- before(X,Y), partition(L,Y,L1,L2). partition([X|L],Y,L1,[X|L2]) :- before(Y,X), partition(L,Y,L1,L2). partition([],_,[],[]). before(pair(X1,Y1),pair(X2,Y2)) :- X1<X2. numbered(tree(T1,pair(X,N1),T2),N0,N) :- numbered(T1,N0,N1), N2 is N1+1, numbered(T2,N2,N). numbered(void,N,N). ============Prolog examples======== Execution: ?- serialize([p,r,o,l,o,g]). [4,5,3,2,3,1] ?- serialize ([i,n,t,.,a,r,t,i,f,i,c,i,a,l]). [5,7,9,1,2,8,9,5,4,5,3,5,2,6] _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Combine to List to a new List
by ptrash 09 Jun '09

09 Jun '09

Hi, I have the following two lists: a = [1,2,3] b = ["A","B","C"] I want a combination of the to lists: c = [(1,"A"), (2, "B"), (3, "C")] How can I do this? I have tried c = [(x,y) | x <- a, y <- b] But this just returns me a list with every possible combination of the 2 lists. Thanks... -- View this message in context: http://www.nabble.com/Combine-to-List-to-a-new-List-tp23942440p23942440.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 4

A generics question
by Henry Laxen 09 Jun '09

09 Jun '09

Lets suppose I have a file that has encoded things of different types as integers, and now I would like to convert them back into specific instances of a data type. For example, I have a file that contains 1,1,2,3 and I would like the output to be [Red, Red, Green, Blue]. I also would like to do this generically, so that if I wanted to convert the same list of integers into say Sizes, I would get [Small, Small, Medium, Large] Now please have a look at the following code: {-# LANGUAGE DeriveDataTypeable #-} import Data.Generics data Color = Red | Green | Blue deriving (Eq,Ord,Read,Show,Typeable,Data) data Size = Small | Mediaum | Large deriving (Eq,Ord,Read,Show,Typeable,Data) g = Green c = undefined :: Color s = undefined :: Size t = do print $ toConstr g -- Green print $ dataTypeOf c -- DataType {tycon = "Main.Color", datarep = AlgRep [Red,Green,Blue]} convert :: (Data a, Data b) =Int -a -b convert i x = let c = dataTypeConstrs (dataTypeOf x) !! (i-1) in fromConstr c I would like to be able to say: x = convert 1 c and have it assign Red to x then I would like to say: y = convert 1 s and have it assign Small to y, however, when I try that I get: Ambiguous type variable `b' in the constraint: `Data b' arising from a use of `convert' at <interactive>:1:8-18 Probable fix: add a type signature that fixes these type variable(s) Of course if I say x :: Color = convert 1 c, it works, but I would like to avoid that if possible, as all of the information is already contained in the parameter c. Is there any way to do this? Thanks in advance for your wise counsel. Best wishes, Henry Laxen

4 5

Unification for rank-N types
by Vladimir Reshetnikov 09 Jun '09

09 Jun '09

Hi, I have the following code: ------------------------------------------------------- {-# LANGUAGE RankNTypes #-} f :: ((forall a. a -> a) -> b) -> b f x = x id g :: (forall c. Eq c => [c] -> [c]) -> ([Bool],[Int]) g y = (y [True], y [1]) h :: ([Bool],[Int]) h = f g ------------------------------------------------------- GHC rejects it: Couldn't match expected type `forall a. a -> a' against inferred type `forall c. (Eq c) => [c] -> [c]' Expected type: forall a. a -> a Inferred type: forall c. (Eq c) => [c] -> [c] In the first argument of `f', namely `g' In the expression: f g But, intuitively, this code is type-safe, and actually I can convince the typechecker in it with the following workaround: ------------------------------------------------------- h :: ([Bool],[Int]) h = let g' = (\(x :: forall a. a -> a) -> g x) in f g' ------------------------------------------------------- So, is the current behavior of GHC correct ot it is a bug? How unification for rank-N types should proceed? Thanks, Vladimir

1 1

Dutch HUG meeting tonight in Amsterdam
by Chris Eidhof 09 Jun '09

09 Jun '09

Hi everyone, Tonight there will be another meeting of the Dutch Haskell Users' Group! This time we'll meet in Amsterdam, in the library. On the wiki [1] you can find the details of how to reach it. We'll be at the top floor and shouldn't be hard to recognize. The meeting is set to begin at 19:30. Everybody's welcome, from beginners to advanced haskellers. Even if you never programmed in Haskell before it'll probably be a lot of fun. See you tonight! There are a lot of international people joining, so no knowledge of Dutch is necessary. If you're joining, also be sure to subscribe to our mailinglist [2]. See you tonight! -chris [1]: http://www.haskell.org/haskellwiki/Dutch_HUG [2]: http://groups.google.com/group/dutch-hug

1 0

How to compile base?
by Henk-Jan van Tuyl 09 Jun '09

09 Jun '09

L.S., I tried to compile base-4.0.0.0 (on Windows XP) as follows: [...]\base\4.0.0.0>runhaskell Setup configure <command line>: module `Prelude' is not loaded It seems that Base needs another way to compile, how? -- Regards, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ --

2 1

Deprecated packages on Hackage?
by Erik de Castro Lopo 09 Jun '09

09 Jun '09

Hi all, Is there a way to list all the deprecated packages on hackage? For instance I found this: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/control-timeout-… via a google search but its not listed on the main hackage packages page. However, there are other packages which are marked DEPRECATED in their description strings. Finally, if a package is deprecated it might be usefult to have a reason as well so the hackage entry might say: Deprecated : true (replaced by package XXX) or Deprecated : true (needs maintainer) Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

3 3

Re: Question on rank-N polymorphism
by oleg＠okmij.org 09 Jun '09

09 Jun '09

Ryan Ingram discussed a question of writing > fs f g = (f fst, g snd) so that fs ($ (1, "2")) type checks. This is not that difficult: > {-# LANGUAGE RankNTypes, MultiParamTypeClasses -#} > {-# LANGUAGE FunctionalDependencies, FlexibleInstances #-} > > class Apply f x y | f x -> y where > apply :: f -> x -> y > > instance Apply (x->y) x y where > apply = ($) > > data Fst = Fst > data Snd = Snd > > instance Apply Fst (x,y) x where > apply _ = fst > > instance Apply Snd (x,y) y where > apply _ = snd The function in question: > fs3 f = (apply f Fst, apply f Snd) -- One of Wouter Swierstra's examples -- examples = (fs id, fs repeat, fs (\x -> [x]), fs ((,)id)) > data Id a = Id > instance Apply (Id a) Fst ((a,a) -> a) where > apply _ _ = fst > instance Apply (Id a) Snd ((a,a) -> a) where > apply _ _ = snd > ex1 = fs3 Id Now, Ryan's main example > newtype Pair a b = Pair (forall w. (((a,b) -> w) -> w)) > instance Apply (Pair a b) Fst a where > apply (Pair f) _ = f fst > instance Apply (Pair a b) Snd b where > apply (Pair f) _ = f snd > ex4 = fs3 (Pair ($ (1, "2"))) > -- (1,"2") Incidentally, a different variation of this example is discussed in http://okmij.org/ftp/Computation/extra-polymorphism.html Indeed, such a selection from a pair occurs quite often...

1 0

ANNOUNCE: StrictBench 0.1 - Benchmarking code through strict evaluation
by Niemeijer, R.A. 09 Jun '09

09 Jun '09

Hello everyone, In the last month or so, I've found myself using the following snippet a lot: import Control.Parallel.Strategies import Test.BenchPress bench 1 . print . rnf This snippet fully evaluates a value and prints how long it took to do so. I regularly use it to see where the bottlenecks lie in my algorithms. It has the minor annoyance, however, that it prints a lot of information (min, max, mean, median, percentiles) that is all identical, because I only run it once. The reason I only run it once is that I'm typically evaluating a pure value, which means that any subsequent attempts to benchmark the evaluation time will take no time at all, since it has already been evaluated. To solve this, I decided to write a small library to make this process easier and only print the time taken once. The result is StrictBench, which can be found at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/StrictBench. A short example: import Test.StrictBench main = bench [1..10000000 :: Integer] This code would give 2890.625 ms as output. For the rest of the documentation I refer you to the Hackage page. Regards, Remco Niemeijer

6 6

Applying Data.Map
by michael rice 09 Jun '09

09 Jun '09

I wrote a Haskell solution for the Prolog problem stated below. I had written a function SQUISH before discovering that NUB does the same thing. While the solution works, I thought maybe I could apply some functions in the Data.Map module, and so wrote a second version of SERIALIZE, one no longer needing TRANSLATE. Using the Data.Map module is probably overkill for this particular problem, but wanted to familiarize myself with Map type. Suggestions welcome. Prolog code also included below for those interested. Michael =========== {- From "Prolog By Example", Coelho, Cotta, Problem 42, pg. 63 Verbal statement: Generate a list of serial numbers for the items of a given list, the members of which are to be numbered in alphabetical order. For example, the list [p,r,o,l,o,g] must generate [4,5,3,2,3,1] -} {- Prelude> :l serialize [1 of 1] Compiling Main ( serialize.hs, interpreted ) Ok, modules loaded: Main. *Main> serialize "prolog" [4,5,3,2,3,1] *Main> -} ===========Haskell code========== import Data.Char import Data.List import Data.Map (Map) import qualified Data.Map as Map {- translate :: [Char] -> [(Char,Int)] -> [Int] translate [] _ = [] translate (x:xs) m = (fromJust (lookup x m)) : (translate xs m ) -} {- serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] in translate s (zip c n) -} serialize :: [Char] -> [Int] serialize s = let c = nub $ sort s n = [1..(length c)] m = Map.fromList $ zip c n in map (\c -> m Map.! c) s ============Prolog code============ serialize(L,R) :- pairlists(L,R,A),arrange(A,T), numbered(T,1,N). ? <- typo? pairlists([X|L],[Y|R],[pair(X,Y)|A]) :- pairlist(L,R,A). pairlists([],[],[]). arrange([X|L],tree(T1,X,T2)) :- partition(L,X,L1,L2), arrange(L1,T1), arrange(L2,T2). arrange([],_). partition([X|L],X,L1,L2) :- partition(L,X,L1,L2). partition([X|L],Y,[X|L1],L2) :- before(X,Y), partition(L,Y,L1,L2). partition([X|L],Y,L1,[X|L2]) :- before(Y,X), partition(L,Y,L1,L2). partition([],_,[],[]). before(pair(X1,Y1),pair(X2,Y2)) :- X1<X2. numbered(tree(T1,pair(X,N1),T2),N0,N) :- numbered(T1,N0,N1), N2 is N1+1, numbered(T2,N2,N). numbered(void,N,N). ============Prolog examples======== Execution: ?- serialize([p,r,o,l,o,g]). [4,5,3,2,3,1] ?- serialize ([i,n,t,.,a,r,t,i,f,i,c,i,a,l]). [5,7,9,1,2,8,9,5,4,5,3,5,2,6]

2 1

Slow documentation generation on Hackage
by Niemeijer, R.A. 09 Jun '09

09 Jun '09

Hello everyone. Last night I uploaded my first Hackage library with documentation (StrictBench). I learned that it takes somewhere between 2 and 8 hours for the link to the documentation to become active. This is confusing for first-time package authors (I went to #haskell to ask what I had forgotten) and annoying for everyone (Don Stewart submitted it to reddit shorly after I published it, which kind of wastes the time of everyone who checks it out before the documentation is up). Moreover, there seems to be no reason for it; on your own computer haddock takes just (milli)seconds. Hence I wanted to ask if this is a bug or if there is a good technical or social reason for it, and whether there is any way around it. Regards, Remco Niemeijer

7 8

Comonadic composition and the game "Doublets"
by Matthew 09 Jun '09

09 Jun '09

Today, I was working on coding a solver for the game "doublets". It's a word game where you transform the start word into the end word one letter at a time (and the intermediate states must also be valid words). For example, one solution to ("warm", "cold") is ["warm", "ward", "card", "cord", "cold"] So, one of my first goals was to write a function that would generate the possible words a given word could transition to. Here's a simple recursive implementation: transition :: [Char] -> [[Char]] transition [] = [] transition (c:cs) = map (c:) (transition cs) ++ map (:cs) ['a'..'z'] For some reason, I find this formulation to be strangely unsatisfying. It seems to me that this sort of computation -- i.e. modifying each element of a container (but only one at a time) -- should be expressible with some higher order function. In a nutshell, what I'm looking for would be a function, say "each" with this type. each :: (Container c) => (a -> a) -> c a -> c (c a) I'm not particularly sure what Class to substitute for "Container". Comonad seemed like a promising solution initially, and provides the basis for my current implementation of the "doublets" solver. The problem being that cobind (extend) takes a function of type (w a - > a) instead of (a -> a). I suspect that there may be a clever way to write "each" by using liftW in combination with .>> or something like that, but presently, I'm at a loss. Has anyone else encountered this sort of abstraction before. I'd love to hear your ideas about what Classes "each" should support, and how to implement it. Matt

3 3

Re: [Haskell-cafe] Incremental XML parsing with namespaces?
by John Millikin 09 Jun '09

09 Jun '09

On Mon, Jun 8, 2009 at 2:51 PM, wren ng thornton<wren(a)freegeek.org> wrote: > One issue you'll have to deal with is that since output is delivered > on-line, by the time a validity (or well-formedness) error can be recognized > by the parser it'll be "too late". Thus the rest of your code will need to > be able to back out any global changes they've done when an asynchronous > error shows up. > > I'm sure you already knew that, but it's worth highlighting. (I recently > wrote similar code, but in Java. Haven't had the chance/need to do any xml > hacking in Haskell yet.) > This is acceptable -- I've written a small Python application that performs incremental parsing on the data stream, and aborting on first detection of an error is fine.

1 0

com-1.2.3 - problems installing
by Günther Schmidt 09 Jun '09

09 Jun '09

Hi all, I'm trying to install com-1.2.3 on Win XP with ghc-6.10.3 I get this error message: Resolving dependencies... Configuring com-1.2.3... cabal: Missing dependencies on foreign libraries: * Missing header file: include/WideStringSrc.h * Missing C libraries: kernel32, user32, ole32, oleaut32, advapi32 This problem can usually be solved by installing the system packages that provide these libraries (you may need the "-dev" versions). If the libraries are already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where they are. cabal: Error: some packages failed to install: com-1.2.3 failed during the configure step. The exception was: exit: ExitFailure 1

1 0

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 09 Jun '09

09 Jun '09

Thanks, guys. Sounds like Lisp packages. Now I see the functionality of the A or B, etc.: Fewer keystrokes. Michael --- On Mon, 6/8/09, minh thu <noteed(a)gmail.com> wrote: From: minh thu <noteed(a)gmail.com> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: "Jochem Berndsen" <jochem(a)functor.nl>, haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 1:00 PM Hi, > import Blurp bring every thing defined in the Blurp module in scope. So if blah is defined in blurp, > blah will work as expected. > import qualified Blurp as B does the same thing but everything defined in Blurp should be qualified (i.e. prefixed) with B. > B.blah will work, not > blah So your import statement is right but you should write Map.fromList instead of just fromList. The goal is to have multiple identical names from different modules and still be able to use them at the same time, but qualified, for instance lookup is defined in both Data.List and Data.Map. > import qualified Data.List as L > import qualified Data.Map as M > L.lookup > M.lookup The two last lines are unambiguous. Cheers, Thu 2009/6/8 michael rice <nowgate(a)yahoo.com>: > I don't understand your response. I copied the imports from Hoogles Data.Map > page. What should the imports be? > > Michael > > --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: > > From: Jochem Berndsen <jochem(a)functor.nl> > Subject: Re: [Haskell-cafe] Problem with Data.Map > To: "michael rice" <nowgate(a)yahoo.com> > Cc: haskell-cafe(a)haskell.org > Date: Monday, June 8, 2009, 12:45 PM > > michael rice wrote: >> I'm trying to understand Map type for possible use in another problem I'm >> working on, but am stymied right off the bat. >> >> ==========Here's my source: >> >> import Data.Map (Map) >> import qualified Data.Map as Map >> >> *Main> fromList $ zip l1 l2 >> >> <interactive>:1:0: Not in scope: `fromList' > > You imported map "qualified as Map", that means that only 'Map.fromList' > and 'Data.Map.fromList' are in scope, and not 'fromList'. The reason one > normally does it like this is that a lot of function names clash with > the Prelude (on purpose). Normally one uses "qualified as M" or > "qualified as Map" to shorten the notation. > > HTH, > > -- > Jochem Berndsen | jochem(a)functor.nl > GPG: 0xE6FABFAB > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 09 Jun '09

09 Jun '09

Gotcha. Thanks! Also wondering why I need two imports for one module. Michael --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: From: Jochem Berndsen <jochem(a)functor.nl> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 12:52 PM michael rice wrote: > I don't understand your response. I copied the imports from Hoogles Data.Map page. What should the imports be? > > Michael The imports are fine, but instead of 'fromList' you should use 'Map.fromList' or 'Data.Map.fromList'. Regards, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

2 1

Re: [Haskell-cafe] Problem with Data.Map
by michael rice 09 Jun '09

09 Jun '09

I don't understand your response. I copied the imports from Hoogles Data.Map page. What should the imports be? Michael --- On Mon, 6/8/09, Jochem Berndsen <jochem(a)functor.nl> wrote: From: Jochem Berndsen <jochem(a)functor.nl> Subject: Re: [Haskell-cafe] Problem with Data.Map To: "michael rice" <nowgate(a)yahoo.com> Cc: haskell-cafe(a)haskell.org Date: Monday, June 8, 2009, 12:45 PM michael rice wrote: > I'm trying to understand Map type for possible use in another problem I'm working on, but am stymied right off the bat. > > ==========Here's my source: > > import Data.Map (Map) > import qualified Data.Map as Map > > *Main> fromList $ zip l1 l2 > > <interactive>:1:0: Not in scope: `fromList' You imported map "qualified as Map", that means that only 'Map.fromList' and 'Data.Map.fromList' are in scope, and not 'fromList'. The reason one normally does it like this is that a lot of function names clash with the Prelude (on purpose). Normally one uses "qualified as M" or "qualified as Map" to shorten the notation. HTH, -- Jochem Berndsen | jochem(a)functor.nl GPG: 0xE6FABFAB

3 2

Problem with Data.Map
by michael rice 09 Jun '09

09 Jun '09

I'm trying to understand Map type for possible use in another problem I'm working on, but am stymied right off the bat. ==========Here's my source: import Data.Map (Map) import qualified Data.Map as Map l1 = "abc" l2 = [1,2,3] ==========Here's my error: Prelude> :l maptest [1 of 1] Compiling Main ( maptest.hs, interpreted ) Ok, modules loaded: Main. *Main> l1 Loading package syb ... linking ... done. Loading package array-0.2.0.0 ... linking ... done. Loading package containers-0.2.0.0 ... linking ... done. "abc" *Main> l2 [1,2,3] *Main> zip l1 l2 [('a',1),('b',2),('c',3)] *Main> fromList $ zip l1 l2 <interactive>:1:0: Not in scope: `fromList' *Main> =========== Why isn't this working? Michael

2 1

purely functional lazy non-deterministic programming
by Sebastian Fischer 09 Jun '09

09 Jun '09

[crosspost from Haskell-libraries and Curry mailing list] Dear Haskell and Curry programmers, there is now a Haskell library that supports lazy functional-logic programming in Haskell. It is available from http://sebfisch.github.com/explicit-sharing and can be obtained from Hackage using cabal-install. The project page links to tutorials that explain how to use the library and to an ICFP'09 paper (joint work with Oleg Kiselyov and Chung-chieh Shan) that explains the implemented ideas in depth. Have fun! Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

1 0

ANN: alloy-1.0.0 (generic programming)
by Neil Brown 08 Jun '09

08 Jun '09

Hi all, I've just put the first release of the Alloy generic programming library on Hackage [1]. Alloy (née Polyplate) is intended to be a fairly fast blend of several other generics approaches, such as SYB (but without the dynamic typing) and Uniplate (but allowing an arbitrary number of target types), for performing transformations on specific types in large tree structures. There is a tutorial explaining how to use the library [2], the API documentation should be live on Hackage shortly [1], and there is also a recent draft of a paper with benchmarks and details of the inner workings for those who are interested [3]. [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/alloy [2] http://twistedsquare.com/Alloy-Tutorial.pdf [3] http://twistedsquare.com/Alloy.pdf Thanks, Neil.

1 0

Maintaining laziness: another example
by Martijn van Steenbergen 08 Jun '09

08 Jun '09

Hello, While grading a Haskell student's work I ran into an example of a program not being lazy enough. Since it's such a basic and nice example I thought I'd share it with you: One part of the assignment was to define append :: [a] -> [a] -> [a], another to define cycle2 :: [a] -> [a]. This was her (the majority of the students in this course is female!) solution: > append :: [a] -> [a] -> [a] > append [] ys = ys > append xs [] = xs > append (x:xs) ys = x : (append xs ys) > > cycle2 :: [a] -> [a] > cycle2 [] = error "empty list" > cycle2 xs = append xs (cycle2 xs) This definition of append works fine on any non-bottom input (empty, finite, infinite), but due to the unnecessary second append case, cycle2 never produces any result. Martijn.

4 4

Re: [Haskell] ANNOUNCE: testrunner-0.9
by Max Bolingbroke 08 Jun '09

08 Jun '09

Your feature list sounds like an almost exact duplicate of that for my test-framework package, which has been available on Hackage for months (although it's almost totally unadvertised!): https://github.com/batterseapower/test-framework/tree http://hackage.haskell.org/cgi-bin/hackage-scripts/package/test-framework There is also John's testpack: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/testpack Seems like we need to advertise these better :-) Cheers, Max 2009/6/8 Reinier Lamers <tux_rocker(a)reinier.de>: > Dear all, > > testrunner is a new framework to run unit tests. It has the following > distinguishing features: > > * It can run unit tests in parallel. > * It can run QuickCheck and HUnit tests as well as simple boolean expressions. > * It comes with a ready-made main function for your unit test executable. > * This main function recognizes command-line arguments to select tests by name > and replay QuickCheck tests. > > testrunner was conceived as a part of the darcs project. > > The home page is http://projects.haskell.org/testrunner/. > > testrunner can be downloaded from > http://projects.haskell.org/testrunner/releases/testrunner-0.9.tar.gz, or with > darcs with a "darcs get http://code.haskell.org/testrunner/". > > Regards, > Reinier Lamers (tux_rocker) > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > >

1 0

Hsmagick crash
by Ron de Bruijn 08 Jun '09

08 Jun '09

Hi, I am trying to extract the image data from various file formats and it appeared that hsmagick would be the right package to use. However, it doesn't actually work or I use it incorrectly. If you have installed hsmagick and change the value of some_png_file to some existing png file, you should see that it crashes at some random pixel. For the particular 256*256 image I had, it crashed on pixel_nr `elem` [54,56,57]. I am open to suggestions for better ways to get a Array (Int,Int) RGB from e.g. a png file. import Graphics.Transform.Magick.Images import Graphics.Transform.Magick.Types import Foreign.Storable import Control.Monad image_file_name_to_2d_array file = do himage <- readImage file let ptr_to_image = image himage himage_ <- peekElemOff ptr_to_image 0 let bounds@(_rows, _cols) = (rows himage_,columns himage_) number_of_pixels = fromIntegral _rows * fromIntegral _cols mapM (\pixel_nr -> do putStrLn ("Pixel: " ++ show pixel_nr) pixel_packet <- liftM background_color_ $ peekElemOff ptr_to_image pixel_nr let red_component = red pixel_packet putStrLn ("Pixel packet: " ++ show red_component) return red_component) [0.. number_of_pixels - 1] some_png_file = "foo.png" t = do initialize_image_library image_file_name_to_2d_array some_png_file initialize_image_library = initializeMagick Best regards, Ron de Bruijn

3 3

Monad transformer responsibilities
by Martijn van Steenbergen 08 Jun '09

08 Jun '09

Hello, Suppose I have two projects: 1) one that defines a monad transformer and an accompanying type class that captures my monad-specific operations and 2) one that uses the other project, combining the monad transformer with, say, Parsec. Now while writing my Parsec parser I want to use my monad transformer operations without using lift: I need an instance MyMonadT Parsec. Where should this instance go? I can think of three answers, all unsatisfactory: 1) For obvious reasons it shouldn't go in the Parsec package. 2) For pretty much the same reasons it shouldn't go in my monad transformer package, either. Also, it is undesirable to add a dependency on Parsec just for this instance, and the package should not have to know about the projects that are going to use it. 3) If I put it in the second project it is an orphan instance, which is undesirable for well-known reasons. What is the best solution? Thank you, Martijn.

9 12

Cabal "addressibility" problem
by Vasili I. Galchin 08 Jun '09

08 Jun '09

Hello, The following is a fragment in my cabal file: Executable GraphPartitionTest Main-Is: Swish.HaskellRDF.GraphPartitionTest.hs Other-modules: Swish.HaskellRDF.GraphPartition Swish.HaskellRDF.GraphClass Swish.HaskellUtils.ListHelpers Swish.HaskellUtils.TestHelpers When I try to do a build I get: Setup: can't find source for Swish in . Cabal/Setup seem to be looking in the current directory for source but as you can see I gave "full" paths, i.e. Swish.HaskellRDF* or Swish.HaskellUtils*. What I doing wrong? Regards, Vasili

4 8

Haddock : parse error on input `{-# UNPACK'
by Erik de Castro Lopo 08 Jun '09

08 Jun '09

Hi all, I'm trying to compile the binary-strict module from hackage and I'm getting the exact same error as in the hackage build log: http://hackage.haskell.org/packages/archive/binary-strict/0.4.2/logs/failur… src/Data/Binary/Strict/IncrementalGet.hs:106:11: parse error on input `{-# UNPACK' Is this a bug? Is there any way to work around it? TIA, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

3 6