- Libraries - Haskell.org

Re: Seeking an active maintainer for 'directory'
by Edward Kmett 17 Feb '15

17 Feb '15

And we have a winner. Thanks, Phil. If you need any help from the core libraries committee, just ask; we'll support your efforts however we can. -Edward On Tue, Feb 17, 2015 at 2:25 PM, Phil Ruffwind <rf(a)rufflewind.com> wrote: > > Is anybody interested in nominating themselves for this role? > > I would be interested in this. I'm generally quite meticulous :) and > I'm familiar with the APIs of both POSIX and Win32, albeit more so > with POSIX. > > -- > Phil >

3 4

Overloadable list type notation
by Greg Weber 17 Feb '15

17 Feb '15

I had an idea whose goal is to ease people into Foldable, Traversable, etc. There could be a notation that shows the generalization that is occurring. map :: Functor [_] => (a -> b) -> [a] -> [b] This means that the syntax for the list type is now syntax for the variable created by the Functor constraint. Adding such a thing to the language is probably not a good idea, but someone might possibly like such a notation for pedagogy. Of course, it will be pointed out that a Functor is not just a container. But Foldable is sometimes expressed as "anything that toList can be called on", so it should make sense there. Greg Weber

6 10

Seeking an active maintainer for 'directory'
by Edward Kmett 17 Feb '15

17 Feb '15

The 'directory' package could use an active maintainer. Currently, the package falls to the Core Libraries Committee for maintenance, but we've had a number of issues accrete for the directory package over the last six months or so, which need some attention to detail and a good understanding of cross-platform issues. Is anybody interested in nominating themselves for this role? -Edward

1 0

Re: [Haskell-cafe] A Proposed Law for Foldable?
by Edward Kmett 13 Feb '15

13 Feb '15

