- Libraries - Haskell.org

proposal #2461: add Traversable generalizations of mapAccumL and mapAccumR
by Ross Paterson 01 Aug '08

01 Aug '08

The proposal is to add the following functions to Data.Traversable, generalizing the list versions in Data.List: -- |The 'mapAccumL' function behaves like a combination of 'fmap' -- and 'foldl'; it applies a function to each element of a structure, -- passing an accumulating parameter from left to right, and returning -- a final value of this accumulator together with the new structure. mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) -- |The 'mapAccumR' function behaves like a combination of 'fmap' -- and 'foldr'; it applies a function to each element of a structure, -- passing an accumulating parameter from right to left, and returning -- a final value of this accumulator together with the new structure. mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) These functions are handy for things like labelling trees, zipping, etc. Deadline: 3 weeks

7 12

Re: [Hs-Generics] Re: Owning SYB
by José Pedro Magalhães 01 Aug '08

01 Aug '08

Hello all, As Johan mentioned, here in Utrecht we are working on libraries for generic programming. We want to make it easier for people to use generic libraries, so we are packaging EMGM [1] and a library for generic programming for mutually recursive datatypes [2]. We intend to release these on Hackage soon (Summer vacations are delaying us a bit), along with useful generic applications (a zipper and a generic rewriting framework). Maintaining SYB fits well in this idea, and if no other natural maintainers volunteer, I (with some support from the other people at Utrecht) am happy to take it upon me. I probably won't do heavy development on the library, but including patches, and providing support is fine. We're also planning to maintain EMGM here in Utrecht, although we didn't develop that ourselves. Recently, (at least) Claus and Oleg have been posting interesting suggestions of improvements/modifications to SYB. Those should be further analyzed and discussed, and finally introduced (or not) in the library. The generic map for SYB, for instance, evolved from the "impossible to implement", through the "unsafe implementation", until the latest gmap2 as described by Oleg [3]. If further tests show this function behaves as expected, then it's clearly a good candidate for extending SYB. We should also rethink if other things previously deemed impossible remain so. Maintaining SYB, alongside with the other generic libraries, will require things such as: * Releasing packages in Hackage, properly documented with Haddock; * Updating such packages as necessary for new releases of GHC; * Writing examples of how to use the libraries (from a user perspective); * Writing testsuites, which are important for checking backwards compatibility of any changes; * Having an updated webpage linking to the library sources, documentation, possibly a bug tracker, etc. These are all things we plan to do for the libraries. Additionally, we could think of improving syb-with-class [4] in parallel with regular SYB. This is something to ask to its maintainer. Cheers, Pedro [1] http://books.google.com/books?id=OyY3ioMJRAsC&pg=PA199&sig=ACfU3U1nczeRAIjN… [2] http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html [3] http://www.haskell.org/pipermail/generics/2008-July/000362.html [4] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/syb-with-class

2 2

darcs patch: Fix Unicode bug in haskell-src
by Andrea Vezzosi 01 Aug '08

01 Aug '08

Language.Haskell.Parser currently can't parse modules with unicode symbols in operators, which are allowed by the haskell98 standard. The attached patch is a small change in the lexer code to fix this. Since parseModule expects a String of Unicode codepoints as usual, examples/hsparser.hs will still raise errors on modules that use unicode, because it doesn't decode the source. The correct behaviour, assuming an utf-8 source, can be tested like this: > import System.IO.UTF8 as U -- from utf8-string > import Language.Haskell.Parser > import Language.Haskell.Pretty > main = do file <- U.readFile "module.hs" > case parseModule of > ParseOk m -> U.putStrLn (prettyPrint m) > e@(ParseError _ _) = print e

3 2

Owning SYB
by Simon Peyton-Jones 30 Jul '08

30 Jul '08

