- Haskell-Cafe - Haskell.org

ANNOUNCE: binary: high performance, pure binary serialisation
by dons＠cse.unsw.edu.au 01 Feb '07

01 Feb '07

Binary: high performance, pure binary serialisation for Haskell ---------------------------------------------------------------------- The Binary Strike Team is pleased to announce the release of a new, pure, efficient binary serialisation library for Haskell, now available from Hackage: tarball: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary/0.2 darcs: darcs get http://darcs.haskell.org/binary haddocks: http://www.cse.unsw.edu.au/~dons/binary/Data-Binary.html The 'binary' package provides efficient serialisation of Haskell values to and from lazy ByteStrings. ByteStrings constructed this way may then be written to disk, written to the network, or further processed (e.g. stored in memory directly, or compressed in memory with zlib or bzlib). Encoding and decoding are achieved by the functions: encode :: Binary a => a -> ByteString decode :: Binary a => ByteString -> a which mirror the read/show functions. Convenience functions for serialising to disk are also provided: encodeFile :: Binary a => FilePath -> a -> IO () decodeFile :: Binary a => FilePath -> IO a To serialise your Haskell data, all you need do is write an instance of Binary for your type. For example, suppose in an interpreter we had the data type: import Data.Binary import Control.Monad data Exp = IntE Int | OpE String Exp Exp We can serialise this to bytestring form with the following instance: instance Binary Exp where put (IntE i) = putWord8 0 >> put i put (OpE s e1 e2) = putWord8 1 >> put s >> put e1 >> put e2 get = do tag <- getWord8 case tag of 0 -> liftM IntE get 1 -> liftM3 OpE get get get The binary library has been heavily tuned for performance, particularly for writing speed. Throughput of up to 160M/s has been achieved in practice, and in general speed is on par or better than NewBinary, with the advantage of a pure interface. Efforts are underway to improve performance still further. Plans are also taking shape for a parser combinator library on top of binary, for bit parsing and foreign structure parsing (e.g. network protocols). Several projects are using binary already for serialisation: lambdabot : state file serialisation hmp3 : mp3 file database hpaste.org : pastes are stored in memory as compressed bytestrings, and serialised to disk on MACID checkpoints Binary was developed by a team of 8 during the Haskell Hackathon, Hac 07, and received 200+ commits over that period. You can see the commit graph here: http://www.cse.unsw.edu.au/~dons/images/commits/community/binary-commits.png The use of QuickCheck was critical to the rapid, safe development of the library. The API was developed in conjunction with the QuickCheck properties that checked the API for sanity. We were thus able to improve performance while maintaining stability. We feel that QuickCheck should be an integral part of the development strategy for all new Haskell libraries. Don't write code without it! Binary is portable, using the foreign function interface and cpp, and is tested with Hugs and GHC. Happy hacking! The Binary Strike Team, Lennart Kolmodin Duncan Coutts Don Stewart Spencer Janssen David Himmelstrup Bjorn Bringert Ross Paterson Einar Karttunen

19 50

DevRandom
by Yitzchak Gale 01 Feb '07

01 Feb '07

Have I re-invented the wheel yet again? I have a module the following simple functions, that I have been using for some time: -- Read data from the system random device. -- Return Nothing if there is currently not -- enough entropy in the system random device. devRandom :: Storable a => IO (Maybe a) -- Read data from the system random device. -- If necessary, wait until there is -- enough entropy in the system random device. devRandomWait :: Storable a => IO a -- Read data from the system random device. -- If there is currently not enough entropy -- in the system random device, use a lower -- quality source of randomness instead. devURandom :: Storable a => IO a These are currently implemented only for platforms that have a /dev/random and /dev/urandom device, i.e., Unix-like. I know how to implement the third function - devURandom - on Windows, but I don't currently have a Windows box on which I can compile Haskell. I don't know how to implement the other two functions on Windows. This seems like something that is important to be in the standard library, or at least publicly accessible. Is it out there already and I am just missing it? If not, what is the best way to make this available? Is there someone who would like to do the Windows part? -Yitz

2 5

OT: Hugs users mailing list down?
by Fernan Bolando 01 Feb '07

01 Feb '07

