- Libraries - Haskell.org

Data.Graph (and Data.Tree) improvements
by Edward Z. Yang 06 Mar '15

06 Mar '15

Data.Graph has always been a bit of an unloved module in containers. However, at GHC HQ the graph has always been a bit of an important data type, and we've been maintaining basically another version of the module under the name Digraph. I was refactoring this module to use Data.Graph and I noticed that there were a few functions which were conspicuously missing from the module proper. So here they are: For Data.Graph: - Generalized reachable :: Graph -> [Vertex] -> [Vertex] (compare to reachable :: Graph -> Vertex -> [Vertex] - Returns an undirected version of a graph which, for any edge a -> b, an edge b -> a also exists. undirected :: Graph -> Graph - Extract a list of groups of elements of a graph such that each group has no dependence except on nodes in previous groups (i.e. they may not depend on nodes in their own group) such that the groups are maximal. No solution exists for cyclic graphs vertexGroups :: Graph -> [[Vertex]] For Data.Tree - preorderF :: Forest a -> [a] (or perhaps flattenF, to keep naming consistent with existing flatten :: Tree a -> [a] which does a preorder) Furthermore, we have a few "low level" functions implementing algorithms for classifying edges, finding connected and biconnected components that were contributed by Sigbjorn Finne in 1997, although GHC does not use them. Finally, I think GHC's node-parametrized variant of graphs (to which it gives the name 'Graph', as opposed to Data.Graph style graphs which it calls 'IntGraph'; is far more useful to clients: data Graph node = Graph { gr_int_graph :: IntGraph, gr_vertex_to_node :: Vertex -> node, gr_node_to_vertex :: node -> Maybe Vertex } and I think it is well worth considering implementing this is the standard library. If no one else, GHC will happily use such an implementation. Thanks, Edward

1 0

fgl-5.5.0.1
by C Maeder 06 Mar '15

06 Mar '15

Hi Ivan, could you make a new release of fgl that works with ghc-7.10? I could compile it locally after the following changes: Data/Graph/Inductive/Query/Monad.hs +import Control.Applicative +import Control.Monad (ap, liftM) +instance Monad m => Functor (GT m g) where + fmap = liftM + +instance Monad m => Applicative (GT m g) where + pure = return + (<*>) = ap Data/Graph/Inductive/Monad/IOArray.hs -{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} +{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-} I'm not sure why FlexibleContexts is now needed and I'm not sure how the package version number should change. Cheers Christian

6 8

ApplicativeZip
by Oleg Grenrus 06 Mar '15

06 Mar '15

After Edward Kmett mentioned that we should add MonadZip to Data.Monoid instances, that got me thinking about: Why we don’t have ApplicativeZip? class Applicative f => ApplicativeZip f where {-# MINIMAL azip | azipWith #-} azip :: m a -> m b -> m (a,b) azip = azipWith (,) -- This is `liftA2` but can be done more efficiently for some instances (is it true?) azipWith :: (a -> b -> c) -> m a -> m b -> m c azipWith f = azip (uncurry f) aunzip :: m (a,b) -> (m a, m b) aunzip mab = (fst <$> mab, liftM <$> mab) and class (Monad m, ApplicativeZip m) => MonadZip m where mzip :: m a -> m b -> m (a,b) mzip = azip mzipWith :: (a -> b -> c) -> m a -> m b -> m c mzipWith = azipWith munzip :: m (a,b) -> (m a, m b) munzip = aunzip IMHO that should been done during AMP-reform, sorry if this topic is already discussed. - Oleg

1 0

On the scope of 'directory' (and which issue tracker to use)
by Phil Ruffwind 03 Mar '15

03 Mar '15

Looking at the current API, it seems that the 'directory' library has been extended to more than just mere directory-related operations: it includes several file-related utilities as well. It looks to me that 'directory' has become a place for consolidating filesystem-related operations for *nix and Windows platforms. Given the state of things, would it be more appropriate to call it a "platform-agnostic library for filesystem operations" rather than a "library for directory manipulation"? (Of course, the name of the library and its modules would remain slightly misleading but oh well.) On an unrelated issue, seeing as most of the issues are on GitHub rather than Trac (and I personally find the former simpler to use) perhaps the .cabal file should point to the GitHub issue tracker instead? -- Phil

2 1

Error -> Except migration
by Ganesh Sittampalam 03 Mar '15

03 Mar '15

Hi, In recent versions of transformers, 'ErrorT' has been deprecated in favour of 'ExceptT': https://hackage.haskell.org/package/transformers-0.4.2.0/docs/Control-Monad… This doesn't seem like a trivial like-for-like replacement since the implementation of 'fail' is different - in ErrorT it produces an exception within the ErrorT itself, and in ExceptT it just calls fail in the underlying monad. Is there any guidance or simple trick to find if a program is relying on the old behaviour? Otherwise migrating could be rather painful/dangerous, particularly as tests often don't cover exceptional cases well. I've spent a while searching for past discussion of the change, but haven't found anything, so please do point me at anything relevant if this has already been discussed. Cheers, Ganesh

2 2

Proposal to deprecate and then drop fromJust
by Erik de Castro Lopo 02 Mar '15

02 Mar '15

Hi all, We currently have in the Data.Maybe module from base: fromJust :: Maybe a -> a which newbies often find using hoogle or other search tools and is a huge trap. *Every* usage of the above can be replaced by using fromMaybe :: a -> Maybe a -> a which forces the user to provide a default value for the case where the Maybe a is a Nothing. The idea would be to deprecate fromMaybe for 7.12 and remove it completely later. Comments? Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

30 67

Re: [Haskell-cafe] A Proposed Law for Foldable?
by Gershom B 28 Feb '15

28 Feb '15

I think I can now float an amended law that is a further step in the right direction. First I will give the law, and then I will attempt to both motivate why the amended treatment is needed, and why the weakening of the initial proposal is a legitimate approach. Finally, I will discuss some remaining issues that it would be nice to examine, including some sketches of related but alternate approaches. So, the new law: === for a lawful Foldable f, and given a fresh newtype GenericSet = GenericSet Integer deriving (Eq, Ord), and mkGenericSet = GenericSet, where GenericSet is otherwise fully abstract then forall (g :: forall a. f a -> Maybe a), (x :: f GenericSet). maybe True (`Foldable.elem` x) (g x) === True == You may recall that the prior formulation asked that this condition hold for all a., (x :: f a), and so required an external notion of equality. Here, we ask that it only hold at a _specified type_ -- i.e. "GenericSet". So, in what sense was the older formulation "too strong"? Here is a minimal case. data TBox a where TAny :: a -> TBox a TString :: String -> TBox String TBox is just a box with some optional type information, and it should be able to be equipped with the obvious Foldable instance. However, we can now write a function such as discrim :: forall a. TBox a -> Maybe a discrim (TAny x) = Just x discrim (TString _) = "zoinks" This is to say that if we _know_ that TBox contains a string, we can now take _any_ string out of it. Clearly, the existence of such functions means that the obvious Foldable instance cannot satisfy the stronger law. By contrast, the straightforward Foldable instance for TBox still satisfies the weaker law, as we only test the action on "GenericSet" -- and since we have defined GenericSet as a fresh newtype, we know that it cannot have a tag to be matched on within a GADT we have already defined. Hence, our law, though it gives a universal property, does not give this property itself "universally" _at every type a_ but rather at a "generic type". This is by analogy with the technique of using "generic points" in algebraic geometry [1] to give properties that are not "everywhere true" but instead are true "almost everywhere", with a precise meaning given to "almost" -- i.e. that the space for which they do not hold _vanishes_. This is to say, a Foldable satisfying the proposed law will not have the property hold "at all types," but rather at "almost all types" for an analogously precise meaning of "almost". I believe that a statement of why GenericSet is indeed "generic" in some topological sense is possible, although I have not fully fleshed this out. To my knowledge, the introduction of this sort of approach in an FP context is new, but I would welcome any references showing prior art. Aside from dealing with GADTs in some fashion, the new approach has a few other useful features. First, by formulating things directly in terms of "Foldable.elem" we omit the need for some sort of notion of equality in the metalogic -- instead we can use the "Eq" typeclass directly. Furthermore, this happens to sidestep the "toList" problem in the initial approach -- it directly allows search of potentially infinite structures. There are still a few things that could potentially be better. 1) The "fully internal" approach means that we are now subject to the "bias" of "||" -- that is to say that _|_ || True -> _|_, but True || _|_ -> True. So we do not fully capture the searchability of infinite structures. This may indicate that a retreat to a metalogical description of "elem" with unbiased "or" is in order. 2) While we can generically characterize a Foldable instance on some f "almost everywhere" this is at the cost of giving it _no_ characterization at the points where our generic characterization fails. It would be nice to establish some sort of relation between the generic characterization and the action at specified points. However, I am not quite sure how to present this. An alternate approach could be to specify a Foldable law for any `f` that first takes `f` (which may be a GADT) to a related type `f1` (which must be an ordinary ADT) that squashes or omits dictionaries and equality constraints, and likewise takes the Foldable instance to a related instance on f1, and then provides a condition on f1. So rather that retreating from universal to generic properties, we instead take hold of the machinery of logical relations directly to establish a law. I would be interested in being pointed to related work along these lines as well. 3) An additional drawback of the "Generic Point" approach as given is that we chose to derive only two particular typeclasses -- Eq and Ord. An alternate approach would be to quantify over all a, but then give the property in terms of say "newtype Generify a = Generify a deriving (...)" which derives all classes on "a" that do not feature "a" in a positive position. Doing this would also mean a retreat from a fully internal notion of equality, of course... Anyway, this is clearly still work in progress, but I would appreciate any feedback on the direction this is going, or references that may seem useful. Cheers, Gershom [1] https://en.wikipedia.org/wiki/Generic_point On Thu, Feb 12, 2015 at 6:33 PM, Edward Kmett <ekmett(a)gmail.com> wrote: > With Foldable we *do* have a very nice law around foldMap. > > A monoid homomorphism g is a combinator such that > > g mempty = mempty > g (mappend a b) = mappend (g a) (mappend (g b) > > For any monoid homomorphism g, > > foldMap (g . f) = g . foldMap f > > We can use that to construct proofs of an analogue to "the banana split > theorem" for foldr, but rephrased in terms of foldMap: > > foldMap f &&& foldMap g = foldMap (f &&& g) > > Getting there uses the fact that fst and snd are both monoid homomorphisms. > > There are also laws relating the behavior of all of the other combinators > in Foldable to foldMap. > > Ultimately the reasons for the other members of the class are a sop to > efficiency concerns: asymptotic factors in terms of time or stack usage > matter. > > -Edward > > > On Thu, Feb 12, 2015 at 5:22 PM, Kim-Ee Yeoh <ky3(a)atamo.com> wrote: > >> (removing Libraries, since not everyone on HC is on that list) >> >> I do not know all of the context of Foldable, but one I do know that's >> not been mentioned is the implicit rule-of-thumb that every type class >> should have a law. >> >> So the undercurrent is that if Foldable doesn't have a law, should it >> even be a type class? This has led to efforts to uncover laws for Foldable. >> >> Worth discussing in a separate thread is the criterion itself of "if it >> doesn't have a law, it's not a type class". Useful sometimes, but that's >> not the sine qua non of type classes. >> >> >> >> -- Kim-Ee >> >> On Fri, Feb 13, 2015 at 2:47 AM, 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 10