Dear Generic folk [I'm spamming libraries(a)haskell.org too, in case anyone interested in generics is not on generics(a)haskell.org.] As you know, Claus has offered a somewhat-detailed proposal for changes to the SYB library (below). But I don't think that we have an active maintainer for any of the generic-programming libraries (esp SYB) apart from Uniplate. Then there's the related question of what generic-programming technology to promote for clients of the GHC API. The obvious candidates are Claus himself, or Alexey Rodriguez, or Thomas Schilling; but perhaps there are others too? Maybe no one has stepped forward because you all think that I'm on the job! But I'm not... I'm busy with GHC itself, and would love a maintainer for SYB and associated gubbins. I fear that otherwise we may lose the benefits of Claus's homework. Simon | -----Original Message----- | From: generics-bounces(a)haskell.org [mailto:generics-bounces@haskell.org] On Behalf Of Claus Reinke | Sent: 21 July 2008 14:16 | To: generics(a)haskell.org | Subject: [Hs-Generics] Data.Generics with GPS (using Maps to avoid getting lost in Data) | | | summary: speed up Syb with Uniplate-inspired techniques | | == Performance issues in Syb == | | As it stands, classic Syb, while well-supported in GHC isn't exactly the | fastest generic programming option. In fact, it routinely seems to come | out last in performance comparisons, sometimes by a substantial factor. | | That isn't always a problem in practice, because the gains in | expressiveness/conciseness/maintainability outweigh the loss in | performance, because traversal performance is not the bottleneck, or | because practical use often involves hand-tuned traversal schemes | instead of the example schemes typically used in benchmarks. | | Be that as it may, performance is a consideration, negative results have | been published, and it seems that performance of experimental code has | led to Syb being abandoned in at least one project. While it would be | unrealistic to expect Syb traversals to compete with hand-written ones | with current compilers, there are several obvious areas where Syb | traversal performance could be subjected to improvements: | | (a) traversing irrelevant parts of the structure (because everything is | treated generically) | (b) combining results in simple, but inefficient ways ((++) nesting with | the structure) | (c) repeated runtime type checks to determine which function in a | generically extended transformation/query to apply | | While runtime type checks are inherent in SYB (and alternatives have | been proposed that claim to avoid them), all of a/b/c can be addressed | to some extent in defining tuned traversals using the basic library. | There tends to be a trade-off for a vs c, as avoiding senseless generic | traversals of specific substructures implies additional runtime type | checks to identify those substructures [...rest snipped...]

3 3

Re: compositional gMap in SYB1
by Claus Reinke 30 Jul '08

30 Jul '08

> Hello! Hello again!-) > Claus wrote: >> Perhaps we can combine our versions to get the best of both? > > I have done so. I have committed a new version of > /comparison/SYB1_2/GMap.lhs [for readers of libraries@: that is in the generics code repo at http://darcs.haskell.org/generics/comparison/SYB1_2/GMap.lhs , look for gmap2/gmapt and comments; the topic is defining Functor fmap generically (hence gmap) in terms of Data/Typeable] Ah, of course! Silly me, if I had followed my own choice of metaphor to the end, I would have known that X marks the spot only on a map, not on the real thing (or else everyone could find the treasure..). Your shallow, incrementally built not-quite copy is just another representation of a map, and since both map and X are hidden from users of the function, everyone is happy. That something out of nothing trick is also used in the PlateData optimization and in my adaptation of it. The difference, apart from choice of representation, is mainly in whether to extract substructure placeholders/types on a type basis once per traversal or on a value basis, incrementally. Here is a re-run of the technique, for defining traverse in terms of Data/Typeable. Apart from being useful for Data.Traversable library users, the type of 'traverse id' is similar to the type of transpose, which should interest the generics readers. {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE ExistentialQuantification #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE RankNTypes #-} import Control.Applicative import Data.Generics data X = X deriving (Data,Typeable) traverseData :: forall f a b t . (Applicative f,Typeable1 f,Typeable a,Typeable b, Data (t a),Data (t b),Data (t X)) => (a -> f b) -> t a -> f (t b) traverseData f = traverseWithMap f (Dyn (undefined::t X)) where traverseWithMap :: forall f a b x y . (Applicative f,Typeable1 f,Typeable a,Typeable b,Data x,Data y) => (a -> f b) -> Dyn -> x -> f (y) traverseWithMap f (Dyn t) x | typeOf t==typeOf X = maybe (error "traverseData: non-applicable type marked") ($x) (cast f) | otherwise = rebuildWith (traverseWithMap f) t1 x where t1 = Dyn (fromConstr (toConstr x) `asTypeOf` t) rebuildWith :: forall f x y . (Applicative f,Data x,Data y) => (forall x y . (Data x,Data y) => Dyn -> x -> f y) -> Dyn -> x -> f y rebuildWith f (Dyn t) x = case gunfold (k f) (\g -> UnfldStateF2 (pure g) tkids kids) con of UnfldStateF2 a [] [] -> a where (tcon,tkids) = dynamize t (con,kids) = dynamize x k :: forall a b . (Data a) => (forall x y . (Data x,Data y) => Dyn -> x -> f y) -> UnfldStateF2 f (a->b) -> UnfldStateF2 f b k f (UnfldStateF2 ca (tkid:tkids) ((Dyn kid):kids)) = UnfldStateF2 (ca <*> (f tkid kid)) tkids kids data UnfldStateF2 f a = UnfldStateF2 (f a) [Dyn] [Dyn] data Dyn = forall a. Data a => Dyn a data Kids a = Kids{growUp:: [Dyn]} dynamize :: Data a => a -> (Constr,[Dyn]) dynamize x = (toConstr x, growUp $ gfoldl f (const (Kids [])) x) where f (Kids l) a = Kids (l ++ [Dyn a]) test = do print $ traverseData (Just . not) tuple print $ traverseData (Just . not) list traverseData print tuple >>= print traverseData print list >>= print where tuple = (True,True) list = [True,True] Btw, while the type of 'traverseData id' matches that of transpose, its behavious doesn't quite, depending on example: *Main> :t traverseData id traverseData id :: (Data (t X), Data (t b), Data (t (f b)), Typeable b, Typeable1 f, Applicative f) => t (f b) -> f (t b) *Main> traverseData id [Just x|x<-[1..3]] Just [1,2,3] *Main> traverseData id [[1..3],[4..6]] [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]] > optimization: if it is determined that a structured value has no > components to map, no traversal is performed and the value is returned > as it is. That should speed things up a little. The trick is producing > something out of nothing. That optimization is another indication of the relation to the substructure types map building, although pleasingly different in form (always nice to learn new tricks;-). > Too bad that the deadline to amend a Haskell workshop paper > has passed, and so has the deadline for the generics workshop. Perhaps > we should write a separate paper? Sounds like a good idea. When you're back. > I'm afraid I would be out of town again for two weeks and so > would not be able to follow the discussion closely. Ah, you're just trying to hide the two-week round trips for lightspeed messages resulting from your space travels!-) Thanks for yet another useful contribution, Claus

1 0

Text.JSON Questions
by R Hayes 29 Jul '08

29 Jul '08

I'm using Haskell to build a web services client. The API uses JSON, so I've been playing around with Text.JSON. Text.JSON works, but it seems kind of clumsy to me. I suspect that it's my failure to understand the proper usage pattern, rather than an issue with the design. For much of what I'm doing, I don't know *exactly* what I'm going to get back. I know that there will be specific JSON fields I'm interested in, but there may be ones I'm not expecting. Writing a readJSON for a pre-designed data structure is not the right answer. I'm not marshalling and un-marshalling structures that originate in Haskell. The structures I am un-marshalling are subject to extension. it seems like the default invocation of decode is something like: (decode aString) :: Result JSValue Is that correct? I'm unclear on the design goals of parameterizing JSObject. Why isn't JSObject just a list of (String,JSValue) tuples? What do we get from parameterizing it? What's the intent of having JSObject as a data constructor for JSValue and as a distinct type constructor (whose hidden data constructor is JSONObject)? What do we get from this? Why hide JSONObject? The way things are constructed, we always end up with two layers of data constructors for JSON objects JSObject (JSONObject ...). What do we get from this additional complexity. -r hayes

4 3

Data.Time.Clock.DiffTime documentation error
by Alexander Dunlap 29 Jul '08

29 Jul '08

Hi all, The documentation for Data.Time.Clock.DiffTime says that DiffTime has an *accuracy* of 10^-12 seconds. Since (I assume) the datatype can't ensure the accuracy of external timekeeping mechanisms, shouldn't this say *precision* of 10^-12 seconds? The same is true for NominalDiffTime. I don't know if a change this simple needs to go though the Library Submissions Process, but it certainly could. Alex

2 1

#2309: containers: specialize functions that fail in a Monad to Maybe
by Ross Paterson 28 Jul '08

28 Jul '08

Several functions on containers used to have types like lookup :: (Ord k) => k -> Map k a -> Maybe a but these were generalized to lookup :: (Monad m, Ord k) => k -> Map k a -> m a The only methods of Monad used are return and fail. The problem is that, depending on the monad, fail can be an ordinary value or a runtime error: this device makes it harder to check whether a program is safe, because it hides possible runtime errors among testable conditions. The proposal is to change these signatures back, specializing them to Maybe. The functions involved are: lookup :: Ord k => k -> Map k a -> Maybe a lookupIndex :: Ord k => k -> Map k a -> Maybe Int minViewWithKey :: Map k a -> Maybe ((k,a), Map k a) maxViewWithKey :: Map k a -> Maybe ((k,a), Map k a) minView :: Map k a -> Maybe (a, Map k a) maxView :: Map k a -> Maybe (a, Map k a) lookup :: Key -> IntMap a -> Maybe a maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a) minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a) maxView :: IntMap a -> Maybe (a, IntMap a) minView :: IntMap a -> Maybe (a, IntMap a) minView :: Set a -> Maybe (a, Set a) maxView :: Set a -> Maybe (a, Set a) maxView :: IntSet -> Maybe (Int, IntSet) minView :: IntSet -> Maybe (Int, IntSet) No information is lost, because in each case there is a single failure mode.