Is the hugs mailing list down? Anybody experiencing zero trafic from hugs-users.. regards ,Fernan -- Public PGP/GnuPG key (http://www.fernski.com) pub 1024D/3576CA71 2006-02-02 Fernan Bolando Key fingerprint = FDFE C9A8 FFED C1A5 2F5C EFEB D595 AF1C 3576 CA71

1 0

Is Excel the most used -- and fucntional -- programming lanuage on Earth?
by Alexy Khrabrov 31 Jan '07

31 Jan '07

Heard that statement recently -- that Excel is a functional programming language, and the most used one -- of any programming languages -- on Earth! Is it true? Are there good examples of typical FP style in Excel? Cheers, Alexy

10 11

What is the best way to understand large programs?
by Stefan O'Rear 31 Jan '07

31 Jan '07

Hello. I am trying to fully understand yi as quickly as possible. Yi, like most big programs, consists of a number of modules; e.g. Yi.UI, Yi.Buffer, etc. Since I am not smart enough to understand all the modules at once, I am trying to understand them one at a time (is this itself the problem?); however, since mutual dependencies exist, I can't do it that easily, since understanding module A requires knowledge of the interface of module B requires knowledge of the implentation of module B requires knowledge of the interface of module A requires knowledge of the implementation of module B (and my brain's lazy fix is not very good). Yi has haddock-style comments (despite not being a library), so I tried using ./Setup.lhs haddock for readable side references, however this failed on CPP markup. After asking on #haskell, newsham noted that he had filed a cabal bug (#102), but the bug's page notes: Haddock generates interface documentation. That's only appropriate for libraries, isn't it? So, if haddock isn't what I want, what is? Or am I going at this completely wrong? What is the recommended way to approach a largish program like yi or lambdabot? (and if haddock is the wrong way to handle this, why does yi have haddock comments?) Note: I *have* managed to pretty thourougly understand lambdabot, but it took a while, wasn't particularly easy, and anyway lambdabot's dependency groups are quite small compared to eg lambdabot's. I'm hoping to make things easier for myself. Stefan

6 7

Re: [Haskell-cafe] GADTs: the plot thickens?
by Conor McBride 31 Jan '07

31 Jan '07

