November 2005 - Libraries

Broken monad laws
by Iavor Diatchki 24 Nov '05

24 Nov '05

Hello, I just noticed that the GHC/Hugs "standard" libraries have acquired a list monad transformer, which is broken, because it does not satisfy the associativity law when applied to non-commutative monads. I am not referring to some corner-case strictness problem, but rather a fairly well known result. The associativity law is important, because without it the 'do' notation can be very confusing. Bellow is an example, for people not familiar with the porblem. -Iavor import Control.Monad.List say :: String -> ListT IO () say x = lift (putStr x) one_two, ex1,ex2 :: ListT IO () one_two = say "1 " `mplus` say "2 " ex1 = do one_two say "3 " say "4 " ex2 = do do one_two say "3 " say "4 " main = runListT ex1 >> putStrLn " or " >> runListT ex2

2 1

Bug in Control.Monad.State
by Yitzchak Gale 24 Nov '05

24 Nov '05

In the following thread, I reported a problem I was having with programs diverging when they use infinite lists with StateT: http://www.haskell.org//pipermail/haskell-cafe/2005-November/012253.html Roberto Zunino and Wolfgang Jeltsch pointed out that this is a bug in Control.Monad.State: (>>=) is lazy in State, but strict in StateT. The source of the problem is that the pattern match in the definition of (>>=) is inside a let expression in State - so it is lazy - but inside a do expression inside StateT - so it strict. Roberto suggests a one-byte patch to fix this problem: add '~' to make the pattern match in StateT irrefutable. (Note that this has already been done for the MonadFix instance of StateT.) The same fix should be applied to evalStateT and execStateT. They are also stricter than their non-transformer counterparts, for the same reason. -Yitz

4 15

RE: Bug in Control.Monad.State
by Simon Marlow 23 Nov '05

23 Nov '05

Apologies for being a bit blunt, but can't this problem be solved by introducing a LazyStateT in addition to StateT? This follows the pattern of ST (default is strict, we also have Control.Monad.ST.Lazy). Cheers, Simon On 23 November 2005 09:59, Udo Stenzel wrote: > Hello Yitzchak, > >>> If an operation is too strict... you can always >>> wrap the offending data in another constructor. >> >> I have seen this claim several times, but I am >> not yet convinced. >> >> In my case, the unwanted strictness is coming from >> the bind method of a monad from the standard >> libraries. I don't see how to get rid of that >> strictness by wrapping something in a constructor. > > as Iavor already pointed out, theres the fine difference between being > string in some implementation detail (the pair of state and result) or > in the state itself, which I missed. > > I was thinking of the state component, and I maintain that it should > be strict. Rationale: if the state is some primitive type, you want > it strict anyway. If it isn't, the strictness doesn't cost much > anyway. If it's still wrong, wrapping in a constructor helps. > > Your problem however is the strict match against a pair you don't even > know is there. Indeed, a strict match against a single constructor > datatype is probably always pointless. So it's really a bug in the > library, after all. > > >> Here is an example. How would you fix this by >> wrapping something in a constructor? > > You can't, since you don't have access to the offending pair. > >> createItems :: RandomGen g => State g [Item] >> createItems = >> liftM catMaybes $ runListT $ >> flip evalStateT initialState $ runMaybeT $ >> do >> item <- liftRandom $ repeatM randomItem >> updateState item >> needMoreItems >>= guard >> return item >> where >> liftRandom = lift . lift . lift > > ...but this is probably broken anyway. After (repeatM randomItem) > presumably the state (the RandomGen) is _|_, but the type of > createItems would suggest it is still usable. I wouldn't do that. > Other than that it's a bit hard to see what you're trying to > accomplish here. > > > Udo.

2 1

Announcement of work in progress: Shaskell sha2 library
by Dominic Steinitz 22 Nov '05

22 Nov '05