21 37

Cabal-Install Update Problems
by Jeff Wheeler 28 Jul '08

28 Jul '08

Hi, I'm trying to use cabal-install on two machines, Debian Sid and OS X 10.5, but I am unable to run "update" on either. Most other commands seem to work fine, but the networking for "update" gives an error on both machines, completely independently: Downloading package list from server 'http://hackage.haskell.org/packages/archive' cabal: recv: resource vanished (Connection reset by peer) Both machines are using a vanilla Netgear ProSafe VPN Firewall FVS318v3, a very simple prosumer router. Obviously, the router works fine for everything else, and has been running flawlessly for ages. This is using cabal-install from darcs and the cabal 1.4 branch. Thanks a bunch for helping, Jeff Wheeler

3 5

Strictness of enumFrom* on numeric types.
by Dan Doel 26 Jul '08

26 Jul '08

Greetings, As happens periodically, someone in #haskell brought up the following code snippet: [1..] !! 1000000 :: Integer When evaluated, that causes a stack overflow, because enumFrom currently returns a list of increasingly nested thunks for Integers (and Floats and Doubles...). The ensuing discussion, however, brought something I hadn't seen before to light: this shouldn't (I think) be the case, per the Haskell 98 report. In the section "Predefined Types and Classes", it is specified: For all four of these Prelude numeric types, all of the enumFrom family of functions are strict in all their arguments. Which would, I believe, have the side effect of making a straightforward implementation of the functions element-strict, thus preventing the stack overflows (to confuse matters, the later reference implementation of the functions for Floats and Doubles in instead non-strict, but that can probably be looked at as a bug in the report). Currently, I believe only Int (of the four listed in the report) has a proper implementation for all the functions. For instance length (take 3 (enumFrom undefined)) is undefined for Ints, but is 3 for Integers, Floats and Doubles, so that at least is a bug. enumFrom*To are, of course, correct by necessity. Anyhow, given the above text in the report, it seems reasonable to me to make the functions stricter for the above types (and any Ints and Words of various lengths if they have similar problems). There is, in fact a trac ticket for that: http://hackage.haskell.org/trac/ghc/ticket/1997 and a patch, evidently. But dons thought it would be appropriate to alert this list, as well (it is the maintainer, after all). Thanks for your time, -- Dan Doel

1 0