- Libraries - Haskell.org

Fwd: Re: Pointed and Traversable
by Petr Pudlák 30 Aug '13

30 Aug '13

I forgot to add "libraries" as a recipient, so I'm forwarding the mail. PP -------- Pu*vodní zpráva -------- Pr(edme(t: Re: Pointed and Traversable Datum: Fri, 30 Aug 2013 16:59:45 +0200 Od: Petr Pudlák <petr.mvd(a)gmail.com> Komu: Edward Kmett <ekmett(a)gmail.com> Kopie: Henning Thielemann <schlepptop(a)henning-thielemann.de>, Frantisek Farka <ffarka(a)gmail.com> Dne 08/26/2013 10:26 PM, Edward Kmett napsal(a): > I can't speak well to SHE's implementation but there are a few > tensions in the design space of how to handle default superclass > instances in a language like Haskell that makes them not perfectly > solve the issue that Haskell generally sucks at dealing with deep > accurate typeclass hierarchies. > > 1.) When you have a complex lattice of types rather than a linear > chain, you're going to get a lot of ways to derive the common default > functionality. > > class Functor f => Applicative f > gives one way to automatically define fmap > > class Functor f => Traversable f > gives another way to define fmap for free > > class Functor f => Comonad f > gives a third way to define fmap for free > > In general when you have a lattice of properties points above you in > the lattice will start getting an exploding number of definitions from > classes below them, leading to limited utility for any 'hiding' based > mechanism as you've traded n definitions for n hiding declarations. True, that's an important issue to solve, I'll have to think about it. One idea that emerges is to borrow some concepts from OOP/Java and to distinguish "interface"-like type classes that have no defaults (just the ones we have now) and "class"-like type classes that can have defaults. And "class"-like could "descend" only from at most one other "class"-like type class. (This is perhaps somewhat similar to http://repetae.net/recent/out/classalias.html, which distinguishes classes from class aliases.) > > 2.) As typeclass hierarchies become deeper with more refined notions, > say, Functor, Semiapplicative, Semimonad, Pointed, Applicative, Monad > (note the last 2 only have laws with no methods in the perfect world), > you wind up being able to get fewer default/mutual definitions to work > at any individual level of the hierarchy. > > 3) Product-like constructions, monad transformers, etc. still need > definitions for every point in the typeclass lattice. Since almost all > of my code is polymorphic in this style, it turns out I almost never > get to use the instances that would be supplied by a default > superclass system. Could you please give an example? You mean that if let's say we introduce Applicative => Monad with the default superclass system, you'd still have to refactor your code? > > I generally favor the notion of adding default definitions for > superclass methods and adding 'default instances', I just think it is > necessary to point out that it doesn't help nearly as much as everyone > thinks it will, when it comes to the pains induced by retroactively > adding a finer grained inheritance hierarchy. > > Culturally, it is a hard sell to the average Haskeller to get them to > embrace a class that doesn't give them any new methods, so we wind up > with an awkward culture that favors a few powerful abstractions over > the full menagerie of accurate types. I'd say it depends how it's presented. The main selling point for adding fine grained hierarchy is that more things get a common type class. Like we could say we don't need Functors or Applicatives because most of them are Monads anyway, but still people agree that Functors are useful and needed. So I think the main objection of the average Haskeller is that introducing a new type class breaks (his) stuff. If we can find a mechanism how to avoid that, I'd say (s)he wouldn't mind (perhaps even care). Best regards, Petr > > -Edward > > > > On Mon, Aug 26, 2013 at 2:18 PM, Petr Pudlák <petr.mvd(a)gmail.com > <mailto:petr.mvd@gmail.com>> wrote: > > One of our students is currently exploring how to extend Haskell > so that splitting classes into more fine-grained hierarchy won't > cause these problems: > https://groups.google.com/forum/#!topic/haskell-cafe/W1NbrikzgCQ > <https://groups.google.com/forum/#%21topic/haskell-cafe/W1NbrikzgCQ> > along the lines of > http://ghc.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances > Unfortunately, it seems his message went unnoticed by Haskell > community. > > Best regards, > Petr Pudlak > > Dne 08/26/2013 07:16 PM, Edward Kmett napsal(a): >> There are several uses of Pointed as a separate beast from >> Applicative. In particular it comes up when we talk about "affine >> traversals", and would let us refine the type hierarchy of lens, >> so you'd think I'd be for it. >> >> However, to move it into its own class would require literally >> everyone who currently has an Applicative instance to clutter >> their code with CPPs. >> >> Even as the author of the Pointed class, I personally find that >> the benefit of the change doesn't warrant the impact of the change. >> >> -Edward >> >> >> On Mon, Aug 26, 2013 at 12:59 PM, Henning Thielemann >> <schlepptop(a)henning-thielemann.de >> <mailto:schlepptop@henning-thielemann.de>> wrote: >> >> There was a lot of discussion about separating "pure" from >> Applicative and putting it into a Pointed class. If I >> remember correctly, the main counter argument was that 'pure' >> alone does not satisfy interesting laws. There are only such >> laws in connection with the Applicative class. >> >> Now, in some situations I liked to have a generalized >> unfoldr. I can build this from "pure" and "sequenceA" using >> the State monad: >> >> unfoldr :: (Pointed t, Traversable t) => (s -> (a, s)) -> s >> -> t a >> unfoldr = evalState . sequenceA . pure . state >> >> One could state a law like: >> >> traverse f (pure a) == traverse id (pure (f a)) >> >> Would this justify to move "pure" into a new Pointed class? >> >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org <mailto:Libraries@haskell.org> >> http://www.haskell.org/mailman/listinfo/libraries >> >> >> >> >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org <mailto:Libraries@haskell.org> >> http://www.haskell.org/mailman/listinfo/libraries > >