Proposal: Functor and friends for the wrappers in Data.Monoid
by Oleg Grenrus 24 Feb '15

24 Feb '15

I propose to add Functor, Applicative, Monad, Foldable, and Traversable and maybe even MonadFix instances to wrapper newtypes in the Data.Monoid module. The same way as in the semigroups package, e.g. https://hackage.haskell.org/package/semigroups-0.16.1/docs/Data-Semigroup.h… <https://hackage.haskell.org/package/semigroups-0.16.1/docs/Data-Semigroup.h…> Basically: instance Functor Sum where fmap f (Sum x) = Sum (f x) instance Foldable Sum where foldMap f (Sum a) = f a instance Traversable Sum where traverse f (Sum a) = Sum <$> f a instance Applicative Sum where pure = Sum a <* _ = a _ *> a = a Sum f <*> Sum x = Sum (f x) instance Monad Sum where return = Sum _ >> a = a Sum a >>= f = f a instance MonadFix Sum where mfix f = fix (f . getSum)

11 23

GHC 7.10 will use Plan FTP
by Simon Peyton Jones 23 Feb '15

23 Feb '15

Colleagues You will remember (see this email<https://mail.haskell.org/pipermail/libraries/2015-February/024925.html>) that the Haskell community has been engaged in a debate about proposed changes to the Haskell Prelude, the Plan-List or Plan-FTP debate<https://ghc.haskell.org/trac/ghc/wiki/Prelude710>. We decided to hold an open survey to get feedback from the community. Simon Marlow and Simon PJ were asked to make a decision in the light of that feedback. The survey closed on 21 Feb, so it's time to decide. Bottom line: we recommend Plan FTP. There are strong arguments in both directions. For the record, our own personal instincts were both in the conservative, Plan List direction. But the survey gave some pretty compelling feedback, and was far more unequivocal than we expected. Some details * Over 800 people participated in the survey. That's a lot for an 11-day window. Many wrote several paragraphs of supporting information. Thank you for participating so actively! * Overall, 82% of respondents were in favour of FTP, a 4:1 majority. Simon and I found this level of unanimity quite surprising - and it made our task much easier. We clearly under-estimated the Haskell community's appetite for absorbing change when they approve of the direction of travel. * Herbert helped us by doing a rough categorisation into hobbyist/non-hobbyist responses. o The first interesting fact is that there were a lot of non-hobbyist responses: in fact a majority (58%) of the responses were from non-hobbyists. So increasingly people are using Haskell for real work. o The support for Plan FTP among hobbyists was overwhelming (over 87%). But it was still very strong indeed among non-hobbyists (over 79%). Caveat: time was short, so the hobby/non-hobby categorisation is extremely approximate. But since the results are so unambiguous, even the crude results are helpful. * We tried filtering out responses that were blank in the name field and both text boxes. The 82% majority did not budge. What happens now * GHC 7.10 will embody Plan FTP. * The Core Libraries committee, freshly energised and informed by this episode, is drafting new guidelines to clarify what it does, and how it works; and to help avoid a repetition of the recent drama. * The responses. In the survey we said "We won't publish either textual responses or personally-identifying information without your consent. The full responses will be made available only to a limited few." However, the English-language comments are a remarkable snapshot of the Haskell community, and it would be a shame to discard them without deeper study. We propose to make them available to the Core Libraries Committee, to inform their future choices. If anyone else wants to digest the comments into a summary report, we think that would be a service to the community, and (in our view, provided they are a reputable person etc) would fall under the "available to a limited few" rubric. If that appeals to you, write to us. If you object even to such limited sharing, write to us too. This wasn't an entirely easy process, especially because it happened so late in the release cycle. But although many people felt quite strongly about List vs FTP, the whole debate has involved light rather than heat; people have concentrated on the technical issues, rather than yelling. Overall, it's been very encouraging to see the resilience, transparency, and constructive tone of the community. We really appreciate that - thank you. Simon Marlow and Simon Peyton Jones

1 0

openBinaryTempFile
by Ben Franksen 21 Feb '15

21 Feb '15

We are using this function from base in Darcs in a way that causes trouble: the returned file handle is closed immediately and only the filename is passed on. Then the file gets re-opened and closed again and some time later deleted. If openBinaryTempFile is used in this way a few times in a row, it returns the same file name every time. I tested this with a small test program. My question: is openBinaryTempFile supposed to behave like that (if used in this way)? I am testing this on an ubuntu trusty with ghc-7.6.3, meaning base-4.6.0.1. Has the function been changed in later versions? Cheers Ben -- "There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." ― C.A.R. Hoare

2 3