David, The Haskell Cryptographic Library consists of contributions from different authors which I have wrapped to give a uniform API, written a test suite and darcsized and cabalized. But caveat emptor! I am happy to incorporate new contributions. A different approach would be to provide an interface to openssl and Peter Simons has already done something along these lines, see http://cryp.to/hopenssl/. The latest version of openssl supports SHA-256 for example. From an industrial strength point of view, this is probably the way to go. Peter had a view that all "crypto" algorithms (I include hashes here) should have monadic versions- see below - even though they are all pure. Neither he nor I got round to doing anything about this. I'm not a lawyer but do hash functions count as encryption? There are no keys and you can't recover the data. And haven't the regulations been relaxed recently? Lots of publicly available packages offer SHA-256. Dominic. On Monday 07 Feb 2005 8:27 pm, you wrote: > Dominic Steinitz writes: > > I'd suggest not touching anything to do with ASN.1 as I > > have now got a prototype of the re-write which will parse > > an X.509 certificate and extract the public key. > > Sounds great. I'll update the repository every now and then so > that I can see what's going on. I was wondering about OpenSSL ... > Have you made FFI bindings to the library? Are you aware that I've > made some for EVP digests too? Maybe we could throw together? > > My main interest in Codec is in unifying the API; hiding the > symmetric ciphers and digests behind one simple type class or > monad or whatever it will be. I want to use those functions > without knowing which one I am using. > > I'm not sure how asymmetric ciphers fit into that; they're > typically used differently, not for octet streams. > > >> It seems that the latest ghc from CVS comes with several > >> changes that break compilation of the code. I'll try to get > >> that fixed without becoming incompatible with the 6.2.2 > >> release in turn. > > > > I'm surprised as I am running 6.2.2 > > [dom@tility dom]$ ghc --version > > The Glorious Glasgow Haskell Compilation System, version 6.2.2 > > Well, GHC is at 6.5 by now, if you use the CVS version. ;-) > > > I think you need both the pure and monadic versions. They > > really are pure functions but sometimes you don't have all the > > data you want to encrypt available in one go. > > A State monad is a pure function. If you have > > aesM :: [Word8] -> State AES [Word] > initAES :: AES > > then you have > > aes :: [Word8] -> [Word8] > aes x = evalStateState (aesM x) initAES > > just as well. But the reverse is impossible. I think _all_ ciphers > and digests should be State monads. It means that an awfully lot > of combinators can be written as monad transformers: > > asciiArmor :: ([Word8] -> State st [Word8]) > -> [Word8] -> State st [Word8] > > Block chaining, encoding, layering of ciphers, permutations and > all that can be written independently of what the actual cipher > is. A cipher is just a transformer with state: we can run it with > runState, we can compose it, and we can fool around with the > input/output stream. > > That's the way to go, IMHO. I've used this exact same design in > Postmaster to build the ESMTP state machine, and the flexibility > is staggering. I've come to love monads by now. ;-) > > Anyway, that's all just speculation. We'll see whether I can whip > up a nice module which shows what it would look like. > Unfortunately, my time is very limited too. It's a shame, really. > > Oh well, I you'll find some spare time and get your ASN.1 parser > done. I'm looking forward to having SSL/TLS support in Postmaster > soon then. ;-) > > Take care, > > Peter

2 1

Data.Set API
by Iavor Diatchki 22 Nov '05

22 Nov '05

Hello, I just noticed that the type of Data.Set.map is (Ord a, Ord b) => (a -> b) -> Set a -> Set b Is the 'Ord a' constraint really neccessary? It did not use to be there in the old implementation. -Iavor

2 1

PROPOSAL: classes for traversals
by Ross Paterson 21 Nov '05

21 Nov '05

Conor McBride and I would like to propose some new classes for traversals of containers, based around applicative functors (the abstraction formerly known as idioms): http://www.soi.city.ac.uk/~ross/traversals/ They are proposed for the base package, and would replace FunctorM. Comments most welcome.

5 7

Announcement of work in progress: Shaskell sha2 library
by David Mercer 21 Nov '05

21 Nov '05

