- Haskell-Cafe - Haskell.org

ANN: haskell-src-exts 0.3.5
by Niklas Broberg 15 Jul '08

15 Jul '08

Hi all, I'm pleased to report that haskell-src-exts is now updated to understand Template Haskell syntax (it used to understand pre-6.4 TH, but now it works with the current version). At least I hope so, I didn't have much TH code to try it on so if you find some bugs just let me know. It wasn't all that hard to fix though, so I'm pretty confident it actually works. Get the code: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haskell-src-exts… darcs get http://code.haskell.org/HSP/haskell-src-exts Cheers, /Niklas

2 1

Re: [Haskell-cafe] Type level sets with GADTs, fundeps etc
by J.Burton＠brighton.ac.uk 15 Jul '08

15 Jul '08

At Tue, 15 Jul 2008 10:02:23 -0400, Jeff Polakow wrote: [...] > > > Type classes are open so there is nothing to prevent you from adding another > instance for If, perhaps in a different module, which returns some arbitrary > type. I see what you mean...so I tried to make Ins return an LSet of "something", like this: data LSet t where Nil :: LSet Nil Ins :: (Member a t b , If b t (a ::: t) r) => L a -> LSet t -> LSet r /home/jim/sdf-bzr/dsel/TF/Set-July08.hs:44:9: No instance for (If b t (a ::: t) r) arising from a use of `Ins' at /home/jim/sdf-bzr/dsel/TF/Set-July08.hs:44:9-11 Possible fix: add an instance declaration for (If b t (a ::: t) r) In the expression: Ins In the definition of `insert': insert = Ins /home/jim/sdf-bzr/dsel/TF/Set-July08.hs:68:6: Inferred type is less polymorphic than expected Quantified type variable `a' is mentioned in the environment: insert :: L a -> LSet t -> LSet r (bound at /home/jim/sdf-bzr/dsel/TF/Set-July08.hs:44:0) When checking an existential match that binds t :: L a The pattern(s) have type(s): LBox The body has type: LSetBox In a case alternative: LBox t -> LSetBox (insert t s) In the expression: case fromChar c of LBox t -> LSetBox (insert t s) Failed, modules loaded: none. > > -Jeff > > > --- > > This e-mail may contain confidential and/or privileged information. If you > are not the intended recipient (or have received this e-mail in error) > please notify the sender immediately and destroy this e-mail. Any > unauthorized copying, disclosure or distribution of the material in this > e-mail is strictly forbidden. > [2 <text/html; US-ASCII (7bit)>] >

2 1

Re: [Haskell-cafe] Type level sets with GADTs, fundeps etc
by J.Burton＠brighton.ac.uk 15 Jul '08

15 Jul '08

At Tue, 15 Jul 2008 09:43:40 -0400, Jeff Polakow wrote: > Hello, Hi Jeff, > > > data LSet t where > > Nil :: LSet Nil > > --either add the new element or do nothing > > Ins :: (Member a t b > > , If b (LSet t) (LSet (a ::: t)) r) > > => L a -> LSet t -> r > > > The constructor Ins needs to return an LSet. Maybe try replacing occurrences of r with (LSet r). > I expected that r would be an LSet, as its the output of If which returns its 2nd or 3rd argument: class If p x y z | p x y -> z where if' :: p -> x -> y -> z instance If T x y x instance If F x y y Jim > -Jeff > > --- > > This e-mail may contain confidential and/or privileged information. If you > are not the intended recipient (or have received this e-mail in error) > please notify the sender immediately and destroy this e-mail. Any > unauthorized copying, disclosure or distribution of the material in this > e-mail is strictly forbidden. > >

2 1

Type level sets with GADTs, fundeps etc
by J.Burton＠brighton.ac.uk 15 Jul '08

15 Jul '08

