- Libraries - Haskell.org

Re: Formal proposal: replace Data.List.inits
by David Feuer 06 Sep '14

06 Sep '14

Minor errors in copying/memory: initsHO = map ($[]) . scanl q id where q f x = f . (x :) On Sun, Jul 20, 2014 at 2:03 AM, David Feuer <david.feuer(a)gmail.com> wrote: > As previously discussed, Data.List.inits has terrible performance: > something as simple as > > print $ length $ inits [100000] > > will take an absurdly long time. The simplest decent improvement seems to be > > initsHO = map ($[]) . scanl q [] > where > q f x = f . (q :) > > A slight transformation of this by Andrew Seniuk (rasfar on #haskell) > gives the slightly faster > > initsR = map reverse . scanl (flip (:)) [] > > As Henning Thielemann and Edward Kmett pointed out, these perform > poorly when calculating things like `map head $ drop 100000 $ inits > [100050]` because the costs of the reverses or compositions are > monolithic and unshared. Edward Kmett pointed out that this could > probably be fixed by using a queue (although he isn't sure it's worth > doing so). As it turns out, it can, and with only a trivial penalty in > other cases. The following uses a stripped-down partial implementation > of Okasaki's banker's queue (see the attached file for a version with > explanatory comments as well as the benchmark code): > > import Data.Bits (popCount) > import Data.Word (Word) > > data Queue a = Queue {-# UNPACK #-} !Word [a] [a] > > queue :: Word -> [a] -> [a] -> Queue a > queue lp1 f r > | popCount lp1 /= 1 = Queue lp1 f r > | otherwise = Queue lp1 (f ++ reverse r) [] > > emptyQ :: Queue a > emptyQ = Queue 1 [] [] > > snocQ :: Queue a -> a -> Queue a > snocQ (Queue lp1 f r) x = queue (lp1 + 1) f (x:r) > > toListQ :: Queue a -> [a] > toListQ (Queue _ f r) = f ++ reverse r > > initsQ :: [a] -> [[a]] > initsQ = map toListQ . scanl snocQ emptyQ > > > This implementation appears to take care of the performance wrinkle in > initsR and initsHO, while being only very slightly slower in other > contexts. It's longer, certainly, but it's not long. > > I have attached the Criterion report produced by the attached program > comparing initsR to initsQ. Previous tests definitively showed that > initsHO is a small constant factor worse than initsR, and > Data.List.inits is incomparably worse, so I limited this round to > initsR and initsQ. > > I therefore propose that we should replace the current implementation > of inits with initsQ, the queue-based one, unless someone comes up > with something faster and/or simpler very soon.

4 10

Proposal: Add strictly filtering filterM' to Control.Monad
by David Feuer 04 Sep '14

04 Sep '14

We have filterM, that looks like this (although I'm trying to get it changed to use foldr): filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = do flg <- p x ys <- filterM p xs return (if flg then x:ys else ys) This can cause a problem in some cases when used with IO, strict ST, or similar. In particular, it doesn't actually discard any elements of the list until all the predicate computations have run. Rather, it accumulates a chain of closures containing elements of the input and (possibly unevaluated) results of the (p x) computations. If the result of (p x) is usually False, so the input list is much longer than the output list, this can lead a program to run out of memory unnecessarily. This behavior cannot be avoided without changing semantics in some cases, as Dan Doel pointed out to me. In particular, a computation (p x) may run successfully to completion but produce a bottom value. PROPOSAL Add a function like this: filterM' :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM' p = go [] where go _ [] = return [] go acc (x:xs) = do flq <- p x ys <- if flq then go (x:acc) xs else go acc xs return (reverse acc) This can be twisted somewhat harder into a right fold if we want: filterM' :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM' p xs = foldr go return xs [] where go x r = \acc -> do flq <- p x ys <- if flq then r (x:acc) else r acc return (reverse acc) The advantage of this function is that instead of building a chain of closures proportional to the size of its *input* (but likely larger), it builds a list equal in size to its (possibly much smaller) *output*.

2 2

PROPOSAL: Make Data.Type.Bool.If polykinded
by Merijn Verstraaten 03 Sep '14

03 Sep '14

Ola! Currently we have: type family If cond tru fls where If True tru fls = tru If False tru fls = fls Unfortunately, this appears to turned into a monomorphicly kinded type family by GHC, which means it’s impossible to do foo :: If cond () (“Condition does not hold” ~ “”) => Foo -> Bar or similar fancy constraints. I hereby propose altering If to: type family If (cond :: Bool) (tru :: k) (fls :: k) :: k where If True tru fls = tru If False tru fls = fls Allowing it to work with kinds other than *. Discussion period: 2 weeks? Seems like a minor change. Cheers, Merijn

3 3

Discussion: Why is inet_addr in IO?
by Edward Kmett 31 Aug '14

31 Aug '14

inet_addr doesn't do any lookups, it is basically a glorified parsing problem converting from a string to a host address. http://hackage.haskell.org/package/network-2.6.0.1/docs/src/Network-Socket.… Why, beyond the obvious implementation details, does it live in IO? Given that the current version lives in IO, should there be a version that is obviously made pure so that folks who want to use it directly can do so without having to bury it behind an unsafePerformIO? This isn't a concrete proposal at this time, but more an attempt to sound out if such a proposal should be formed. -Edward

9 10

Proposal: Export Data.Word.Word from Prelude
by Herbert Valerio Riedel 31 Aug '14

31 Aug '14

Hello *, Proposal -------- I hereby propose to export Haskell2010's Data.Word.Word type from the Prelude Motivation ---------- Starting with Haskell2010, "Data.Word" exporting the type 'Word', "an unsigned integral type, with the same size as 'Int'" became part of the Haskell Report. 'Word' is usually a better choice than 'Int' when non-negative quantities (such as list lengths, bit or vector indices, or number of items in a container) need to be represented. Currently however, 'Word' is at a disadvantage (with respect to 'Int') in terms of public exposure by being accessible only after an "import Data.Word". Moreover, since 'Word' is now part of the Haskell Report, libraries should attempt to avoid name-clashing with 'Word' (and if they do, it ought to be a conscious decision, which ought to be declared by a requiring a "import Prelude hiding (Word)"). While one might think 'Word' would be a popular type-name to use in Haskell code, the current level of name collision is still rather low (as is shown in the next section), so the cost would still be bearable at this point in my opinion. Due diligence (w.r.t. code breakage impact) ------------------------------------------- Packages depending on `haskell2010` or `haskell98` are not affected, and neither would be those depending on `base` with a PVP-suggested upper bound. However, to get a rough idea how widespread the use of 'Word' as a type on Hackage currently is, here's a simple check for current uses of 'Word' as a type-name performed with the simple heuristic search find -name '*.*hs*' -exec grep \ '$data\|newtype\|type$[[:space:]]\+Word[ =]' {} + over the unpacked source trees of the latest versions of the current 6766 packages on Hackage resulted in the following 43 packages being possibly affected (see specific source-code matches at end of email[1]): 1 adict-0.4.1 2 boxes-0.1.3 3 cjk-0.1.0.1 4 clash-prelude-0.5.1 5 combinat-0.2.5.0 6 concraft-pl-0.7.1 7 Craft3e-0.1.0.10 8 crf-chain1-0.2.2 9 crf-chain1-constrained-0.3.0 10 crf-chain2-generic-0.3.0 11 crf-chain2-tiers-0.2.1 12 delta-h-0.0.3 13 eros-0.6.0.0 14 estimators-0.1.4 15 estreps-0.3.1 16 FermatsLastMargin-0.1 17 fsmActions-0.4.4 18 gf-3.6 19 happraise-0.1 20 HAppS-Data-0.9.3 21 happstack-contrib-0.2.1 22 hist-pl-fusion-0.5.3 23 Holumbus-Searchengine-1.2.3 24 integer-pure-1.0 25 ixset-typed-0.3 26 language-bash-0.6.0 27 language-sh-0.0.3.1 28 lhc-0.10 29 MemoTrie-0.6.2 30 mpppc-0.1.3 31 nerf-0.5.2 32 regex-deriv-0.0.4 33 regex-pderiv-0.1.3 34 regexpr-symbolic-0.5 35 remote-0.1.1 36 soyuz-0.0.0 37 text-icu-0.6.3.7 38 text-register-machine-0.4.0 39 utf8-light-0.4.2 40 WordNet-1.1.0 41 WordNet-ghc74-0.1.3 42 xhaskell-library-0.0.6 43 york-lava-0.2 Discussion period ----------------- 2 weeks Footnotes --------- [1] More specifically, here's the output of the above mentioned `grep` command: --8<---------------cut here---------------start------------->8--- adict-0.4.1/src/NLP/Adict/Core.hs:type Word a = V.Vector a boxes-0.1.3/Text/PrettyPrint/Boxes.hs:data Word = Word { wLen :: Int, getWord :: String } cjk-0.1.0.1/CJK/Data/CEDICT.hs:data Word = Word { clash-prelude-0.5.1/src/CLaSH/Tutorial.hs:type Word = Signed 4 combinat-0.2.5.0/Math/Combinat/FreeGroups.hs:type Word a = [Generator a] concraft-pl-0.7.1/src/NLP/Concraft/Polish/Morphosyntax.hs:data Word = Word Craft3e-0.1.0.10/Chapter7.hs:type Word = String Craft3e-0.1.0.10/Index.hs:type Word = String crf-chain1-0.2.2/Data/CRF/Chain1/Dataset/External.hs:type Word a = S.Set a crf-chain1-constrained-0.3.0/src/Data/CRF/Chain1/Constrained/Dataset/External.hs:data Word a b = Word crf-chain2-generic-0.3.0/Data/CRF/Chain2/Generic/External.hs:data Word a b = Word { crf-chain2-tiers-0.2.1/src/Data/CRF/Chain2/Tiers/Dataset/External.hs:data Word a b = Word { delta-h-0.0.3/src/EvalSem.hs:type Word = String eros-0.6.0.0/src/Text/Eros/Message.hs:type Word = L.Text estimators-0.1.4/NLP/Probability/Example/Trigram.hs:newtype Word = Word T.Text estreps-0.3.1/src/Repeats.lhs:-- type Word = Int FermatsLastMargin-0.1/FLM/WikiPages.hs: newtype Word = Word String fsmActions-0.4.4/Data/FsmActions.hs:newtype Word sy = Word [sy] gf-3.6/lib/src/finnish/wordnet/FreqFin.hs:type Word = String gf-3.6/treebanks/susanne/SusanneFormat.hs:type Word = String gf-3.6/treebanks/talbanken/Format.hs:data Word = W {id :: Id, word :: String, pos :: Tag} happraise-0.1/Main.hs:type Word = String HAppS-Data-0.9.3/src/HAppS/Data/Atom.hs: newtype Word = Word String happstack-contrib-0.2.1/src/Happstack/Contrib/Atom.hs: newtype Word = Word String hist-pl-fusion-0.5.3/src/NLP/HistPL/Fusion.hs:type Word = T.Text Holumbus-Searchengine-1.2.3/src/Holumbus/Index/Common/BasicTypes.hs:type Word = String integer-pure-1.0/Data/Integer.hs:type Word = Int -- We fake the Word type, to avoid nasty conversions. ixset-typed-0.3/src/Data/IxSet/Typed.hs: > newtype Word = Word String language-bash-0.6.0/src/Language/Bash/Word.hs:type Word = [Span] language-sh-0.0.3.1/Language/Sh/Syntax.hs:type Word = [Lexeme] lhc-0.10/lib/base/src/Data/Word.hs:type Word = Word32 lhc-0.10/lib/base/src/GHC/Word.hs:data Word = W# Word# deriving (Eq, Ord) MemoTrie-0.6.2/src/Data/MemoTrie.hs:-- newtype Word :->: a = WordTrie ([Bool] :->: a) mpppc-0.1.3/src/Text/PrettyPrint/MPPPC/TwoDim/Combinators/Flow.hs:data Word s t = Printable s t => nerf-0.5.2/src/NLP/Nerf/Types.hs:type Word = T.Text regex-deriv-0.0.4/Text/Regex/Deriv/ByteString/BitCode.hs:type Word = S.ByteString regex-deriv-0.0.4/Text/Regex/Deriv/ByteString/Posix.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/ByteString/LeftToRight.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/ByteString/LeftToRightD.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/ByteString/Posix.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/ByteString/RightToLeft.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/ByteString/TwoPasses.lhs:> type Word = S.ByteString regex-pderiv-0.1.3/Text/Regex/PDeriv/String/LeftToRightD.lhs:> type Word = String regexpr-symbolic-0.5/RegExpr/RegExprOperations.lhs:> type Word a = [a] remote-0.1.1/examples/tests/Test-MapReduce.hs:type Word = String remote-0.1.1/examples/kmeans/KMeans3.hs:type Word = String soyuz-0.0.0/DCPU16/Instructions.hs:data Word text-icu-0.6.3.7/Data/Text/ICU/Break.hsc:data Word = Uncategorized -- ^ A \"word\" that does not fit into another text-register-machine-0.4.0/Language/TRM/Base.hs:newtype Word = W [Letter] deriving (Eq, Monoid) utf8-light-0.4.2/src/Codec/Binary/UTF8/Light.hs:data Word = W# Word# WordNet-1.1.0/NLP/WordNet/Types.hs:type Word = String WordNet-ghc74-0.1.3/NLP/WordNet/Types.hs:type Word = String xhaskell-library-0.0.6/Text/Regex/PDeriv/ByteString/LeftToRight.lhs:> type Word = S.ByteString xhaskell-library-0.0.6/Text/Regex/PDeriv/ByteString/Posix.lhs:> type Word = S.ByteString xhaskell-library-0.0.6/Text/Regex/PDeriv/ByteString/RightToLeft.lhs:> type Word = S.ByteString xhaskell-library-0.0.6/Text/Regex/PDeriv/ByteString/TwoPasses.lhs:> type Word = S.ByteString york-lava-0.2/modules/Lava/Prelude.hs:type Word n = Vec n Bit --8<---------------cut here---------------end--------------->8---

12 18

[PROPOSAL] Add `FiniteBits(count{Leading,Trailing}Zeros)`
by Herbert Valerio Riedel 31 Aug '14

31 Aug '14

Hello *, As GHC 7.10.1 will have support for new assembler-optimized CLZ & CTZ[1] primops[2], it'd be useful to provide also a convenient high-level interface to avoid having to work with -XMagicHash and unboxed values. To this end, I hereby propose to add two new methods to the 'FiniteBits' class, specifically class Bits b => FiniteBits b where {- ... -} countLeadingZeros :: b -> Int countLeadingZeros x = (w-1) - go (w-1) where go i | i < 0 = i -- no bit set | testBit x i = i | otherwise = go (i-1) w = finiteBitSize x countTrailingZeros :: b -> Int countTrailingZeros x = go 0 where go i | i >= w = i | testBit x i = i | otherwise = go (i+1) w = finiteBitSize x The full patch (including Haddock doc-strings) is available for code review at https://phabricator.haskell.org/D158 I suggest to try to keep the discussion/voting/bikeshedding about the proposal proper here (including any bike-shedding about naming). At same time, I'd like to invite you to try out the Phab code-revision tool[3] for pointing-out/discussing technical issues with the proposed patch. Cheers, hvr [1]: http://en.wikipedia.org/wiki/Find_first_set provides a good overview why CLZ/CTZ are desirable primitive operations. [2]: http://git.haskell.org/ghc.git/commit/e0c1767d0ea8d12e0a4badf43682a08784e37… [3]: Phab code-revisions allow you to directly annotate code-fragments. However, after having written inline annotations, you have to actually submit those by submitting a non-inline (possibly empty) comment (see bottom of that page) to make them visible for everyone.

7 8

Splitting Network.URI from the network package
by Michael Snoyman 28 Aug '14

28 Aug '14

This was brought up last year[1], and I'd like to bring it up again, based on a recent issue I was working through with a user[2]. I realize that this is a breaking change, but: 1. It's a minor breaking change: you simply need to add an extra package to your build-depends. 2. The problems caused by having a parsec dependency in network can be severe, especially for new users (I'll describe the details after the proposal). Concretely, I believe we should do the following: 1. Create a new package, network-uri, version 2.5.0.0, which exposes no modules and has an upper bound `network < 2.6. 2. Create a second release of network-uri, version 3.0.0.0, which provides the Network.URI module verbatim as provided by the network package today, and has a lower bound `network >= 3.0`. 3. Release network version 3.0.0.0, with no changes from the currently released version, except that (a) no Network.URI module is provided, and (b) there is no parsec dependency. I don't remember how the discussion went last time, but I seem to remember general consensus. I'd like to set a discussion period of two weeks (August 15). ## Motivation To give a concrete example of why this problem is severe, consider the following data: * The network package is a pain to install on Windows for most users (especially new users), since it requires msys. * Most Windows users therefore install the Haskell Platform, avoiding the msys dependency. * The current release of HP installs text version 0.11.3.1. text is a dependency of parsec, and parsec is a dependency of network. Therefore, you can't build against a new version of text *and* use the network package without recompiling network, which as I mentioned is difficult. * A number of popular packages depend on newer versions of text. For example, since 0.8.0.0, aeson requires text version 1.1.0.0 or later. as does attoparsec since version 0.12.0.0. [1] http://www.haskell.org/pipermail/libraries/2013-January/019234.html [2] https://groups.google.com/d/msg/yesodweb/auk2vByXgO8/lUZ9oanKyMwJ

12 40

Re: Proposal: Export Data.Word.Word from Prelude
by Ben Millwood 26 Aug '14

26 Aug '14

On Sun, Aug 10, 2014 at 09:07:42AM +0100, Malcolm Wallace wrote: > > On 10 Aug 2014, at 07:04, Ivan Lazar Miljenovic wrote: > >> I'm +1 on the re-exporting (I would be tempted to go the whole hog and >> re-export all the Word* types as well). > > > I was involved in the discussions when the Word type was originally > added to Haskell, primarily for the use of the FFI. As I recall, > people were deeply uncomfortable that there should even be a Word > type, with unspecified precision. The types Word8, Word16, Word32, > and Word64 were entirely uncontroversial, because you know what you > are dealing with. The primary use of the Word* types was to > represent machine words (bytes, half-words, etc), enabling (for > instance) bit-twiddling of individual components of the word. With > an unknown-precision Word value, you can guarantee nothing about > whether your bit-operation will work. I believe the use of > unknown-precision Word to represent non-negative integers was the > winning justification, but it remains controversial in the same way > that Int (rather than Int32, or Integer) does. Lack of clarity > over whether or when a number overflows is a pretty bad downside. > Pragmatically, it may work OK for most people most of the time. > But the Haskel > l way is to prefer correctness. I think I sympathise a great deal with people's discomfort. I feel like the ubiquity of Int was a mistake: it's basically a performance optimisation, with reasonably serious correctness issues, and shouldn't be the first thing every newbie comes across. I moreover feel like, e.g. `length :: [a] -> Word` (or things of that ilk) would be even more of a mistake, because type inference will spread that `Word` everywhere, and `2 - 3 :: Word` is catastrophically wrong. Although it seems nice to have an output type for non-negative functions that only has non-negative values, in fact Word happily supports subtraction, conversion from Integer, even negation (!) without a hint that anything has gone amiss. So I just don't believe that it is a type suitable for general "positive integer" applications. I feel a little unqualified to comment in the face of people far more knowledgeable and experienced than I am enthusiastically +1-ing this proposal, but I'm going to go ahead and -1 it. I think the situations in which Word is really what you want are few enough that it should not clutter the universal namespace. > Regards, > Malcolm > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries

14 20

Proposal: Simplify/Generalize Data.Dynamic
by Edward Kmett 26 Aug '14

26 Aug '14

I'd like to propose a cleanup to the API of Data.Dynamic. By way of (partial) motivation, a couple of years back Lennart posed a question on stackoverflow <http://stackoverflow.com/questions/10889682/how-to-apply-a-polymorphic-func…> about how to use Dynamic to implement apD :: forall f. Typeable1 f => (forall a. a -> f a) -> Dynamic -> Dynamic At the time, I offered a solution that is no longer applicable in a world with polykinded Typeable. But, if we change the definition of Data.Dynamic to data Dynamic where Dynamic :: Typeable a => a -> Dynamic from its current magic implementation in terms of unsafeCoerce and a manually held typeRep, then fromDynamic becomes a trivial application of Data.Typeable.cast and dynApply becomes easier, This would enable us to implement Data.Dynamic with its full constructor exposed without losing safety. In lieu of supplying the constructor, we could offer a form of withDyn :: Dynamic -> (forall a. Typeable a => a -> r) -> r but I'd rather expose the constructor rather than needlessly Church encode as the kind of code/user that needs this is the kind that would bemoan needless performance barriers in the name of nebulous encapsulation benefits. Now it becomes possible to write code that does polymorphic things underneath the Dynamic wrapper, such as Lennart's example once more, but now in a principled way. Discusssion Period: 2 Weeks *tl;dr* polykinded Typeable took away some power from the users of Data.Dynamic, which we can give back in a more principled way, simplifying the API as a result. -Edward

7 6

time and old-locale
by Ashley Yakeley 24 Aug '14

24 Aug '14

For time-1.5, I'm removing the dependency on old-locale, and including that code directly in Data.Time.Format. The package will also include its own deprecated System.Locale. I expect this to be a popular, decade-overdue move, but if you have some complaint, let me know before I release it. Repository is at https://github.com/haskell/time -- Ashley Yakeley

3 5