- Libraries - Haskell.org

Proposal: Foldable typeclass: make foldl' and foldr' class methods
by Duncan Coutts 20 Jun '11

20 Jun '11

All, This issue was brought up again recently by Milan's questions about what to do with folds for the containers package. Currently the Foldable type class has: class Foldable t where fold :: Monoid m => t m -> m foldMap :: Monoid m => (a -> m) -> t a -> m foldr :: (a -> b -> b) -> b -> t a -> b foldl :: (a -> b -> a) -> a -> t b -> a foldr1 :: (a -> a -> a) -> t a -> a foldl1 :: (a -> a -> a) -> t a -> a with default implementations for each in terms of the others. Then it defines: foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b foldr' f z0 xs = foldl f' id xs z0 where f' k x z = k $! f x z foldl' :: Foldable t => (a -> b -> a) -> a -> t b -> a foldl' f z0 xs = foldr f' id xs z0 where f' x k z = k $! f z x That is, they are fixed definitions so specialised implementations cannot be provided. Note also that these are the classic higher-order "foldl in terms of foldr" definitions. Current releases of GHC cannot optimises these higher-order definitions into efficient versions using accumulating parameters. Since one of the main purposes of foldl' is performance (other purpose being to avoid space leaks) then that's rather unfortunate. The proposal is simple: move these two functions into the Foldable type class itself. They would keep their existing default definitions but since they are then class methods they can have efficient implementations provided by the class instances. This should not break much code. In particular it should not break existing type class instance declarations since there is a default definition for instances that don't defined the new methods. The only potential breakage is that foldl' and foldr' are exported via Foldable(..) rather than directly. This could affect modules that use explicit imports. (I consider this fact to be a slightly unfortunate quirk of the Haskell module system). Patch attached. Deadline: 2 weeks: Monday 4th July. Unresolved: what is a good concise specification of foldr' to use in the documentation? For foldl' we can say: foldl' f z = List.foldl' f z . toList Related issues not covered by this simple proposal: providing foldl1' and foldr1', updating instances to define foldl' and foldr' if possible (e.g. array could provide an efficient impl of foldr'). Duncan

6 10

Re: Proposal: Foldable typeclass: make foldl' and foldr' class methods
by wren ng thornton 20 Jun '11

20 Jun '11

On 6/20/11 3:14 PM, Dan Doel wrote: > Actually, the prelude doesn't contain foldl', because it wasn't in Haskell 98. You only get it from Data.List. Ah, my bad. It comes loaded by default on my GHCi so I figured Prelude. It's been a while since I actually looked in there <chagrin/> (The breakage would look about the same, only it's even less likely now) -- Live well, ~wren

1 0

Re: Proposal: Foldable typeclass: make foldl' and foldr' class methods
by wren ng thornton 20 Jun '11

20 Jun '11

On 6/20/11 2:21 PM, Antoine Latter wrote: > On Mon, Jun 20, 2011 at 12:02 PM, Duncan Coutts wrote: >> >> This should not break much code. In particular it should not break >> existing type class instance declarations since there is a default >> definition for instances that don't defined the new methods. >> >> The only potential breakage is that foldl' and foldr' are exported via >> Foldable(..) rather than directly. This could affect modules that use >> explicit imports. (I consider this fact to be a slightly unfortunate >> quirk of the Haskell module system). > > What would the broken code look like? Broken code would look like GHC complaining that uses of foldl' (or foldr') are ambiguous between the Prelude and Data.Foldable. The ambiguity is introduced by import Data.Foldable (Foldable(..), {-...-}) where the ... does not include foldl' or foldr' and we did not explicitly: import Prelude hiding (foldl', foldr', {-...-}) or use -XNoImplicitPrelude, or import Prelude qualified, or... ... ... Honestly, it's a really bizarre corner case that this would even happen since often folks will be importing Data.Foldable qualified or will be importing everything it offers and hiding it from Prelude. In the event breakage occurs, it's obvious what went wrong and how to fix it. Backwards compatibility shouldn't even be much of an issue since you can just add the imports outside of the (..). The only backwards compatibility issue is folks wanting to give definitions to these new methods, but the standard CPP hackery can be used to work around that. -- Live well, ~wren

1 0

Various folds in the containers package
by Milan Straka 20 Jun '11

20 Jun '11

Hi all, currently we have the following folds in the containers package: Map: fold, foldWithKey, foldrWithKey, foldlWithKey Set: fold IntMap; fold, foldWithKey IntSet: fold If the direction (right, left) is not specified, the fold is the right fold. So currently we have no left folds (except for the Map) and also Map and IntMap are not consistent. There are several issues I am thinking about: a) we could left and right folds. For the Set and IntSet it is simple -- we can add foldr and foldl, and deprecated fold with the message 'use foldr instead'. For the Map and IntMap it is not so simple -- should we add both foldr, foldl, foldlWithKey and foldrWithKey? b) we could use the Foldable instances more. We can implement foldr and foldl efficiently and let the users to use those instead of providing eg Set.foldr, Set.foldl. This does not cover the *WithKey variant, as the Foldable instances over Map and IntMap does not utilize the key. c) strict folds. If we add also strict folds, we would have a total of _four_ folds in Set and IntSet and __eight__ folds in Map and IntMap. The Foldable module exports foldl' and foldr', which use foldr, foldl respectively, but needs some intermediate memory (it creates a thunk for every node of the structure). Apart from that, this does not cover the *WithKey variants as in b). Personally I would add foldr, foldl, foldlWithKey, foldrWithKey and specialised foldr, foldl implementations in the Foldable classes. I am not sure about the strict folds -- I used an equivalent of the foldr' from the Foldable module in GHC and it was reasonable fast. Any oppinions? Cheers, Milan