Hi Bruno This looks like the stuff! > Lets also have naturals reflected at the value level: > > > data Nat :: * -> * where > > Zero :: Nat Z > > Succ :: Nat n -> Nat (S n) Good plan. Of course, if you combine this method with Pablo's suggestion, you can make the class RepNat n whose method is repNat :: Nat n and then wrap your explicit versions in implicit versions. Implicit information inferred from type information but passed at run time: it's something we need to get used to. I'm glad we only need three definitions of the natural numbers, none of which is data Nat = Zero | Succ Nat > Now we modify thin to take an extra Nat n (not needed, but just to > show the duality with thickening): > > > thin :: Nat n -> Fin (S n) -> Fin n -> Fin (S n) > > thin n Fz i = Fs i > > thin (Succ n) (Fs i) (Fz) = Fz > > thin (Succ n) (Fs i) (Fs j) = Fs (thin n i j) > > The thing to note here is that only: > > > thin (Succ n) (Fs i) (Fz) = Fz > > is well typed; if you had the case: > > > thin Zero (Fs i) (Fz) = Fz > > you get: > > Conor.lhs:28:21: > Inaccessible case alternative: Can't match types `S n' and `Z' > In the pattern: Fz > In the definition of `thin': thin Zero (Fs i) (Fz) = Fz > Failed, modules loaded: none. That's a relief. Of course, in Epigram, you get that n is a successor for free, the moment you look at an element of Fin n. > Now lets go for the thickening function: > > > thicken :: Nat n -> Fin (S n) -> Fin (S n) -> Maybe (Fin n) > > thicken n Fz Fz = Nothing > > thicken n Fz (Fs j) = Just j > > thicken Zero (Fs i) Fz = Nothing > > thicken (Succ _) (Fs i) Fz = Just Fz > > thicken (Succ n) (Fs i) (Fs j) = fmap Fs (thicken n i j) > > Note that this version of thicken is more precise than the version you > had -- your third case splits into two > different cases now. The problem is that when you had: > > > thicken (Fs i) Fz = ... > > you need to account for two possibilities: the first possibility is > (Fz :: Fin (S Zero)), to which you want to return Nothing > and (Fz :: Fin (S (S n))) for which you can safely return Just Fz. I thought that might work. Your solution is quite close to the Epigram version of the program, but you haven't covered the Zero (Fs i) (Fs j) case, which is impossible anyway. I suggest the following minor modification, whose significance is purely documentary. > thicken :: Nat n -> Fin (S n) -> Fin (S n) -> Maybe (Fin n) > thicken n Fz Fz = Nothing > thicken n Fz (Fs j) = Just j > thicken Zero (Fs i) j = undefined {- i stinks -} > thicken (Succ _) (Fs i) Fz = Just Fz > thicken (Succ n) (Fs i) (Fs j) = fmap Fs (thicken n i j) The Epigram version explicitly refutes i in the case where it inhabits Fin Z. I thought of this example because of the other thread about empty cases. > Let me know if that helps. It certainly delivers the necessary explanation. What has happened here? Somehow, we discovered that we had to shift some data from the static language to the dynamic language so that we could give the compiler enough information to see what was ok about the program we started with. There's something subtle here. If the compiler just magically swallowed my earlier program, I think we'd lose type safety, because it allows us to manufacture a non-_|_ inhabitant of (Fin Z) fromJust (thicken (Fs undefined) Fz) = Fz :: Maybe (Fin Z) So you really need a safety check there. Another way to do it, crudely but avoiding the run time numbers, is this > thicken :: Fin (S n) -> Fin (S n) -> Maybe (Fin n) > thicken Fz Fz = Nothing > thicken Fz (Fs j) = Just j > thicken (Fs Fz) Fz = Just Fz > thicken (Fs Fz) (Fs j) = fmap Fs (thicken Fz j) > thicken (Fs (Fs i)) Fz = Just Fz > thicken (Fs (Fs i)) (Fs j) = fmap Fs (thicken (Fs i) j) That's just another way to get the strictness you need. Although it's ugly. Perhaps it's possible to pack up the explanation "every element of a finite set is an element of a nonempty finite set" as some sort of view, although not the sort of view currently being proposed, I guess. Exactly what information is needed in which phase and how totality or its absence affects what's possible are interesting and subtle questions. We live in interesting times. All the best Conor

2 1

(no subject)
by TFP 2007 31 Jan '07

31 Jan '07

Dear Colleagues, Apologies in advance for the "p.m." ommission. This is a kind reminder that the deadline for extended abstract submissions to TFP 2007 is tomorrow, Feb. 1 at 11:59 p.m. EST. We are also pleased to announce that the TFP 2007 invited speaker is John McCarthy, Stanford University. For further details, please visit our website at: http://cs.shu.edu/tfp2007/ . The TFP 2007 program committee looks forward to receiving your submissions! Best wishes, Marco ************************************************************************************ Dr. Marco T. Morazan TFP 2007 Program Committee Chair http://cs.shu.edu/tfp2007/

1 0

TFP 2007 Submission Deadline is Tomorrow
by TFP 2007 31 Jan '07

31 Jan '07

Dear Colleagues, This is a kind reminder that the deadline for extended abstract submissions to TFP 2007 is tomorrow, Feb. 1 at 11:59 EST. We are also pleased to announce that the TFP 2007 invited speaker is John McCarthy, Stanford University. For further details, please visit our website at: http://cs.shu.edu/tfp2007/ . The TFP 2007 program committee looks forward to receiving your submissions! Best wishes, Marco ************************************************************************************ Dr. Marco T. Morazan TFP 2007 Program Committee Chair http://cs.shu.edu/tfp2007/

1 0

GADTs: the plot thickens?
by Conor McBride 31 Jan '07

31 Jan '07

