August 2008 - Haskell-Cafe

External Sort and unsafeInterleaveIO
by Ben 11 Oct '08

11 Oct '08

hi folks -- a haskell newbie here, searching for comments and wisdom on my code. i had a project to try to implement "external sort" in haskell as a learning exercise. (external sort is sorting a list that is too large to fit in main memory, by sorting in chunks, spooling to disk, and then merging. more properly there probably should be multiple stages, but for simplicity i'm doing a one-stage external sort.) the trick is the number of files can quickly grow very large, so it is best to use one large file and seek inside it around. however as one can imagine the order-of-IO-operations becomes a bit tricky, if you're seeking file handles around underneath Data.ByteString.Lazy's nose. but late this night after not thinking about it for a while i had a brainstorm: rewrite hGetContents to keep the handle position in the right place! it's all about judicious use of unsafeInterleaveIO..... it seems to be rather fast, strangely faster than the usual "sort" at times. it also seems to have nice memory characteristics, though not perfect. it's hard to test because the normal "sort" function takes too much RAM on large lists, making my computer swap like mad. i'd appreciate any testing, comments and suggestions from the haskell gods out there. my thanks to the Data.ByteString.Lazy, Data.Binary, and Data.Edison people, who made this rather easy, once I grokked unsafeInterleaveIO. thanks and take care, B > module ExternalSort where Sort a list of Ords "offline." We're doing this to be able to sort things without taking up too much memory (for example sorting lists too large to fit in RAM.) Laziness is imperative, as is the order-of-operations. > import Control.Monad > import Data.List > import qualified Data.Binary as Bin > import qualified Data.ByteString.Lazy as B > import qualified Data.ByteString as P (hGetNonBlocking, null) > import Data.ByteString.Base (LazyByteString(LPS)) > import Foreign.Storable (sizeOf) > import System.IO (openFile, hClose, hSeek, hTell, hIsEOF, hWaitForInput, > Handle, IOMode(ReadMode, WriteMode), > SeekMode(AbsoluteSeek)) > import System.IO.Unsafe (unsafeInterleaveIO) > > import qualified Data.Edison.Seq.ListSeq as LS > import qualified Data.Edison.Coll.SplayHeap as Splay Conceptually, we sort a list in blocks, spool blocks to disk, then merge back. However for IO performance it is better to read off chunks of elements off the sorted blocks from disk instead of elements-at-a-time. It would be better if these were in KBytes instead of # of elements. > blocksize :: Int > blocksize = 10000 Turn a list into a list of chunks. > slice :: Int -> [a] -> [[a]] > slice _ [] = [] > slice size l = (take size l) : (slice size $ drop size l) Turn a list into a list of blocks, each of which is sorted. > blockify :: (Ord a) => Int -> [a] -> [[a]] > blockify bsize l = map sort $ slice bsize l Serialize a block, returning the (absolute) position of the start. > dumpBlock :: (Ord a, Bin.Binary a) => Handle -> [a] -> IO Integer > dumpBlock h b = do > start <- hTell h > B.hPut h $ Bin.encode b > return start The actual sorting function. We blockify the list, turning it into a list of sorted blocks, and spool to disk, keeping track of offsets. We then read back the blocks (lazily!), and merge them. > externalSort [] = do return [] > externalSort l = do > h <- openFile "ExternalSort.bin" WriteMode > idx <- mapM (\x -> dumpBlock h x) (blockify blocksize l) > hClose h > h <- openFile "ExternalSort.bin" ReadMode > blocks <- mapM (\x -> do {bs <- hGetContentsWithCursor h x; > return $ Bin.decode bs}) idx > return (kMerge $ blocks) Merging chunks. K-way merge (and in fact external sort in general) is detailed in Knuth, where he recommends tournament trees. The easiest thing is to probably use one of Okasaki's heaps. I'll use splay heaps, because I don't know any better. It would be better if I changed Ord for blocks to only check the first element. > kMerge :: (Ord a) => [[a]] -> [a] > kMerge [] = [] > kMerge l = > let h = Splay.fromSeq l in > kM (Splay.minElem h) (Splay.deleteMin h) > where > kM :: (Ord a) => [a] -> Splay.Heap [a] -> [a] > kM l h > | h == Splay.empty = l > | otherwise = > let next = Splay.minElem h > (f, b) = span (\x -> x <= head next) l > in > f ++ (kM next (if null b then Splay.deleteMin h > else (Splay.insert b $ Splay.deleteMin h))) > > kMergeSort :: (Ord a) => [a] -> [a] > kMergeSort l = kMerge $ blockify blocksize l This is a version of hGetContents which resets its handle position between reads, so is safe to use with interleaved handle seeking. > hGetContentsWithCursor :: Handle -> Integer -> IO B.ByteString > hGetContentsWithCursor = hGetContentsWithCursorN defaultChunkSize > > hGetContentsWithCursorN :: Int -> Handle -> Integer -> IO B.ByteString > hGetContentsWithCursorN k h start = (lazyRead start) >>= return . LPS > where > lazyRead start = unsafeInterleaveIO $ loop start > > loop start = do > hSeek h AbsoluteSeek start > ps <- P.hGetNonBlocking h k > --TODO: I think this should distinguish EOF from no data available > -- the otherlying POSIX call makes this distincion, returning either > -- 0 or EAGAIN > if P.null ps > then do eof <- hIsEOF h > if eof then return [] > else hWaitForInput h (-1) > >> (loop start) > else do > pos <- hTell h > pss <- lazyRead pos > return (ps : pss) > > defaultChunkSize :: Int > defaultChunkSize = 32 * k - overhead > where k = 1024 > overhead = 2 * sizeOf (undefined :: Int)

5 6

Exceptions
by Adrian Neumann 18 Sep '08

18 Sep '08

Hello, I think it'd be nice if the compiler could warn me if there are any exceptions which I'm not catching, similar to checked exceptions in Java. Does anyone know of a possibility to do that in Haskell? Adrian

6 6

SYB with class: Bug in Derive.hs module
by Alexey Rodriguez Yakushev 16 Sep '08

16 Sep '08

Hi people (and Ralf and Alex), I found a bug in the SYB with class library when trying to implement generic equality. I am hoping that someone in the Cafe (maybe Ralf) can confirm it is a bug, or maybe show me that I am doing something wrong. I am using the "Scrap your boilerplate with class" library (http:// homepages.cwi.nl/~ralf/syb3/). More precisely, I am using the library distributed by the HAppS project, because it works with GHC 6.8 . You can get the repository as follows: darcs get http://happs.org/HAppS/syb-with-class However, the offending module (Derive.hs) produces broken instances in both distributions. The bug: ---------- Generic equality needs type safe casting when implemented in SYB3, I have tried both the gzipwith variant and using Pack datatypes (geq*.hs in the first distribution). However, both functions loop when applied to a tree value. This loop occurs when the functions try to cast one of the arguments. I have managed to reduce the error to a smaller source file that I send attached. It does the following: > main = print typeReps > > tree = (Bin (Leaf 1) (Leaf 2))::BinTree Int > > data Pack = forall x. Typeable x => Pack x > > packedChildren = gmapQ geqCtx Pack tree > > typeOfPack (Pack x) = typeOf x > > typeReps = map typeOfPack packedChildren Basically the tree is transformed into a list of Pack-ed values and then to a list of type representations. This program loops at "typeOf" when you call "main". The Data instance that Derive generates is as follows: > instance (Data ctx a, > Data ctx (BinTree a), > Sat (ctx (BinTree a))) => > Data ctx (BinTree a) where Note the recursive |Data ctx (BinTree a)| in the context. If I get rid of it (a correct manual instance is also included in the attachment) the example works. I thought of removing this from the context in the Derive source. But maybe I might break some other use cases. So I am asking for help! Should Derive be fixed? How? Cheers, Alexey

3 2

ANN: vxml (validating xml lib) - proof of concept - need some guidance - bad type level performance (ghc)
by Marc Weber 12 Sep '08

12 Sep '08

Hi @ll. This shouldn't have been an announce yet.. it's more crying for help to get to know how / wether to continue :-) I had an idea: a xml generating library validating the result against a given dtd (to be used in web frameworks etc .. ) After one week of coding I got the result git clone git://mawercer.de/vxml (1) (see README) git hash as of writing : 4dc53 A minimal example looks like this (taken from test.hs): import Text.XML.Validated.TH $( dtdToTypes "dtds/xhtml1-20020801/DTD/xhtml1-strict_onefile.dtd" (XmlIds (Just "-//W3C//DTD XHTML 1.0 Strict//EN") (Just "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd") ) ) main = putStrLn $ xml $ ((html << (head << (title <<< "vxml hello world"))) << (body << (div <<< "PCDATA text" )) ) Which takes about 7 secs to compile on my (fast) 2.5 Ghz machine. Before Oleg telling me about how to use the TypeEq implementation found in HList it took several hours (switch the cabal configure flag to see experience the incredible slow TypeToNat implementation) However type checking the simple small document (2) already takes 35 seconds, duplicating the tags within the body raises compilation time to 74 seconds. (Have a look at test/XmlToQ.hs to automatically create the code generating such a given xml file (its used in run-testcases.hs) The dtd representation used is very easy to understand: (3a) shows allowed subelements of the head tag Seq = sequence Star = zero or more ... (3b) shows the list of allowed attributes for a more commonly used tag such as div the element list (3a) is 324 lines long and there are approximately 15 attributes. Use a line such as putStrLn $ xml $ debugEl div to get this view. All the work is done by class Consume st el r | st el -> r -- result is on of C,CS,R,F class Retry elType st el st' | st el -> st' st = state as given in (3a) el = child to be added (Elem Html_T) or PCDATA C = element consumed, end CS a = element consumed, continue with state a R a = retry with given state (can happen after removing a Star = ()* on a no match ) F a = no match, show failure a instance Retry elType C el C instance Retry elType (CS st) el st instance ( -- retry Consume st el r , Retry elType r el st' ) => Retry elType (R st) el st' Maybe you knowing much more about ghc internals have some more ideas how to optimize? I only came up with a) implement xml HTrue $ xmldoc -- type checking variant xml HFalse $ xmldoc -- unchecked but faster variant so you can run xml HTrue once a day only while having lunch.. ( doubt Maybe you have to take lunch two or more times on intermediate web projects .. ) b) change (A attrType) to attrType only and (Elem e) to e which does not work for the same reason as class TypeEq a b c | a b -> c instance TypeEq a a HTrue instance TypeEq a b HFalse doesn't. Of course a a will match a b as well, but the result is totally different.. So would it be possible to either tell ghc to ignore this happily taking the result of the better matching instance? Or to explicitely tell ghc when an instance matches the way it does in current implementations make it a no match if some constraints can or cannot be satisfied such as this: class TypeEq a b c | a b -> c instance TypeEq a a HTrue instance [ NoMatchOn a b -- if this can be satisfied ignore this instance ] => TypeEq a b HFalse class NoMatchOn a b instance NoMatchOn a a c) Having a reduction rule such as this: If the left side of (Or a b) returnns C (consumed) tell ghc to not evaluate the result of (Consume b element result) which must be done to see wether there is closer instance match (Is this correct ?) Of course not everything is implemented yet.. but except speed I consider it beeing quite usable. He, thanks for reading till the end. Any feedback and suggestions are appreciated. If you have any trouble contact me on irc. I've been using $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.8.2 Sincerly Marc Weber (1) If you are interested and either don't have git or are not familiar using it I can send you a tarball. (2) <!DOCTYPE html SYSTEM "/tmp/dtd.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="en-US" xml:lang="en-US"> <head> <title>Example 6 - XHTML 1.0 Strict as application/xhtml+xml</title> <meta http-equiv="Content-Type" content="application/xhtml+xml; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="style.css" /> </head> <body> <h1>Example 6 - XHTML 1.0 Strict as application/xhtml+xml</h1> <p> This document is valid XHTML 1.0 Strict served as <code>application/xhtml+xml</code>. </p> <p> This document references CSS rules contained in an external stylesheet via <code>link</code>. </p> <p> Note how the CSS rules for the background are applied in Netscape 7.x, Mozilla, Opera 7 but that Internet Explorer can not display the page at all. </p> <p> <a href="http://validator.w3.org/check/referer"><img src="http://www.w3.org/Icons/valid-xhtml10" alt="Valid XHTML 1.0!" height="31" width="88" /></a> </p> </body> </html> (3a) (Seq (Star (Or (Elem Script_T) (Or (Elem Style_T) (Or (Elem Meta_T) (Or (Elem Link_T) (Elem Object_T)))))) (Or (Seq (Elem Title_T) (Seq (Star (Or (Elem Script_T) (Or (Elem Style_T) (Or (Elem Meta_T) (Or (Elem Link_T) (Elem Object_T)))))) (Query (Seq (Elem Base_T) (Star (Or (Elem Script_T) (Or (Elem Style_T) (Or (Elem Meta_T) (Or (Elem Link_T) (Elem Object_T)))))))))) (Seq (Elem Base_T) (Seq (Star (Or (Elem Script_T) (Or (Elem Style_T) (Or (Elem Meta_T) (Or (Elem Link_T) (Elem Object_T)))))) (Seq (Elem Title_T) (Star (Or (Elem Script_T) (Or (Elem Style_T) (Or (Elem Meta_T) (Or (Elem Link_T) (Elem Object_T))))))))))) (3b) (HCons (A Lang_A) (HCons (A Xml:lang_A) (HCons (A Dir_A) (HCons (A Id_A) (HCons (A Profile_A) HNil)))))

2 7

Re: [Haskell] Top Level <-
by Adrian Hey 08 Sep '08

08 Sep '08

I have a feeling this is going to be a very long thread so I'm trying to go to Haskell cafe again (without mucking it up again). Derek Elkins wrote: > Haskell should be moving -toward- a capability-like model, not away from > it. Could you show how to implement Data.Random or Data.Unique using such a model, or any (preferably all) of the use cases identified can be implemented? Like what about implementing the socket API starting with nothing but primitives to peek/poke ethernet mac and dma controller registers? Why should Haskell should be moving -toward- a capability-like model and why does top level <- declarations take us away from it? Regards -- Adrian Hey

21 178

language proposal: ad-hoc overloading
by Ryan Ingram 07 Sep '08

07 Sep '08

The point of having a strongly typed language is so the compiler can do more work for you. But right now I do a lot of typing (pun not intended) to appease the compiler. Let me give you an example: module Prob where import qualified Data.Map as M ... newtype Prob p a = Prob { runProb :: [(a,p)] } combine :: (Num p, Ord a) => Prob p a -> Prob p a combine m = Prob $ M.assocs $ foldl' (flip $ uncurry $ M.insertWith (+)) M.empty $ runProb m Do you see it? All those "M." just seem dirty to me, especially because the compiler should be able to deduce them from the types of the arguments. My proposal is to allow "ad-hoc" overloading of names; if a name is ambiguous in a scope, attempt to type-check the expression against each name. It is only an error if type-checking against all names fails. If type-checking succeeds for more than one then the expression is ambiguous and this is also an error. Pros: shorter code, less busywork to please the compiler Cons: potentially exponential compile time? Any thoughts? -- ryan

16 25

2 modules in one file
by Maurício 05 Sep '08

05 Sep '08

Hi, Is it allowed to write two different modules in a single file? Something like: module Mod1 (...) where { ... } module Mod2 (...) where { import Mod1; ... } I tried, and got an error, but would like to confirm that there's no way to do that. Thanks, Maurício

7 10

Re: [Haskell-cafe] Re: [Haskell] Top Level <-
by Ganesh Sittampalam 05 Sep '08

05 Sep '08

On Sun, 31 Aug 2008, Adrian Hey wrote: > Ganesh Sittampalam wrote: >> On Sun, 31 Aug 2008, Adrian Hey wrote: >> >>> Thanks for taking the time to do this Dan. I think the safety requirement >>> has been met, but I think it fails on the improved API. The main complaint >>> would be what I see as loss of modularity, in that somehow what should be >>> a small irrelevant detail of the implementation of some obscure module >>> somewhere has propogated it's way all the way upto main. >> >> That's the key point, as I see it - they aren't "irrelevant details of the >> implementation", they are requirements the implementation places on its >> context in order for that implementation to be correct. So they should be >> communicated appropriately. > > Eh? Please illustrate your point with Data.Unique. What requirements > does it place on it's context? (whatever that might mean :-) It requires that its context initialises it precisely once. Data.Unique is actually a poor example, as it is actually fine to initialise it multiple times as long as the resulting Unique values aren't treated as coming from the same datatype. But equally it can be implemented with IORefs, so it's not a good advert for the need for global variables. > The real irony of your remark is that making APIs this robust is > practically impossible *without* using global variables, and you're > now saying that because they've done this work to eliminate these > constraints they now have to be held to account for this with > an absurd API. I think there are two cases to consider here. A Data.Unique style library, which requires genuinely *internal* state, and which is agnostic to having multiple copies of itself loaded simultaneously. In that case, there is no requirement for a process-level scope for <-, just that each instance of the library is only initialised once - the RTS can do this, as can any dynamic loader. The other is some library that really cannot be safely loaded multiple times, because it depends on some lower-level shared resource. Such a library simply cannot be made safe without cooperation from the thing that controls that shared resource, because you cannot prevent a second copy of it being loaded by something you have no control over. If the <- proposal were only about supporting the first of these applications, I would have far fewer objections to it. But it would have nothing to do with process-level scope, then. Ganesh

5 11

Compiler's bane
by Andrew Coppin 04 Sep '08

04 Sep '08

Hi guys. I'm writing a simple interpretter for a small extended-lambda-calculus sort of language. And I'd just like to say... RECURSIVE LET-BINDS! GAAAAH!!! >_< No other part of the program has consumed nearly as much brain power as me trying to figure out when it is and isn't safe to replace a variable with its RHS. To illustrate: let x = f x; y = 5 in x y A simple-minded interpretter might try to replace every occurrance of "x" with "f x". This yields let y = 5 in (f x) y ...and x is now a free variable. OOPS! Trying to tease out exactly under which conditions you can and cannot perform the substitution is utterly maddening. Since this is a Haskell mailing list and as such it is populated by vast numbers of people with PhDs and so forth... does anybody happen to know the *correct* solution to this conundrum? Before I become clinically insane...? o_O By the way... To all those people who work on projects like GHC and so on, who have to get this stuff right "for real": you have my infinite respect!

10 29

Haskell audio libraries & audio formats
by Eric Kidd 03 Sep '08

03 Sep '08

Greetings, Haskell folks! I'm working on a toy program for drum synthesis. This has lead me to explore the various sound-related libraries in Hackage. Along the way, I've learned several things: 1. There's a lot of Haskell sound libraries, but no agreement on how to represent buffers of audio data. 2. Some of the most useful sound libraries aren't listed in Hackage's "Sound" section, including HCodecs, SDL-mixer and hogg. 3. The Haskell OpenAL bindings are great, but ALUT has been removed from MacOS 10.5. Of course, a pure-Haskell version of ALUT would be pretty easy to write, and it could be used as a fallback. 4. '[[a]]' is _not_ a good representation for multi-channel audio data. Manipulating even 10 seconds of audio is noticeably slow. 5. HCodecs is probably the best library for reading WAVE files. It uses 'DiffUArray Int a' to represent audio data, and not '[[a]]'. It also supports MIDI and SoundFont, which is quite handy. 6. YampaSynth looks really cool, and it might be possible to turn it into a reusable MIDI synthesizer library for use with HCodecs. This would be extremely useful: it would provide a basis for all kinds of crazy MIDI-based programming in Haskell. At the end of this e-mail, you can find a list of Haskell sound libraries and their supported audio formats. What would the ideal Haskell sound API look like? Personally, I would love to see: a. Something like HCodecs's Data.Audio as the basic sound format. Data.Audio is an array-based API, and it supports converting between a wide range of common sample formats. I don't know how fast this is, but it already exists, and it's used by YampaSynth. b. OpenAL for sound playback, with a portable version of ALUT. This may require writing a pure-Haskell version of ALUT. c. Utility functions to convert Data.Audio to OpenAL.AL.Buffer. d. An easy-to-use API for audio processing. It might be possible to start with something like Jack's 'mainMono' and 'mainStereo' functions, which map a function over an audio stream. Other nice-to-have features might include: e. A standard MIDI format, based on either the HCodecs package or the midi package. (HCodecs is used by YampaSynth, and the midi package is used by alsa-midi.) f. A modular version of YampaSynth which can convert MIDI data structures into Data.Audio values. It looks like Haskell could be a really sweet audio programming environment with just a bit of integration work. What do folks think? Are there other libraries I should look at more closely? Other features that should be included in an ideal audio API? Thank you for your advice and feedback! Cheers, Eric Haskell audio libraries Reading and writing sound files: HCodecs: (Audible a) => DiffUArray Int a hsndfile: MArray with Float and Double HSoundFile: [[Double]] ALUT: OpenAL.AL.Buffer WAVE: [[Int32]] Playing sounds: OpenAL: Ptr UInt8, Ptr Int16, 1-N channels SDL-mixer: ForeignPtr ChunkStruct, ForeignPtr MusicStruct Sound processing libraries: dsp: Array a, [a] jack: Operates via mapping functions mainMono :: (CFloat -> IO CFloat) -> IO () mainStereo :: ((CFloat, CFloat) -> IO (CFloat, CFloat)) -> IO () MIDI-based: HCodecs: Reads and writes MIDI files midi: Reads and writes MIDI files alsa-midi: Uses midi library YampaSynth: Stand-alone program Special-purpose APIs only (FFIs, etc.): hCsound: CsoundPtr hsc3: UGen No public sound-buffer API: hbeat: The relevant source files are missing! hogg: Very low-level API for Ogg internals only libmpd: No sound buffer API sonic-visualizer: No sound buffer API truelevel: Stand-alone program (uses WAVE) wavconvert: Stand-alone program

6 14