1 0

sequence causing stack overflow on pretty small lists
by Niklas Hambüchen 28 Aug '13

28 Aug '13

On #haskell we recently had a discussion about the following: import System.Random list <- replicateM 1000000 randomIO :: IO [Int] I would think that this gives us a list of a million random Ints. In fact, this is what happens in ghci. But with ghc we get: Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. This is because sequence is implemented as sequence (m:ms) = do x <- m xs <- sequence ms return (x:xs) and uses stack space when used on some [IO a]. >From a theoretical side, this is an implementation detail. From the software engineering side this disastrous because the code is * obviously correct by itself * the first thing people would come up with * not exaggerating: a million elements is not much * used a lot of places: mapM, replicateM are *everywhere* and yet it will kill our programs, crash our airplanes, and give no helpful information where the problem occurred. Effectively, sequence is a partial function. (Note: We are not trying to obtain a lazy list of random numbers, use any kind of streaming or the likes. We want the list in memory and use it.) We noticed that this problem did not happen if sequence were implemented with a difference list. What do you think about this? Should we "fix" functions like this, probably trading off a small performance hit, or accept that idiomatic Haskell code can crash at any time?

8 10

cabal-install and executable dependencies
by harry 26 Aug '13

26 Aug '13

Many packages have dependencies on executable packages. There are currently three ways to specify the dependency: -Include it in the dependencies list, which will reinstall it every time. -Omit it, and the user will have to work it out when they see the Setup error message. -Some packages "cheat" by including a dummy library with the executable. I would like to propose that cabal do simple dependency checking for executables. If it exists in the path or cabal's bin directory, then the dependency it deemed satisfied. If it's in cabal's bin but not the path, the user should be warned. This doesn't support version bounds, but surely it's better than the current situation. I'm assume that this has been discussed some time before, but can't find any such discussion. -- View this message in context: http://haskell.1045720.n5.nabble.com/cabal-install-and-executable-dependenc… Sent from the Haskell - Libraries mailing list archive at Nabble.com.

3 8

Re: [commit: unix] master: change notes (1461d21)
by Ian Lynagh 24 Aug '13