6 10

Built failure on Hackage due to missing libraries
by Boris Lykah 17 Jun '11

17 Jun '11

Hi everyone! Recently I uploaded package to Hackage (http://hackage.haskell.org/package/groundhog-0.0.1) and it failed with an error as if the libraries monad-control and pool were not exposed. What is the current situation with these libraries? According to Cabal FAQ this could mean that they were built with --user flag while my package is built with --global or they are not exposed at all. -- Regards, Boris

3 2

Re: Various folds in the containers package
by wren ng thornton 16 Jun '11

16 Jun '11

On 6/15/11 8:43 AM, Duncan Coutts wrote: > Do provide a Foldable instance, +1. > and perhaps later we can lobby for foldl' and foldr' to be > made members of the Foldable class rather than fixed definitions in terms of foldl and foldr (bytestring, vector and text could benefit from this too). +1. -- Live well, ~wren

1 0

HP: GUI
by Guy 12 Jun '11

12 Jun '11

Software frequently requires a graphical user interface. Haskell has 2 major GUI packages (gtk and wx), but both are difficult to install, at least on Windows. Including a GUI library with HP, or even as a separate download, would make Haskell GUI programming much more accessible.

2 1

Proposal: Make gcd total
by Daniel Fischer 11 Jun '11

11 Jun '11

Reposting to libraries, since I was advised that this would be the correct place, and not haskell-prime, as I assumed because it would change behaviour specified in the language report. The proposal has been made earlier and received widespread support, but it was never finished. This time, on the haskell-prime list, http://www.haskell.org/pipermail/haskell-prime/2011-May/003403.html, Jaques Carette and Cale Gibbard already recorded their support. Discussion period: two weeks, until 11. June 2011. An old and reopened ticket is at: http://hackage.haskell.org/trac/ghc/ticket/3304 The Proposal: I would like to propose the elimination of the special error case gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" to replace it with gcd 0 0 = 0 (which would be an automatic consequence of removing the above line). Rationale: 1. It makes gcd a total function. 2. It makes gcd associative. 3. It makes folding gcd over a list safe. 4. It conforms to common mathematical practice: In a commutative ring, a greatest common divisor of two elements a, b is a common divisor g of a and b such that every common divisor d of a and b also divides g (if R is a commutative ring, a \in R, d \in R is a divisor of a iff there exists c \in R with a = d*c [leaving out noncommutative rings for simplicity]). Since every ring element divides 0, the above definition entails gcd 0 0 = 0. Further, in a principal ideal ring, the greatest common divisors of two elements a and b are the generators of the ideal (a,b), again that characterisation of greatest common divisors says gcd 0 0 = 0: (0,0) = {0} = (0). Pros: see above. Cons: ? I'm not aware of any, the change shouldn't break existing code, since that would have to check for the special case anyway. There is, however, a difficulty with the documentation. Reading the old threads about the topic (thanks to Judah Jacobson for the links): http://www.haskell.org/pipermail/haskell/2001-December/008560.html http://www.haskell.org/pipermail/haskell-cafe/2009-May/060880.html made me aware that many (probably most) people, upon reading 'greatest' in 'greatest common divisor', think it refers to the natural order of integers and not the divisibility preorder. Of course, historically it did, but since the concept has been expanded to rings which have no natural order, it can't anymore (and even in rings which have a natural order, like Z[sqrt 2], the term 'greatest' can't refer to the natural order if the ring has units > 1). It is not difficult to explain this given enough space, but I don't know yet how to fit it in the limited space a reasonable function documentation provides. Suggestions how to formulate it are welcome. Daniel

4 5

New libraries process
by Simon Peyton-Jones 08 Jun '11

08 Jun '11

Friends Last month Simon M and I put forward a proposal to revise the process for developing the Core Haskell libraries: http://www.haskell.org/haskellwiki/Library_submissions/NewDraft There was some discussion, leading to improvements now incorporated in the draft, but I believe that there was general support; indeed no one opposed the change. Several weeks have gone by, so I suggest that we adopt the new process forthwith. Unless I hear otherwise I'll replace http://www.haskell.org/haskellwiki/Library_submissions with the new process in a day or two. We still need volunteers to become the maintainer of mtl random [though I think someone maybe did volunteer, Daniel perhaps?] Win32 Please! best wishes Simon

5 5

Proposal: add 'partitionM' to Control.Monad module
by Heka Treep 08 Jun '11

08 Jun '11

filterM is already exist, partitionM is quite similar: -- | This generalizes the list-based 'partition' function. partitionM :: (Monad m) => (a -> m Bool) -> [a] -> m ([a], [a]) partitionM _ [] = return ([], []) partitionM p (x:xs) = do test <- p x (ys, ys') <- partitionM p xs return $ if test then (x:ys, ys') else (ys, x:ys')

1 0