June 2010 - Libraries

State of the Hackage: Q1, Q2 2010
by Don Stewart 30 Jun '10

30 Jun '10

Downloads and popular packages on Hackage for Q1 and Q2 this year. http://donsbot.wordpress.com/2010/06/30/popular-haskell-packages-q2-2010-re… -- Don

1 0

Dependency Problem on Hackage
by Seyed Hosein Attarzadeh Niaki 29 Jun '10

29 Jun '10

Dear Haskell libraries maintainers, I have recently uploaded a package to Hackage and got a build failure: http://hackage.haskell.org/packages/archive/ForSyDe/3.1.1/logs/failure/ghc-… The error looks to be due to dependencies on multiple versions of some Haskell libraries built on Hackage. In particular, depending on both "directory" and "process" leads to indirect dependencies on unix-2.4.0.1 and 2.4.0.2. The same situation is there for "containers" and "regex-posix" which results to multiple dependency on array-0.3.0.0 and 0.3.0.1. I asked about this matter on #haskell. They said it is because of the centralized build mechanism of Hackage which hopefully will be improved with the new servers. But, for the short term I should ask the maintainers to rebuild the deps. I would like to ask if you confirm the cause of error. Also, since many packages depend on these Haskell libraries, I guess other people might also have the same problem. Do you have any plans to rebuild these packages on Hackage? Regards, -- Hosein Attarzadeh

1 0

crypto-api Status + Semantics (was: DRBG pre-announce and a discussion on RNG/Crypto infrastructure)
by Thomas DuBuisson 28 Jun '10

28 Jun '10

All, This is a status update and a discussion on semantics. 1.0 SEMANTICS Given classes that imply a blockSize, how are instances of those classes expected to behave? Some options (I prefer option 1.1): 1.1 Single block (bare bones implementation) Each call to 'update' (for Hash) or 'blockEncrypt/Decrypt' (for BlockCipher) will consume exactly 'blockSize/8' bytes. That is, this follows most hash/cipher definitions quite strictly by performing exactly one block encrypt or hash update. Data over blockSize is ignored, if the input is empty then return Data.ByteString.empty or the current context (for BlockCipher, Hash respectively). Obvious options for non-empty input of length less than blockSize are: throw an exception or make all returns something like "Maybe a"... I'll probably throw an exception. Users wouldn't / shouldn't care as they will be accessing these instances via the "hash", "hash'", "hmac", "hmac'" or mode-specific encryption methods - all of which are part of crypto-api and handle the chunking of data already. IOW this saves duplicate work at the slight risk of a dev doing something dumb and having a runtime exception. 1.2 Multiple of blockSize bytes Implementations are encouraged to consume data (continue updating, encrypting, or decrypting) until there is less than blockSize bits available. There is duplicate work here as both the "hash" implementation and the "update" instance check the bytestring length and chunkify. 1.3 Any input size works Much like accepting any number of blocks except in the case of Hashes, the 'update' function must track a remainder (bytes < blockSize) - such accounting is done by "hash" already and only matters if, for some odd reason, people start using the class methods directly. For encryption/decryption we would just truncate. Because the example instances below were built from pre-existing packages this is exactly what they do now. I like this option least of all. 2.0 STATUS Addressing each item in the todo list: > - Decide on package name, replace "Crypto" or select a new name? I think "crypto-api" is best, which means this would exist in parallel with the "Crypto" package. I still encourage people to move away from / eventually depricate Crypto! > - Look harder at the other classes including "BlockCipher", "AsymCipher", "StreamCipher" A stab at these classes are now in the repo. Nothing is in stone - chiseling is hard work compared to typing. > NEW ITEM: Copy Data.LargeWord from Crypto into Crypto-API Word{128,192,256} seem useful enough and I don't think people should rely on both Crypto and crypto-api. Perhaps I should be asking where it truly belongs - with FFI and directly in Data.Word? I'm ok with it being in crypto-api but it should be in FFI - pulled into Data.Word. > - example instances of each class from the pureMD5 repo: --- BEGIN Hash instance --- instance Hash MD5Context MD5Digest where outputLength = Tagged 128 blockLength = Tagged 512 initialCtx = md5InitialContext updateCtx = md5Update finalize = md5Finalize strength = Tagged 24 -- END Hash instance --- For block ciphers I built an instance for twofish (see below). I realized part way in that making TwofishCipher have an extra type tag (TwofishCipher ⍺, to allow separate instance for each key length) is entirely a hack-job wrt the rest of the twofish code. A better long term solution is to make a field in the TwofishCipher data declaration which indicates the size of the key (keySize :: Int) and have a single BlockCipher instance for "TwofishCipher" (keyLength = keySize). -- BEGIN BlockCipher instance --- instance BlockCipher (TwofishCipher Word128) where blockSize = Tagged 128 encryptBlock t = encode . liftCryptor (eb t) . decode decryptBlock t = encode . liftCryptor (db t) . decode buildKey bs = mkStdCipher (decode bs :: Word128) keyLength _ = 128 --- END BlockCipher instance --- I'm not aware of any Haskell implementation of / bindings to a stream cipher. If someone points one out I might try to make an instance. WRT AsymCipher, I'll probably make an example instance for the RSA package (PKCS1) later... feel free to beat me to it > - example uses of each class A Hash example can be found in DRBG. Also, crypto-api uses Hash to build the functions hash and hmac. > - Collecting tests, building a test framework I'll be adding both agnostic and algorithm-specific tests to crypto-api. These will be included/excluded depending on a cabal flag. > - Move "for" and (.::.) into the Tagged library (?) Helper functions were added to tagged, but they didn't seem to suffice in place of "for". I'd be happy to be corrected. > - Decide what we want on padding Could someone who needed the padding in Crypto tell me their use cases? Are people mainly wanting PKCS5? I'm tempted to leave this out unless there is some need for them in the generalization / API. > - Decide what we want with crypto-related items that aren't directly a > cipher or hash (ex: pbkdf2). This will be put off till I consider crypto-algs more carefully. > - Implement modes Trying to figure out the API here. I think we want: cbc, cbc', unCbc, unCbc' ecb, ecb', unEcb, unEcb' ctr, ctr', unCtr, unCtr', ofb, ofb', unOfb, unOfb' These would have types in the form of: cbc :: (Cipher k) => k -> IV -> ByteString -> (ByteString, IV) I've considered a suggestion to make a custom State monad to track IVs, but don't see the need and why users of crypto-api wouldn't be better served by simpler definitions that can be wrapped for their own State monad for a given program. At any rate, a State wrapper can be made (part of crypto-api or not) using these underlying functions. 3.0 Next Time Hopefully I'll have done (2 weeks): - implement modes - Copy Data.LargeWord unless there are convincing objections such as "These will be in FFI Data.Word next week". - Implement CTR based DRBG from NIST SP 800-90 (use BlockCipher class). - clean pureMD5 - make it jive with semantics from section 1.1 And later (~4 weeks) - Define, document exceptions (if we choose to throw any as a result of non-blockSized inputs) - Test cases And even later (~6 weeks) - Release 0.0.0.1 on hackage - Talk about crypto-algs Comments, patches, and suggestions are all welcome. Cheers, Thomas

