March 2006 - Haskell-Cafe

Looking for an efficient tree in STM
by Einar Karttunen 20 Mar '06

20 Mar '06

Hello Does anyone have an efficient tree implemented in STM that supports concurrent updates in an efficient fashion? This seems suprisingly hard to implement - a normal binary tree with links as TVar is very slow and does not scale very well. - Einar Karttunen

5 5

hs-plugins/ haskelldb/ ELF zlib incompatibility.
by Marc Weber 20 Mar '06

20 Mar '06

I get this error: calhost db=store uid=marc pwd=" DB/Direct: Daan Leijen (c) 1999, HWT (c) 2003-2004, Bjorn Bringert (c) 2005 Connecting to database... DBDirect: user error (loadShared: couldn't load `/usr/lib/libz.so' because /usr/lib/libz.so: invalid ELF header Any idea how to fix it ? (What to watch for?) latest cvs ghc, latest darcs hs-plugins (dons told me to ask the haskelldb how they managed to run it..) I've tried compiling with -lz option. Same result. I'm also posting here because I don't know how frequently the haskelldb mailinglist is read yet.. It doesn't seem to be used by that much people yet. Marc

2 2

RE: [Haskell-cafe] Type classes
by Geest, G. van den 20 Mar '06

20 Mar '06

I suppose you want to define compareEntries like this: > compareEntries (Entry x) (Entry y) = compareEntries x y An option is to just implement it the following way (Haskell98!): > class DatabaseEntry e where > entryLabel :: e -> String > formatEntry :: e -> String > compareEntries :: e -> e -> Ordering > > data Entry a = Entry a > > instance DatabaseEntry a => DatabaseEntry (Entry a) where > entryLabel (Entry e) = entryLabel e > formatEntry (Entry e) = formatEntry e > compareEntries (Entry x) (Entry y) = compareEntries x y Gerrit -----Original Message----- From: haskell-cafe-bounces(a)haskell.org on behalf of Max Vasin Sent: Mon 3/20/2006 3:46 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] Type classes Hi! I'm currently experimenting with a bibliography generation tool for LaTeX. It will (if it will be finished) use BibTeX databases but bibliography styles will be written in Haskell. I want styles to be able to transform database entries into some style specific data type, so I define > class DatabaseEntry e where > entryLabel :: e -> String > formatEntry :: e -> String > compareEntries :: e -> e -> Ordering Then I define > data Entry = forall a. (DatabaseEntry a) => Entry a > instance DatabaseEntry Entry where > entryLabel (Entry e) = entryLabel e > formatEntry (Entry e) = formatEntry e How can I define compareEntries for this instance? -- WBR, Max Vasin. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

3 2

Type classes
by Max Vasin 20 Mar '06

20 Mar '06

Hi! I'm currently experimenting with a bibliography generation tool for LaTeX. It will (if it will be finished) use BibTeX databases but bibliography styles will be written in Haskell. I want styles to be able to transform database entries into some style specific data type, so I define > class DatabaseEntry e where > entryLabel :: e -> String > formatEntry :: e -> String > compareEntries :: e -> e -> Ordering Then I define > data Entry = forall a. (DatabaseEntry a) => Entry a > instance DatabaseEntry Entry where > entryLabel (Entry e) = entryLabel e > formatEntry (Entry e) = formatEntry e How can I define compareEntries for this instance? -- WBR, Max Vasin.

3 3

Associated types and data constructors (was: the MPTC Dilemma (please solve))
by David Menendez 19 Mar '06

19 Mar '06