There are 3 cases ruled out by this law. Two of them I'd have no trouble seeing go, the third one I think damages it beyond repair. First, `foldMap = mempty` is currently an admissable definition of foldMap for anything that is not Traversable. The law effectively talks backwards and ensures that you have to give back info on every 'a' in the container, so this is ruled out for any container that actually 'contains' an a. I'm pretty much okay with that case being ruled out. Second, There are instances such as the Foldable instance for `Machine` in the machines package. Here it starves the machine for input and takes the output and folds over it. However, these are not 'all of the 'a's it is possible to generate with such a machine, as you can construct a function (Machine ((->) b) a -> Maybe a) that feeds the machine a 'b' and then gets out an 'a' that would not occur in toList. One could argue that this Foldable violates the spirit of Foldable. I'm somewhat less okay with that case being ruled out as folks have found it useful, but I could accept it. Third, In the presence of GADTs, the fact that Foldable only accepts 'f' in negative position means that 'f' might be a GADT, telling us more about `a`, despite your function being parametric. e.g. it could carry around a Num constraint on its argument. Extracting this dictionary from the GADT would enable sum :: Num a => f a -> a to be used in your function (forall a. f a -> Maybe a), preventing parametricity from providing the insurance you seek. This means that your law would rule out any `Foldable` that exploits GADT-like properties. A version of `Set` where the data type carries around the `Ord` instance internally, could for instance instantiate `elem` in log time. That example becomes only marginally safe under your law because of `min` and `max` being in Ord and producing "new" a's, but it also rules out similar O(1) optimizations for sum or product in other potential containers, which could carry Num. These I'm much more reluctant to let go. You might be able to repair your law by also quantifying over `f` with a Foldable constraint or some such, but that re-admits the former 2 laws and seems to make it vacuous. -Edward On Thu, Feb 12, 2015 at 2:59 PM, Atze van der Ploeg <atzeus(a)gmail.com> wrote: > Hi Gershom! > > Do you have an example where this law allows us to conclude something > interesting we otherwise would not have been able to conclude? > > Cheers, > > Atze > On Feb 12, 2015 8:47 PM, "Gershom B" <gershomb(a)gmail.com> wrote: > >> For a long time, many people, including me, have said that "Foldable has >> no laws" (or Foldable only has free laws) -- this is true, as it stands, >> with the exception that Foldable has a non-free law in interaction with >> Traversable (namely that it act as a proper specialization of Traversable >> methods). However, I believe that there is a good law we can give for >> Foldable. >> >> I earlier explored this in a paper presented at IFL 2014 but (rightfully) >> rejected from the IFL post-proceedings. ( >> http://gbaz.github.io/slides/buildable2014.pdf) That paper got part of >> the way there, but I believe now have a better approach on the question of >> a Foldable law -- as sketched below. >> >> I think I now (unlike in the paper) can state a succinct law for Foldable >> that has desired properties: 1) It is not "free" -- it can be violated, and >> thus stating it adds semantic content. 2) We typically expect it to be >> true. 3) There are no places where I can see an argument for violating it. >> >> If it pans out, I intend to pursue this and write it up more formally, >> but given the current FTP discussion I thought it was worth documenting >> this earlier rather than later. For simplicity, I will state this property >> in terms of `toList` although that does not properly capture the infinite >> cases. Apologies for what may be nonstandard notation. >> >> Here is the law I think we should discuss requiring: >> >> * * * >> Given Foldable f, then >> forall (g :: forall a. f a -> Maybe a), (x :: f a). case g x of Just a >> --> a `elem` toList x >> * * * >> >> Since we do not require `a` to be of type `Eq`, note that the `elem` >> function given here is not internal to Haskell, but in the metalogic. >> >> Furthermore, note that the use of parametricity here lets us make an "end >> run" around the usual problem of giving laws to Foldable -- rather than >> providing an interaction with another class, we provide a claim about _all_ >> functions of a particular type. >> >> Also note that the functions `g` we intend to quantify over are functions >> that _can be written_ -- so we can respect the property of data structures >> to abstract over information. Consider >> >> data Funny a = Funny {hidden :: a, public :: [a]} >> >> instance Foldable Funny where >> foldMap f x = foldMap f (public x) >> >> Now, if it is truly impossible to ever "see" hidden (i.e. it is not >> exported, or only exported through a semantics-breaking "Internal" module), >> then the Foldable instance is legitimate. Otherwise, the Foldable instance >> is illegitimate by the law given above. >> >> I would suggest the law given is "morally" the right thing for Foldable >> -- a Foldable instance for `f` should suggest that it gives us "all the as >> in any `f a`", and so it is, in some particular restricted sense, initial >> among functions that extract as. >> >> I do not suggest we add this law right away. However, I would like to >> suggest considering it, and I believe it (or a cleaned-up variant) would >> help us to see Foldable as a more legitimately lawful class that not only >> provides conveniences but can be used to aid reasoning. >> >> Relating this to adjointness, as I do in the IFL preprint, remains future >> work. >> >> Cheers, >> Gershom >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

4 7

A Proposed Law for Foldable?
by Gershom B 12 Feb '15

12 Feb '15

For a long time, many people, including me, have said that "Foldable has no laws" (or Foldable only has free laws) -- this is true, as it stands, with the exception that Foldable has a non-free law in interaction with Traversable (namely that it act as a proper specialization of Traversable methods). However, I believe that there is a good law we can give for Foldable. I earlier explored this in a paper presented at IFL 2014 but (rightfully) rejected from the IFL post-proceedings. ( http://gbaz.github.io/slides/buildable2014.pdf) That paper got part of the way there, but I believe now have a better approach on the question of a Foldable law -- as sketched below. I think I now (unlike in the paper) can state a succinct law for Foldable that has desired properties: 1) It is not "free" -- it can be violated, and thus stating it adds semantic content. 2) We typically expect it to be true. 3) There are no places where I can see an argument for violating it. If it pans out, I intend to pursue this and write it up more formally, but given the current FTP discussion I thought it was worth documenting this earlier rather than later. For simplicity, I will state this property in terms of `toList` although that does not properly capture the infinite cases. Apologies for what may be nonstandard notation. Here is the law I think we should discuss requiring: * * * Given Foldable f, then forall (g :: forall a. f a -> Maybe a), (x :: f a). case g x of Just a --> a `elem` toList x * * * Since we do not require `a` to be of type `Eq`, note that the `elem` function given here is not internal to Haskell, but in the metalogic. Furthermore, note that the use of parametricity here lets us make an "end run" around the usual problem of giving laws to Foldable -- rather than providing an interaction with another class, we provide a claim about _all_ functions of a particular type. Also note that the functions `g` we intend to quantify over are functions that _can be written_ -- so we can respect the property of data structures to abstract over information. Consider data Funny a = Funny {hidden :: a, public :: [a]} instance Foldable Funny where foldMap f x = foldMap f (public x) Now, if it is truly impossible to ever "see" hidden (i.e. it is not exported, or only exported through a semantics-breaking "Internal" module), then the Foldable instance is legitimate. Otherwise, the Foldable instance is illegitimate by the law given above. I would suggest the law given is "morally" the right thing for Foldable -- a Foldable instance for `f` should suggest that it gives us "all the as in any `f a`", and so it is, in some particular restricted sense, initial among functions that extract as. I do not suggest we add this law right away. However, I would like to suggest considering it, and I believe it (or a cleaned-up variant) would help us to see Foldable as a more legitimately lawful class that not only provides conveniences but can be used to aid reasoning. Relating this to adjointness, as I do in the IFL preprint, remains future work. Cheers, Gershom

1 0

Discussion: Add unboxed mutable references somewhere sensible
by David Feuer 12 Feb '15

12 Feb '15

The problem they solve is perhaps not as well known as it should be: Code that frequently modifies an `STRef Int`, for example, will typically surprise the programmer by allocating a ton of memory. This happens because the reference holds a *boxed* Int. Code like modifySTRef ref (+1) will allocate a new Int box every time. To the best of my knowledge, GHC makes no attempt to figure out if this is actually necessary and do something about it. The Data.Ref.Unboxed module in the ArrayRef package attempts to address this, but it doesn't seem to get much visibility, and its code hasn't been touched since 2009. What can we do about this?

4 7

Drastic Prelude changes imminent
by Augustsson, Lennart 11 Feb '15

11 Feb '15

The next version (7.10) of GHC is slated to have a drastically changed Prelude. This message is very late in the release process, but I would urge caution before changing. The changes are (aptly) named the Burning Bridges Proposal (BBP). Even though the work has been going on for a while, it seems that this change is coming as a surprise to many people (including Simon Peyton Jones). In summary, it generalizes many list operation, e.g., foldr, to be overloaded. There is much to welcome in BBP, but changing the Prelude cannot be done lightly since it really is like changing the language. So I think it's really important for a large number of people to be able to try out such changes before they come into effect, and to have time to let the changes stabilize (you rarely get it right the first time). I've discussed this with a number of people, including Simon PJ, and we have concrete proposals. Proposal 1: * Add a new pragma {-# LANGUAGE Prelude=AlternativePrelude #-} * This is a new feature, but it is easy and low-risk to implement. * Which Prelude you use really is a language choice; appropriate for a LANGUAGE pragma. * Semantics is name-space only: import Prelude (); import AlternativePrelude * No effect on desugaring or typing of built-in syntax (list comprehensions, do-notation etc). * Ship with both old and new prelude. * So now old and new behaviour are easy to achieve, in the module or in a .cabal file. * The question becomes "what is the default". Proposal 2: * Make the default be the old rather than the new. * Altering the default Prelude API should be done slowly, with lots of warning; because all users get it willy-nilly. * Unlike AMP, the change is controversial (clearly). * Easier to make changes to New Prelude if it isn't the default. That's it. Discussing the BBP proposal we also came up with a number of technical questions: Q1 An alternative to Foldable would be class Enumerable t where toList :: t a -> [a] -- Implementations should use 'build' Is Foldable more general (or efficient) than a Enumerable class, plus fusion? Consider a new data type X a. I write foldX :: (a -> b -> b) -> b -> X a -> b foldX = ...lots of code... toList :: X a -> [a] {-# INLINE toList #-} toList x = build (\c n. foldX c n x) So now toList is small and easy to inline. Every good list consumer of a call to toList will turn into a call to foldX, which is what we want. Q2 What are the criteria for being in Foldable? For instance, why are 'sum', 'product' in Foldable, but not 'and', 'or'? Q3 What's the relationship of Foldable to GHC.Exts.IsList? Which also has toList, fromList, and does work with ByteString. * For example, could we use IsList instead of Foldable? Specifically, Foldable does not use its potential power to apply the type constructor t to different arguments. (Unlike Traversable which does.) foldr :: IsList l => (Item l->b->b) -> b -> l -> b -- Lennart This email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please delete all copies and notify the sender immediately. You may wish to refer to the incorporation details of Standard Chartered PLC, Standard Chartered Bank and their subsidiaries at http://www.standardchartered.com/en/incorporation-details.html Insofar as this communication contains any market commentary, the market commentary has been prepared by a sales and/or trading desk of Standard Chartered Bank or its affiliate. It is not and does not constitute research material, independent research, recommendation or financial advice. Any market commentary is for information purpose only and shall not be relied for any other purpose, and is subject to the relevant disclaimers available at http://wholesalebanking.standardchartered.com/en/utility/Pages/d-mkt.aspx. Please visit http://wholesalebanking.standardchartered.com/en/capabilities/financialmark… for important information with respect to derivative products.

39 120

GHC 7.10 Prelude: we need your opinion
by Simon Peyton Jones 10 Feb '15

10 Feb '15

[You have probably seen this already, but I stupidly failed to cross-post it to libraries(a)haskell.org<mailto:libraries@haskell.org>, and am now doing so. libraries@ is actually the right list for debate about the issues.] Haskell Friends This email asks for your help in deciding how to proceed with some Prelude changes in GHC 7.10. Please read on, but all the info is also at the survey link, here: http://goo.gl/forms/XP1W2JdfpX. Deadline is 21 Feb. The Core Libraries Committee (CLC) is responsible for developing the core libraries that ship with GHC. This is an important but painstaking task, and we owe the CLC a big vote of thanks for taking it on. For over a year the CLC has been working on integrating the Foldable and Traversable classes (shipped in base in GHC 7.8) into the core libraries, and into the Prelude in particular. Detailed planning for GHC 7.10 started in the autumn of 2014, and the CLC went ahead with this integration. Then we had a failure of communication. As these changes affect the Prelude, which is in scope for all users of Haskell, these changes should be held to a higher bar than the regular libraries@ review process. However, the Foldable/Traversable changes were not particularly well signposted. Many people have only recently woken up to them, and some have objected (both in principle and detail). This is an extremely unfortunate situation. On the one hand we are at RC2 for GHC 7.10, so library authors have invested effort in updating their libraries to the new Prelude. On the other, altering the Prelude is in effect altering the language, something we take pretty seriously. We should have had this debate back in 2014, but here we are, and it is unproductive to argue about whose fault it is. We all share responsibility. We need to decide what to do now. A small group of us met by Skype and we've decided to do this: · Push back GHC 7.10's release by at least a month, to late March. This delay also gives us breathing space to address an unrelated show-stopping bug, Trac #9858. · Invite input from the Haskell community on which of two approaches to adopt (this survey<http://goo.gl/forms/XP1W2JdfpX>). The main questions revolve around impact on the Haskell ecosystem (commercial applications, teaching, libraries, etc etc), so we want to ask your opinion rather than guess it. · Ask Simon Marlow and Simon Peyton Jones to decide which approach to follow for GHC 7.10. Wiki pages have been created summarizing these two primary alternatives, including many more points and counter-points and technical details: · Overall summary: https://ghc.haskell.org/trac/ghc/wiki/Prelude710<https://www.google.com/url?q=https%3A%2F%2Fghc.haskell.org%2Ftrac%2Fghc%2Fw…> · Details of Plan List: https://ghc.haskell.org/trac/ghc/wiki/Prelude710/List<https://www.google.com/url?q=https%3A%2F%2Fghc.haskell.org%2Ftrac%2Fghc%2Fw…> · Details of Plan FTP: https://ghc.haskell.org/trac/ghc/wiki/Prelude710/FTP<https://www.google.com/url?q=https%3A%2F%2Fghc.haskell.org%2Ftrac%2Fghc%2Fw…> This survey invites your input on which plan we should follow. Would you please · Read the details of the alternative plans on the three wiki pages above · Add your response to the survey<http://goo.gl/forms/XP1W2JdfpX> Please do read the background. Well-informed responses will help. Thank you! DEADLINE: 21 February 2015 Simon PJ

1 0

Data.Graph nitpicks
by Andreas Voellmy 10 Feb '15

10 Feb '15

Hi folks, I was just using the stronglyConnComp function in Data.Graph and found some minor annoying things: 1. stronglyConnComp takes an out-list as input. On the other hand, none of the other graph algorithms, like dfs, etc do this. stronglyConnComp seems to basically be an algorithm on graphs, so why doesn't it take the graph as input? Can we change stronglyConnComp to take a graph as input? That would make the interface more uniform. 2. Why is stronglyConnComp in a special haddock section whereas all the other algorithms are in the "Algorithms" section? How about we group it with all the other algorithms? 3. Why are there are so few instances of SCC? In particular, why not derive Show and Eq? Cheers, Andi

3 2

Re: Drastic Prelude changes imminent
by malcolm.wallace 04 Feb '15

04 Feb '15

Perhaps this discomfort points to another possible way forward: remove from the Prelude all functions that were formerly list-y, and now Foldable/Traversable. Make it so that you must import Data.List if you want the List versions, or Data.Foldable if you want the generalised versions. Of course, it would be a change causing a lot of breakage in existing code, but then, I have never experienced a major release of ghc that did not break existing code. Regards, Malcolm On 04 Feb, 2015,at 04:14 PM, Christopher Done <chrisdone(a)gmail.com> wrote: Looking at the generalizations in Data.List I find them pretty odd now when I think about it. I'd expect Data.List functions to be monomorphic to lists, just like I expect functions in Data.Map to be monomorphic to maps. Now there might be generalized versions of these functions in e.g. the Prelude, but generalizing Data.List means that I don't even have the monomorphic versions available if I want to resolve ambiguity by using them*. Sums up my feelings exactly. Data.Map, Data.List, etc. should be monomorphic. Adding generalized functions in Data.List is a little baffling. _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://www.haskell.org/mailman/listinfo/libraries

2 1