1 0

Tuning tries (IntSet, hashmap, bytestring-trie, etc.)
by Jim Apple 26 Jun '10

26 Jun '10

Given the recent faster trie implementations (hooray!), I thought it would be worth pointing out that a pretty thorough discussion of the tradeoffs of functional trie design is available at http://www.nada.kth.se/~snilsson/publications/Functional-trie-compression-e… An experimental study of compression methods for functional tries Jukka-Pekka Iivonen, Stefan Nilsson, and Matti Tikkanen WAAAPL'99 FWIW, apparently clojure uses a 32-ary hashtrie: http://blog.ezyang.com/2010/03/the-case-of-the-hash-array-mapped-trie/ http://blog.higher-order.net/2009/09/08/understanding-clojures-persistentha… Because it is only binary, Data.IntSet is sometimes quite deep. All of that pointer chasing makes Data.Set actually faster than Data.IntSet for looking up 0 in the set 0:[2^i | i <-[0..30]].

2 1

Map folds in containers: why no worker/wrapper split?
by Claus Reinke 26 Jun '10

26 Jun '10

Looking at the source code for containers (0.3.0.0), especially the foldWithKey functions in Data.Map and Data.IntMap, I see recursive definitions with non-strict accumulators, without the usual worker/wrapper split, such as: foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b foldlWithKey _ z Tip = z foldlWithKey f z (Bin _ kx x l r) = foldlWithKey f (f (foldlWithKey f z l) kx x) r For comparison, here is base:GHC.List.lhs's definition of foldl: -- We write foldl as a non-recursive thing, so that it -- can be inlined, and then (often) strictness-analysed, -- and hence the classic space leak on foldl (+) 0 xs foldl :: (a -> b -> a) -> a -> [b] -> a foldl f z0 xs0 = lgo z0 xs0 where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs Doesn't that mean that strictness in the folded Map/IntMap operations cannot be used by the strictness analyser? What am I missing? Claus

4 8

Re: Containers and strictness
by Ben 25 Jun '10

25 Jun '10