Hello everyone, my name is David Mercer, and after a few days of hanging out on the #haskell irc channel asking annoying questions about monads, and reading mailing list archives for a while, I'm pretty sure that this is the correct list to post this announcement/request for feedback and review from the Haskell community. I am currently nearly done with a library implementing the SHA-224/256/384/512 message digest algorithms, collectively often called SHA2, completely in Haskell. The initial motivation was a desire to compute SHA2 hashs in what was to have been my first Haskell program (this is instead). I looked around to see if perhaps there was a library, or at least a wrapper to some C/C++ crypto libraries SHA2 hash functions. Alas, all was naught (correct me if I missed something, please!), and at best the SHA1 code from darcs was uncovered (after a query on the cryptography mailing list), which is a pure Haskell SHA1 library. Digest.hs is a wrapper to OpenSSL's SHA1 functions, but would need to be updated to handle SHA2. So like any good programmer I started with the same API as Digest.hs, gleefully grabbed the shell of it, gpl and all, as it's infrastructure and crypto, and set to work. I have so far completed all of the non-stateful (pure and lazy!) portions of the FIPS 180-2 specification, up through section 6.2.1 inclusive, and step 1. only from section 6.2.2. That last is the tricky bit, where all of the stateful computation takes place and entropy is disturbed with prime number mixing and overflowing bit operations. It's only a few lines of the spec that I have remaining (aside from message length padding), and I intend to implement them as a monad. Unfortunately due to (in my opinion) silly laws in the United States, I have to say that only those resident in the list of countries found at the end of this message are supposed to click the link that's coming up and look at my source code. Silly because it can always be scanned overseas after hardcopy publication, and sillier yet again because for the last 5 years one can legally post encryption source code in the US online without logging who downloads it. The just require you to email the NSA with the url of publication (which I have done by the way). All of which is even sillier yet again because I'm only releasing message digest, and not actual high level encryption, source code. So although my webserver does not even keep access logs, presumably 'big brother' knows where to traffic sniff to watch who dowmloads what from where. If they want to. But I digress. The source code for this pre-release version of Shaskell for peer review is at: http://davidmercer.nfshost.com/projects/shaskell/shaskell.hs That address will also remain the permanent download url for released versions of the Shaskell library source code. Associated files and a local mirror of the (public domain and non-export controlled) FIPS 180-2 specification, in pdf format are at http://davidmercer.nfshost.com/projects/shaskell/ Comments, critiques, suggestions, fan mail, hate mail, monad tutorials, suggestions for publication venues and other thoughts on the source code or the abstract for the the eventual academic paper (in the above directory as well) are welcome and encouraged! Thanks a bunch in advance for any of your time or attention expended on this, and I look forward to contributing to the Haskell community! -David Mercer University of Arizona Tucson, AZ [dmercer@u.arizona.edu|radix42@gmail.com] PS Have the major Haskell distributions had to directly deal with crypto export control issues yet, or has it been dodged so far by using only wrapper libraries, as appears to be the case from what I've dug up so far? Thanks again!

2 2

Cabal with profiling
by Iavor Diatchki 18 Nov '05

18 Nov '05

Hello, I am sure this was asked before, but I could not find any answers... How can I use Cabal to build a package that includes both normal and profiling versions of my library for GHC? I am thinking of something like: runhaskell Setup.hs configure --ghc --with-profiling * remembers that we want profiling libraries) runhaskell Setup.hs build * compile as usual * if 'with-profiling' compile again with some additional options, (e.g., -prof etc) and then proceed as usual. -Iavor

2 2

Hex Values
by Dominic Steinitz 17 Nov '05

17 Nov '05

I often find myself wanting to print out hex values as a string. I couldn't find a library function so I came up with this. Is it worth putting in a library? The obvious place for me would be Data.Codec.Utils. Thoughts? Dominic. hexify :: Integral a => a -> Doc hexify n = let bar = map (map sh) (split 16 (toOctets 256 n)) foo = map (intersperse colon) (map (map text) bar) baz = vcat (map hcat foo) in baz sh x | x < 16 = showHex x "0" | otherwise = showHex x "" split :: Int -> [a] -> [[a]] split n xs = unfoldr (g n) xs where g :: Int -> [a] -> Maybe ([a],[a]) g n y | length y == 0 = Nothing | otherwise = Just (splitAt n y)

5 5

cabal: configure --user imples install --user
by Isaac Jones 15 Nov '05

15 Nov '05

I am changing the behavior of user vs global installations slightly, and I'm wondering if anyone sees a problem with this. It seems to make much more sense than what we were doing. Commit log follows. peace :) isaac Modified files: libraries/Cabal/Distribution Setup.hs Simple.hs libraries/Cabal/Distribution/Compat FilePath.hs libraries/Cabal/Distribution/Simple Configure.hs LocalBuildInfo.hs Log: modified install --user behavior to include configure --user If the user configures with --user, that means that they are willing to satisfy dependencies from the user databaes. If that's the case, then it really only makes sense to install the package as --user as well, since if user A installs configures / builds the package with --user, then installs it as root, user B may attempt to use the package and not be able to fulfill the dependencies. Therefore, if the package is configured as --user, then we also will call ghc-pkg with --user. Of course, in this case: ./setup configure --user ./setup install --global Cabal will accept the user's instructions to install this globally, however ill conceived. This changes the type of the install hook, btw, since we now need to be able to tell the difference between passing the --global flag and not passing any flag. Any objections to this change?

1 0