I have a problem with applying a type constraint in the constructor of a GADT...I wrote some type level code for sets using empty types and fundeps, along the lines of Conrad Parker's Instant Insanity and Oleg's Lightweight Static Resources. At this level things works OK so I have empty types A, B ... Nil with an infix cons (:::) and fundeps determining constraints like Member, Disjoint etc. (Links to code at the end of message.) Then I can evaluate: > :t insert (undefined::A) (undefined:: A ::: Nil) insert (undefined::A) (undefined:: A ::: Nil) :: A ::: Nil But what I really want to do is wrap this up so that it can be used at runtime, not just in the type-checker, so that (just a sketch) I could have insert 'A' empty :: Set (A ::: Nil) where the runtime value of the set is fully determined by its type. I got some help with this and existential boxing seems to be the answer. I got a version that uses this strategy working OK until it comes to applying constraints (e.g. Member, needed when inserting an element). My problem is below. Here's one with no constraints that will type-check: ---------------------- {-box for labels -} data LBox = forall a. LBox (L a) {-box for sets of labels-} data LSetBox = forall t. LSetBox (LSet t) {-sets of labels -} data LSet t where Nil :: LSet Nil -- 'dumb' insertion Ins :: L a -> LSet t -> LSet (a ::: t) insert = Ins empty :: LSetBox empty = LSetBox Nil {-take a Char into a boxed LSet-} insertChar :: Char -> LSetBox -> LSetBox insertChar c (LSetBox s) = case fromChar c of LBox t -> LSetBox (insert t s) {-populate a box-} fromChar :: Char -> LBox fromChar 'A' = LBox AL {- ... B, etc -- use Template Haskell to generate alphabet and the various instances needed? -} fromChar _ = error "fromChar: bad Char" ------------------------ With some Show instances then I can evaluate > insertChar 'A' empty LSet {A,} But what about constraints on the Ins constructor, e.g. on insertion, ignore elements that are already there: --------------------- data LSet t where Nil :: LSet Nil --either add the new element or do nothing Ins :: (Member a t b , If b (LSet t) (LSet (a ::: t)) r) => L a -> LSet t -> r insert = Ins [...] class Member x ys b | x ys -> b where member :: x -> ys -> b instance Member x Nil F instance (Eq x y b', Member x ys m, If b' T m b) => Member x (y:::ys) b class If p x y z | p x y -> z where if' :: p -> x -> y -> z instance If T x y x instance If F x y y --------------------- But this evidently isn't the way to use fundeps -- here's the error: Malformed constructor result type: r In the result type of a data constructor: r In the data type declaration for `LSet' Failed, modules loaded: none. (The other place I tried putting the constraints is in the type of `insert' rather than the Ins constructor...) How can I express this constraint? BTW, I would rather be using type families for this, for forward compatibility and their greater generality, so if I can also get round this with them I'd love to know how... Thanks, and sorry for the long post! Jim [1] Purely type level version: http://jim.sdf-eu.org/TypeLevelSets2.hs [2] Interactive version using GADTs/Existential boxing: http://jim.sdf-eu.org/Set-July08.hs

2 1

ANN: Launching Haskell Group in Vancouver, Canada
by Jon Strait 15 Jul '08

15 Jul '08

For those in Vancouver, a short announcement about the recently created Haskell Programmers Group and a meeting scheduled for next Monday, July 21st. http://groups.google.com/group/hugvan Future group announcements will be posted on this Google Groups site, so feel free to join the group list to be notified of future events or just show up to a meeting to bounce ideas and questions off of other Haskell programmers. Thanks, Jon

1 0

A question about algebra and dependent typing
by Nathan Bloomfield 15 Jul '08

15 Jul '08