this all sounds like wonderful work, looking forward to it. slightly off topic, but in whatever revision of Data.IntMap you come up with, can you include foldrWithKey, toDescList, mapAccumRWithKey and the rest of the reverse-order traversals which are in Data.Map? all for consistency..... best regards, ben On Thu, Jun 24, 2010 at 9:00 AM, <libraries-request(a)haskell.org> wrote: > Send Libraries mailing list submissions to > libraries(a)haskell.org > > To subscribe or unsubscribe via the World Wide Web, visit > http://www.haskell.org/mailman/listinfo/libraries > or, via email, send a message with subject or body 'help' to > libraries-request(a)haskell.org > > You can reach the person managing the list at > libraries-owner(a)haskell.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Libraries digest..." > > > Today's Topics: > > 1. Re: Containers and strictness (Edward Kmett) > 2. Re: Containers and strictness (Johan Tibell) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Thu, 24 Jun 2010 09:28:15 -0400 > From: Edward Kmett <ekmett(a)gmail.com> > Subject: Re: Containers and strictness > To: Johan Tibell <johan.tibell(a)gmail.com> > Cc: Duncan Coutts <duncan.coutts(a)googlemail.com>, > libraries(a)haskell.org > Message-ID: > <AANLkTim3-EIxn7fLIybNqXXR0tEZznitJlPG-78IdHN7(a)mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > On Thu, Jun 24, 2010 at 8:27 AM, Johan Tibell <johan.tibell(a)gmail.com>wrote: > >> On Thu, Jun 24, 2010 at 1:59 PM, Edward Kmett <ekmett(a)gmail.com> wrote: >> >>> >>> >>> 2010/6/24 Milan Straka <fox(a)ucw.cz> >>> >>> > On 24 June 2010 11:14, Milan Straka <fox(a)ucw.cz> wrote: >>>> > >>>> > > I need some opinion: >>>> > > >>>> > > - Do you think methods like insert/lookup/delete/etc should be strict >>>> in >>>> > > key/element? >>>> > > >>>> > > As Claus wrote, right now it is undocumented and inconsistent (both >>>> in >>>> > > the methods of one container and also in the same methods of >>>> different >>>> > > container). >>>> > >>>> > Just as it is sometimes important to be able to do strict inserts, it >>>> > is important sometimes that we have maps that are lazy in the >>>> > elements. There are important use cases both ways. >>>> > >>>> > So yes we should have some kind of consistent convention. We could do >>>> > worse than the naming convention where the strict versions use a >>>> > trailing prime ' character. >>>> >>>> I thought we are talking only about keys/elements. I would leave the >>>> values untouched. >>>> >>>> Personally I vote for: >>>> - keys in Maps and elements in Sets are strict >>>> - vales in Maps are left untouched (lazy) >>>> >>> >>> +1 from me >>> >>> Great work so far. >>> >> >> The space overhead per key/value pair is 6 words (48 bytes on a 64-bit >> architecture) when using lazy values but only 4 words (32 bytes) per >> key/value pair when using strict (unpacked) values, a 50% difference. This >> really starts to matter with big enough data sets (as seen in the recent >> Twitter analysis thread). When work with Big Data it's often desirable to >> fit as much data in RAM as possible as the result of many algorithms (think >> machine learning or search ranking) differs with the amount of data you can >> hold in memory. >> >> Something to consider. >> > > I definitely agree that unboxing can help a great deal with performance and > space utilization. > > However, as containers does not currently require any exotic extensions, I > think that perhaps a type family -based generic map would belong in another > 'unboxed-containers' or 'adaptive-containers' package (both of which > currently exist on hackage), as it dramatically extends the language > extension footprint of containers, taking it from something that easily runs > across a wide array of Haskell implementations to something very > ghc-specific. > > -Edward Kmett >

1 1

Re: Status of regex-posix on Windows?
by Claus Reinke 17 Jun '10

17 Jun '10