24 Aug '13

On Fri, Feb 08, 2013 at 01:56:28PM +0000, Simon Marlow wrote: > On 03/02/13 20:48, Simon Marlow wrote: > >On 02/02/13 14:11, Ian Lynagh wrote: > >> > >>The unix version number is still 2.6.1.0, but doesn't the new policy > >>http://hackage.haskell.org/trac/ghc/wiki/Repositories#Modifyinglocalpackages > >> > >>mean that it should be bumped to 2.7.0.0 now? Actually, having just tried to do this, I'm not sure how it's meant to work in practice. Bumping unix's version requires relaxing the dependencies in Cabal and haskeline on unix. One way to do this is to get upstream to relax the dependency and updating our lagging repo. That will mean a version of the library will be uploaded to hackage with the relaxed dependency. But we don't know what the release 2.7.0.0 of unix will look like yet; perhaps by the time it is released it will not work with the current Cabal/haskeline code. The other way is to make local ghc-only changes to relax the dependencies, but that would increase the risk that we'd release with a ghc branch of the library by mistake. Wouldn't it be better to go back to the previous scheme, where we didn't update version numbers until release time? Thanks Ian

5 7

backwards compatibility of array
by Richard Eisenberg 21 Aug '13

21 Aug '13

The following thread on Haskell-cafe is of interest to this list: http://www.haskell.org/pipermail/haskell-cafe/2013-August/108427.html The first email introduces an infelicity in the libraries, but then the discussion says that this address (libraries(a)haskell.org) is listed as the maintainer of the libraries, and yet the mailing list cannot be written to by the general public. I tend to agree that this should be fixed. Richard

2 1

RE: isSafeOverlap
by Simon Peyton-Jones 20 Aug '13

20 Aug '13

| Oh also, we deprecated a bunch of unsafe functions in modules. For | example, `unsafeInterleaveST` in Control.Monad.ST.Lazy as it was moved | to Control.Monad.ST.Lazy.Unsafe. | | Are you happy with me removing these now that it's been a three | releases (7.2, 7.4, 7.6) with them deprecated? Ccing 'libraries' but yes that sounds reasonable. Simon | -----Original Message----- | From: David Terei [mailto:davidterei@gmail.com] | Sent: 20 August 2013 00:04 | To: Simon Peyton-Jones | Subject: Re: isSafeOverlap | | Oh also, we deprecated a bunch of unsafe functions in modules. For | example, `unsafeInterleaveST` in Control.Monad.ST.Lazy as it was moved | to Control.Monad.ST.Lazy.Unsafe. | | Are you happy with me removing these now that it's been a three | releases (7.2, 7.4, 7.6) with them deprecated? | | Cheers, | David | | On 19 August 2013 13:04, David Terei <davidterei(a)gmail.com> wrote: | > Sure. Doing right now. | > | > On 19 August 2013 01:19, Simon Peyton-Jones <simonpj(a)microsoft.com> | wrote: | >> David | >> | >> Looking at BasicTypes.lhs I see that the OverlapFlag has an | isSafeOverlap | >> field for every flag. I guess this is something to do with Safe | Haskell but | >> there is nothing to say so, nor any comment to explain what the | significance | >> is. | >> | >> Do you think you might add "Note [isSafeOverlap flag]" to explain? | Thanks! | >> | >> Simon | >> | >> | >> | >> Microsoft Research Limited (company number 03369488) is registered in | >> England and Wales | >> | >> Registered office is at 21 Station Road, Cambridge, CB1 2FB | >> | >>

2 2

suggestion: use lazy pattern matching for Monoid instances of tuples
by Petr Pudlák 19 Aug '13

19 Aug '13