There's something I want to do with Haskell, and after tinkering for a while I think it's not possible. Before giving up entirely, I thought I'd try this mailing list. I'm working on an abstract algebra library, using the "types are sets" strategy. For the algebraists out there, I'm trying to implement as much as I can of "Abstract Algebra" by Dummit & Foote in Haskell. I've got a Ring class definition that looks approximately like > class Ring t where > (<+>) :: t -> t -> t > (<*>) :: t -> t -> t > neg :: t -> t > zero :: t So, for example, we can say >instance Ring Integer where > (<+>) = (+) > (<*>) = (*) > neg = negate > zero = 0 >From here I can subclass to domains, PIDs, EDs, UFDs, fields, et cetera, and write some useful algorithms in great generality. The ring R[x] can be modeled by the type [r], direct products are tuples, and fractions in the domain r have type Fraction r. I can even model the set (i.e. type) of nxn matrices over a ring using type-level integers as demonstrated in the paper "Number-Parameterized Types" by Oleg Kiselyov [1]. All good stuff. However, I'm running into problems modeling some other useful and computationally interesting things, in particular adjoining an algebraic element and taking a quotient by an ideal. For example, I've tried the following (using GHC extensions): >class (Ring r) => Ideal i r | i -> r > >data (Ring r) => FinGenIdeal r = Ideal [r] > >instance (Ring r) => Ideal (FinGenIdeal r) r > >data (Ring r, Ideal i r) => Coset r i = r :+: i But of course I can't say >instance (Ring r, Ideal i r) => Ring (Coset r i) where > (r :+: i) <+> (s :+: j) = (r <+> s) :+: i > zero = zero :+: ? > ... It shouldn't make sense to add 2 :+: Ideal [3] and 3 :+: Ideal [5], for example, and zero is ambiguous. This problem happems because Ideal [3] and Ideal [5] have the same type, namely FinGenIdeal Integer. I am pretty new to Haskell and type theory, but I think what I'm wanting is dependent types. So, for instance, the type of Coset r i is parameterized by an particular value in FinGenIdeal r. Is there another way around this? I'm sure there is some sophisticated type-fu one could perform (similar to the examples in [1]) to construct ideals of integers, tuples of integers, et cetera, but this would quickly get unwieldy and sacrifices some generality. I have heard lots of praise of GADT as an approximation to dependent types, but I don't yet see how they could apply in this situation. Has anyone else encountered a similar problem, and if so, how did you get around it? Would I be better off working in a dependently-typed language like Agda? [1] - http://okmij.org/ftp/papers/number-parameterized-types.pdf

5 4

Sphinx full-text searching client on Hackage
by Chris Eidhof 14 Jul '08

14 Jul '08

Hey everyone, We started working on a client [1] for the sphinx full-text search engine [2], which is a very fast full-text search engine that has either SQL or XML as a backend. While our version is far from done (it only supports the query command, and a limited number of parameters), we still think that it might be useful for other people as well. If you want to help us hacking on it, testing it or improving documentation, you're more than welcome. The communication with Sphinx is done using a quite low-level binary protocol, but Data.Binary saved the day: it made it very easy for us to parse all the binary things. Especially the use of the Get and Put monads are a big improvement over the manual reading and keeping track of positions, as is done in the PHP/Python clients. Thanks, -chris [1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sphinx [2]: http://www.sphinxsearch.com/

2 1

vector vs uvector
by stefan kersten 14 Jul '08

14 Jul '08

hi, what's the difference between the vector [1] and uvector [2] packages? should one of those preferred over the other? thanks, <sk> [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ vector-0.1 [2] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ uvector-0.1.0.1

3 3

Human-friendly compiler errors for GHC
by Max Bolingbroke 14 Jul '08

14 Jul '08

I had some free time this afternoon so I put together an (experimental) patch for GHC that implements helpful errors messages. Have a look at this GHCi session to see what I mean: "" $ stage2/ghc-inplace --interactive -fhelpful-errors GHCi, version 6.9.20080711: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> let foo = 10 Prelude> foa <interactive>:1:0: Not in scope: `foa' Maybe you meant one of: `foo' `fst' `not' -- Maybe the matching threshold could stand to be tweaked a bit, e.g. scaled with identifier string length.. Prelude> let myIdentifier = 10 Prelude> myIdentfiier <interactive>:1:0: Not in scope: `myIdentfiier' Maybe you meant `myIdentifier' Prelude> "" The feature was inspired by the equivalent feature in the Boo programming language (http://boo.codehaus.org/) I use the restricted Damerau–Levenshtein distance to do the fuzzy match (http://en.wikipedia.org/wiki/Damerau-Levenshtein_distance) What do you think about this feature? Would it be genuinely helpful or annoying? Max

10 15

Re: [Haskell-cafe] ANNOUNCE: vector 0.1 (efficient arrays with lots of fusion)
by Levi Stephen 14 Jul '08

14 Jul '08

On Sun, Jul 13, 2008 at 12:31 AM, Roman Leshchinskiy <rl(a)cse.unsw.edu.au> wrote: > Hi all, > > the vector library will eventually provide fast, Int-indexed arrays with a > powerful fusion framework. It's very immature at the moment (I haven't > tested most of the code) and implements just a few combinators but I > thought releasing early wouldn't hurt. Use at your own risk and expect > things to break horribly! > Sounds interesting. How does this compare to the uvector library? Thanks, Levi

3 2