[Mikhail redirected to haskell-platform@] Hi Chris, > I am the listed darcs / hackage maintainer for regex-posix. It is true > that I do not use it on Windows and so I do not have that setup properly. .. > http://code.haskell.org/regex-posix/ > > Patches to enable compiling regex-posix-0.94.2 on Windows are welcome. That darcs repo and package version are the ones I was referring to!-) But before I look into patches, I would like to understand how things are supposed to work. Also, others have patched already, just not sent the patches to you, so there seems to be something more going on. The problems are not actually Windows-specific, it just so happens that Windows is one OS on which one would like to use the in-package C-library. So if you could clarify how to build the package that way, it should also work on Windows, using mingw/msys. Claus -- hackage and darcs package versions $ grep ^Version: */*/regex-posix.cabal darcs/regex-posix/regex-posix.cabal:Version: 0.94.2 hackage/regex-posix-0.94.2/regex-posix.cabal:Version: 0.94.2 $ cat darcs/regex-posix/_darcs/prefs/repos http://code.haskell.org/regex-posix -- hackage version is missing cbits etc $ diff -r darcs/regex-posix/ hackage/regex-posix-0.94.2/ Only in darcs/regex-posix/: Makefile Only in darcs/regex-posix/: _darcs Only in darcs/regex-posix/: aclocal.m4 Only in darcs/regex-posix/: cbits Only in darcs/regex-posix/: config.mk.in Only in darcs/regex-posix/: configure.ac Only in darcs/regex-posix/: include Only in darcs/regex-posix/: package.conf.in Only in darcs/regex-posix/: prologue.txt diff -r darcs/regex-posix/regex-posix.cabal hackage/regex-posix-0.94.2/regex-posix.cabal 27c27 < Build-Depends: regex-base >= 0.93, base >= 4, array, containers, bytestring --- > Build-Depends: regex-base >= 0.93, base >= 4 && < 5, array, containers, bytestring -- two Build-Types, neither configure? $ grep Build-Type darcs/regex-posix/regex-posix.cabal Build-Type: Custom Build-Type: Simple -- no Custom/Configure here, either $ cat darcs/regex-posix/Setup.hs import Distribution.Simple main = defaultMain -- is this still supposed to work? $ head -1 darcs/regex-posix/configure.ac AC_INIT([Haskell regex-posix package], [0.71], [TextRegexLazy(a)personal.mightyreason.com] [regex-posix]) -- Makefiles date back to when regex-posix was built within GHC $ find darcs/regex-posix/ -name Makefile | xargs grep TOP darcs/regex-posix/cbits/Makefile:TOP = ../.. darcs/regex-posix/cbits/Makefile:include $(TOP)/mk/boilerplate.mk darcs/regex-posix/cbits/Makefile:include $(TOP)/mk/target.mk darcs/regex-posix/Makefile:TOP = .. darcs/regex-posix/Makefile:include $(TOP)/mk/boilerplate.mk darcs/regex-posix/Makefile:include $(TOP)/mk/target.mk

1 0

Re: Status of regex-posix on Windows?
by Claus Reinke 16 Jun '10

16 Jun '10

Sorry about the triplicate (for the first two, my mailer told me it had failed to send the message). Claus

1 0

Status of regex-posix on Windows?
by Claus Reinke 16 Jun '10

16 Jun '10

There was a thread here in March 2010 about issues with building regex-posix on Windows: http://www.haskell.org/pipermail/libraries/2010-March/013321.html It was pointed out that the maintainer doesn't have Windows access, and some conclusion seems to have been reached that allowed regex-posix to be included in the Haskell platform release. But it does not look as if the results were fed back to the maintainer for inclusion in the regex-posix package (darcs or hackage version). What is the recommended way to build regex-posix on Windows these days? Could the information be distilled into a package that builds without hacks, and could the hackage package please be updated to reflect that? It is a platform package, after all. Claus -- It looks as if at some point the package could just be built without external dependencies (other than GHC's build system) but it is not clear to me what the current intention is for building on Windows. The hackage version is still missing bits from the darcs version (in particular, the c-code to build and link with/include from), the darcs version has Makefiles that date back to when regex-posix was built within GHC's build system, and a configure.ac proclaiming the library to be at version 0.71. The .cabal file (version 0.94.2) features two Build-type entries (Custom and Simple), the Setup.hs simply calls defaultMain.

1 0

Status of regex-posix on Windows?
by Claus Reinke 16 Jun '10

16 Jun '10

There was a thread here in March 2010 about issues with building regex-posix on Windows: http://www.haskell.org/pipermail/libraries/2010-March/013321.html It was pointed out that the maintainer doesn't have Windows access, and some conclusion seems to have been reached that allowed regex-posix to be included in the Haskell platform release. But it does not look as if the results were fed back to the maintainer for inclusion in the regex-posix package (darcs or hackage version). What is the recommended way to build regex-posix on Windows these days? Could the information be distilled into a package that builds without hacks, and could the hackage package please be updated to reflect that? It is a platform package, after all. Claus It looks as if at some point the package could just be built without external dependencies (other than GHC's build system) but it is not clear to me what the current intention is for building on Windows. The hackage version is still missing bits from the darcs version (in particular, the c-code to build and link with/include from), the darcs version has Makefiles that date back to when regex-posix was built within GHC's build system, and a configure.ac proclaiming the library to be at version 0.71. The .cabal file (version 0.94.2) features two Build-type entries (Custom and Simple), the Setup.hs simply calls defaultMain.

1 0