Dear haskellers, currently the instances are defined as |instance (Monoid a,Monoid b) =>Monoid (a,b)where mempty = (mempty, mempty) (a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2)| However for some applications this isn't lazy enough, for example |-- | Build two lists by folding on a pair of `Endo` monoids. test = head $ appEndo (fst $ foldMap (f &&& f) [1..]) [] where f =Endo . (:)| never terminates because of the unnecessary pattern matching on the constructor |(,)| forces evaluation of the whole infinite list. I suggest to change all Monoid instances for tuples to be like | instance (Monoid a,Monoid b) =>Monoid (a,b)where mempty = (mempty, mempty) ~(a1,b1) `mappend` ~(a2,b2) = (a1 `mappend` a2, b1 `mappend` b2) -- ^^^ ^^^| which fixes the problem. Best regards, Petr

7 14

Proposal: Add gtraverse to Data.Data
by Edward Kmett 18 Aug '13

18 Aug '13

Data.Data provides an gmapM as an analogue to mapM but not one to traverse. The following definition from lens fills in this gap, but it probably belongs in Data.Data alongside its kin. gtraverse :: (Applicative f, Data a) => (forall d. Data d => d -> f d) -> a -> f a gtraverse f = gfoldl (\x y -> x <*> f y) pure Discussion period: 2 weeks -Edward Kmett

3 2

Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_
by Ryan Newton 16 Aug '13

16 Aug '13

If there's not an existing way to do this, I suppose this is a minor proposal. When writing monadic code that consumes a container (Set, Map) etc, I often find that I just want what iterators in imperative languages provide: that is, to iterate over the contents of a large container, performing monadic effects along the way, but without allocating. The Foldable instance for Data.Map almost gives you what you want, but it only exposes the values, not their keys. The "traverseWithKey" function is close too, but it builds a new Map as output: traverseWithKey :: Applicative<../base-4.6.0.1/Control-Applicative.html#t:Applicative> t => (k -> a -> t b) -> Map <Data-Map-Lazy.html#t:Map> k a -> t (Map<Data-Map-Lazy.html#t:Map> k b) So in practice what I do, and what I assume others do is this: mapM_ f (toList myMap) And I don't see any fusion rules that would ameliorate this (they seem limited to pure code), so I'm betting I always pay the cost of conversion to a list. In the case of Data.Map* the proposal is simply a "traverseWithKey_" that returns "t ()".* This follows the suffixing convention of mapM/mapM_ etc. More generally, it would be nice to do an audit of all popular containers with the assumption of very large collections that cant' be frivolously copied. -Ryan P.S. Actually, there are a number of places where the standard libraries could do with a more complete set of "_" functions -- e.g. it always chafes to not have "atomicModifyIORef_", which would apply a (a->a) function like a regular modifyIORef.

10 42

Proposal to solve the `EitherT` problem.
by Gabriel Gonzalez 15 Aug '13

15 Aug '13

As an application writer I'm a big fan of Edward's `either` package because his `EitherT` does not require an `Error` constraint. As a library writer, I am wary of heavy dependencies and I would prefer something more light-weight that I can depend on. Normally I would just directly contact Edward about reducing the number of dependencies but there was a previous discussion here about possibly merging his work into `transformers`, so I'm renewing that discussion and bringing up a few approaches for consideration. There are three approaches that I'd like to submit for consideration and receive feedback on: * Approach 1: Remove the `Error` constraint from `transformers` Disadvantage: This silently breaks all existing uses of `fail`. I don't know any way to add a compiler warning to notify downstream libraries of this change. * Approach 2: Add `EitherT` to `transformers` alongside `ErrorT` and have them both implement `MonadError`. Disadvantage: Bloat from having two almost identical monad transformers. However, there is precedent from duplicating `StateT`, `WriterT` and `RWST` for both strict and lazy instances. * Approach 3: Convince Edward to reduce the dependencies of the `either` package and submit the simplified version to the Haskell platform. Disadvantage: One extra import instead of just importing `transformers`. * Approach 4: None of the above. Disadvantage: Packages that depend on `either` have very low prospects of making it into the Haskell platform. If you have time, just take a moment to vote on which approach you favor or propose another alternative if you have another idea that I haven't listed.

17 36