Hi folks A puzzle for you (and for me too). I just tried to translate an old Epigram favourite (which predates Epigram by some time) into GADT-speak. It went wrong. I had a feeling it might. I wonder how to fix it: I imagine it's possible to fix it, but that some cunning may be necessary. Here it is: Type-level Nat > data Z = Z > data S x = S x Finite sets: Fin Z is empty, Fin (S n) has one more element than Fin n > data Fin :: * -> * where > Fz :: Fin (S n) > Fs :: Fin n -> Fin (S n) The "thinning" function: thin i is the order-preserving embedding from Fin n to Fin (S n) which never returns i. > thin :: Fin (S n) -> Fin n -> Fin (S n) > thin Fz i = Fs i > thin (Fs i) Fz = Fz > thin (Fs i) (Fs j) = Fs (thin i j) Its partial inverse, "thickening" has the spec thicken i i = Nothing thicken i (thin i j) = Just j > thicken :: Fin (S n) -> Fin (S n) -> Maybe (Fin n) > thicken Fz Fz = Nothing > thicken Fz (Fs j) = Just j > thicken (Fs i) Fz = Just Fz > thicken (Fs i) (Fs j) = fmap Fs (thicken i j) The trouble is that whilst thin compiles, thicken does not. GHC rightly complains Thicken.lhs:18:32: Couldn't match expected type `n' (a rigid variable) against inferred type `S n1' `n' is bound by the type signature for `thicken' at Thicken.lhs:15:19 Expected type: Fin n Inferred type: Fin (S n1) In the first argument of `Just', namely `Fz' In the expression: Just Fz The trouble is that (Fs i) is only known to be of some type Fin (S n), so we need to return the Fz :: Fin n, and there ain't no such beast. The question is how to explain that this program actually does make some sense. One to ponder. Cheers Conor

2 1

Re: [Haskell-cafe] GADTs: the plot thickens?
by Bruno Oliveira 31 Jan '07

31 Jan '07

Hello Conor, The following seems to work: On 31 Jan 2007, at 11:46, Conor McBride wrote: > Hi folks > > A puzzle for you (and for me too). I just tried to translate an old > Epigram favourite (which predates Epigram by some time) into GADT- > speak. It went wrong. I had a feeling it might. I wonder how to fix > it: I imagine it's possible to fix it, but that some cunning may be > necessary. Here it is: > > Type-level Nat > > > data Z = Z > > data S x = S x > Lets also have naturals reflected at the value level: > data Nat :: * -> * where > Zero :: Nat Z > Succ :: Nat n -> Nat (S n) > > Finite sets: Fin Z is empty, Fin (S n) has one more element than Fin n > > > data Fin :: * -> * where > > Fz :: Fin (S n) > > Fs :: Fin n -> Fin (S n) > > The "thinning" function: thin i is the order-preserving embedding > from Fin n to Fin (S n) which never returns i. > Now we modify thin to take an extra Nat n (not needed, but just to show the duality with thickening): > thin :: Nat n -> Fin (S n) -> Fin n -> Fin (S n) > thin n Fz i = Fs i > thin (Succ n) (Fs i) (Fz) = Fz > thin (Succ n) (Fs i) (Fs j) = Fs (thin n i j) The thing to note here is that only: > thin (Succ n) (Fs i) (Fz) = Fz is well typed; if you had the case: > thin Zero (Fs i) (Fz) = Fz you get: Conor.lhs:28:21: Inaccessible case alternative: Can't match types `S n' and `Z' In the pattern: Fz In the definition of `thin': thin Zero (Fs i) (Fz) = Fz Failed, modules loaded: none. > > Its partial inverse, "thickening" has the spec > > thicken i i = Nothing > thicken i (thin i j) = Just j > > Now lets go for the thickening function: > thicken :: Nat n -> Fin (S n) -> Fin (S n) -> Maybe (Fin n) > thicken n Fz Fz = Nothing > thicken n Fz (Fs j) = Just j > thicken Zero (Fs i) Fz = Nothing > thicken (Succ _) (Fs i) Fz = Just Fz > thicken (Succ n) (Fs i) (Fs j) = fmap Fs (thicken n i j) Note that this version of thicken is more precise than the version you had -- your third case splits into two different cases now. The problem is that when you had: > thicken (Fs i) Fz = ... you need to account for two possibilities: the first possibility is (Fz :: Fin (S Zero)), to which you want to return Nothing and (Fz :: Fin (S (S n))) for which you can safely return Just Fz. Let me know if that helps. Cheers, Bruno

2 3