(I've moved this from haskell' to haskell-cafe, because it's more a question about associated types than about resolving the MPTC dilemma.) Bulat Ziganshin writes: > Hello Manuel, > > MMTC> My statement remains: Why use a relational notation if you can > MMTC> have a functional one? > > how about these examples? > > MMTC> class Monad m => RefMonad m where > MMTC> type Ref m :: * -> * > > can i use `Ref` as type function? for example: > > data StrBuffer m = StrBuffer (Ref m Int) > (Ref m String) > This is something I've been wondering about for a while. Can you do that sort of thing with associated types? As another example, consider this type class for composible continuation monads: class Monad m => MonadCC p sk m | m -> p sk where newPrompt :: m (p a) pushPrompt :: p a -> m a -> m a withSubCont :: p b -> (sk a b -> m b) -> m a pushSubCont :: sk a b -> m a -> m b You can use instances of this class to create backtracking monads, along these lines: data Tree m a = HZero | HOne a | HChoice a (m (Tree m a)) newtype SR p m a = SR (forall ans. ReaderT (p (Tree m ans)) m a) instance MonadCC p sk m => MonadPlus (SR p m) With associated types, the MonadCC class becomes: class Monad m => MonadCC m where type Prompt m a type SubCont m a b newPrompt :: m (Prompt m a) pushPrompt :: Prompt m a -> m a -> m a withSubCont :: Prompt m b -> (SubCont m a b -> m b) -> m a pushSubCont :: SubCont m a b -> m a -> m b Since |Prompt m| is determined by |m|, can we eliminate the prompt parameter from SR? newtype SR' m a = SR' (forall ans. ReaderT (Prompt m (Tree m ans)) m a) instance MonadCC m => MonadPlus (SR' m) That would presumably lead to SR' having the type SR' :: (MonadCC m) => ReaderT (Prompt m (Tree m ans)) m a -> SR' m a That doesn't seem like it should be a problem, since it's impossible to create a value of type |ReaderT (Prompt m (Tree m ans)) m a| unless m is an instance of MonadCC, but it also puts a context on a newtype data constructor, which isn't currently allowed. Sure, it's still possible to do this: instance MonadCC m => MonadPlus (SR (Prompt m) m) but that doesn't feel like a big win. -- David Menendez <zednenem(a)psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"

1 0

STUArray
by Frederik Eaton 18 Mar '06

18 Mar '06

Hi all, I'm trying to figure out how to use STUArray. Is it possible to let it be polymorphic? Here is an excerpt from my program: class (IArray UArray k, Ord k, Fractional k) => Elt k class (Bounded a, Enum a, Ix a, Eq a, Show a) => IxB a -- |like Array but uses IxB instead of Ix newtype Vector k i = Vector (UArray.UArray i k) deriving (Eq) margin :: (IxB a, IxB b, Elt k, (MArray (STUArray s) k (ST s))) => Vector k a -> (a -> b) -> Vector k b margin (Vector v) f = Vector (runSTUArray (do ax <- newArray (minBound, maxBound) 0 mapM_ (\ (i,x) -> updateArray ax (f i) (+x)) (assocs v) return ax )) where updateArray ax i f = do e <- readArray ax i writeArray ax i (f e) When I try to run it, I get the following error. I think I understand what the error means, but not how to fix the problem: Vector2.hs:166:22: No instance for (MArray (STUArray s) k (ST s)) arising from use of `updateArray' at Vector2.hs:166:22-32 Probable fix: add (MArray (STUArray s) k (ST s)) to the expected type of an expression or add an instance declaration for (MArray (STUArray s) k (ST s)) In a lambda abstraction: \ (i, x) -> updateArray ax (f i) ((+ x)) In the first argument of `mapM_', namely `(\ (i, x) -> updateArray ax (f i) ((+ x)))' In a 'do' expression: mapM_ (\ (i, x) -> updateArray ax (f i) ((+ x))) (assocs v) Thanks in advance, Frederik -- http://ofb.net/~frederik/

5 7

RE: [Haskell-cafe] how would this be done? type classes? existentialtypes?
by Geest, G. van den 18 Mar '06

18 Mar '06

Try using a GADT: data Rs where Rs :: Resource a => a -> Rs class Resource a where resourceName :: a -> String instance Resource String where resourceName x = "String" instance Resource Int where resourceName x = "Int" resName (Rs x) = resourceName x resNames = map resName test = resNames [Rs "Hi", Rs (1::Int) ] The most important observations is that when pattern matching on (Rs x) we cannot make any assumptions about x, except using the class members of Resource. We hope this will help you, Gerrit (and the rest of the ST-lab) -----Original Message----- From: haskell-cafe-bounces(a)haskell.org on behalf of Matthias Fischmann Sent: Thu 3/16/2006 12:57 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] how would this be done? type classes? existentialtypes? hi, this is one of those situations that always make scheme and perl hackers laugh at me: i have written a piece of code that is intuitively clear, and now i am trying to turn it into something that compiles. and here it goes. i have a type class that looks something like this: class Resource a where resourceName :: a -> String resourceAdvance :: a -> a resourceStarved :: a -> Bool resourceSpend :: a -> Int -> a resourceEarn :: a -> Int -> a resource types are rice, crude oil, pizza, software code, and so on. they all have a different internal structure and the same abstract interface, that's why i have defined this type class. now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) => [a] but with r1 being pizza, r2 being crude oil, and so on. my first idea was this: data Rs = forall a . (Resource a) => Rs a unRs (Rs a) = a rsName :: Rs -> String rsName = resourceName . unRs ... and then export Rs as an abstract data type. this would allow for lists of type [Rs], which is exactly what i want. but what is the type of unRs? or better: can i make it type at all? and isn't this solution a little redundant and verbose? should i do it like in the example for existentially quantified types in the ghc manual? http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html but wouldnt't the code become really messy? or should i do the type class and instances, and then do Rs the existentially quantified way, with all class methods arguments to the Rs constructor? or is there a completely different way to do this (besides using scheme or perl :-)? thanks, matthias -----Original Message----- From: haskell-cafe-bounces(a)haskell.org on behalf of Matthias Fischmann Sent: Thu 3/16/2006 12:57 PM To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] how would this be done? type classes? existentialtypes? hi, this is one of those situations that always make scheme and perl hackers laugh at me: i have written a piece of code that is intuitively clear, and now i am trying to turn it into something that compiles. and here it goes. i have a type class that looks something like this: class Resource a where resourceName :: a -> String resourceAdvance :: a -> a resourceStarved :: a -> Bool resourceSpend :: a -> Int -> a resourceEarn :: a -> Int -> a resource types are rice, crude oil, pizza, software code, and so on. they all have a different internal structure and the same abstract interface, that's why i have defined this type class. now i want to create a list of a type similar to [r1, r2, r3] :: (Resource a) => [a] but with r1 being pizza, r2 being crude oil, and so on. my first idea was this: data Rs = forall a . (Resource a) => Rs a unRs (Rs a) = a rsName :: Rs -> String rsName = resourceName . unRs ... and then export Rs as an abstract data type. this would allow for lists of type [Rs], which is exactly what i want. but what is the type of unRs? or better: can i make it type at all? and isn't this solution a little redundant and verbose? should i do it like in the example for existentially quantified types in the ghc manual? http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.html but wouldnt't the code become really messy? or should i do the type class and instances, and then do Rs the existentially quantified way, with all class methods arguments to the Rs constructor? or is there a completely different way to do this (besides using scheme or perl :-)? thanks, matthias

3 3

Re: dynamic arrays
by Jared Updike 17 Mar '06

17 Mar '06

(Moved to haskell-cafe) JU> General question to the list: JU> (Q) Are there any data structures in Haskell similar to C++/STL JU> vectors or C# generic Lists (i.e. strongly typed ArrayLists, e.g. JU> List<int>)? These data structures grow automatically as you add JU> elements to them (but in large chunks, not one node at a time). This JU> data structure (if it exists in Haskell) would run inside a monad (ST JU> and/or IO) and it would automaticly resize when needed, but would be JU> more or less like a mutable array except you can add new elements to JU> the end of it without reallocating an entire array of n+1 elements... i tried to implement this today :) but there is one problem: > if i have (l,u) - array bounds of type Ix, and i - offending index of > the same type, how can i compute new bounds of array so that it will > grow in large chunks? there is no such computation operations for > Ix type and that is logical - if this array is really a matrix then > it's hard to use the same rules of extending it as for vectors Hmmm, that is a problem, especially as you said, for enum types that are bounded above. I guess you can't make it grow more than the min and max. For the most part, this dynamic array would only be useful for arrays with indices isomorphic to the natural numbers. > such computation as (u-l)*2+l is great for integral indexes, but not > for general case. now i plan to use this strategy for all enum types > and just "grow to minimal and maximal indexes actually used" for other > index types Perhaps the function to build these DynamicArrays could take a Maybe parameter telling the maximum possible range (for bounded enums) or Nothing if the array is allowed to grow indefinitely. Or an Either parameter where Left (a,a) tells the max range and Right (a,a) -> (a,a) which tells how the range should grow on a resize. Or just the range resize function :: (a,a) -> (a,a) telling how to grow on a resize, i.e. for enums function = id. Something like that. Jared.

4 5

different code in different platforms
by José Miguel Vilaça 17 Mar '06

17 Mar '06

Sorry. In the previous email I forgot the subject. Hi Im having a small problem with the portability of my Haskell code. My code uses wxHaskell and the library for which this one is the Haskell interface (that is called wxWidgets) doesnt work in the same away in Windows and Linux. Now I now which code run in Linux and in Windows but I dont want to have to manually change the file in each platform. I tried a solution using the C pre-processor but I getting in trouble. I use code like: #ifdef __WIN32__ (Windows code) #else (Linux code) #endif I also add the --cpp to the ghc and it works for me in Linux but give me linking errors in Windows. Does someone have any hints on how to have different code in Windows and Linux? I would be thankful in some help. Best regards Miguel Vilaça

5 4

Re: [Haskell-cafe] how would this be done? type classes? existential types?
by Matthias Fischmann 16 Mar '06

16 Mar '06

Alexandra Silva <xana(a)di.uminho.pt> wrote: > http://homepages.cwi.nl/~ralf/HList/ this looks like it might address my problems with Read / Eq instantiation? will read. thanks again to everybody. m.

1 0