- Haskell-Cafe - Haskell.org

what is a stack overflow?
by S. Alexander Jacobson 24 Jan '05

24 Jan '05

GHC assumes the user knows the difference between the heap and the stack. I don't. No matter how much heap I specify on the GHCi command line, I get a stack overflow exception. I have no idea what that means or how to remedy it. Hints? Note: My program is basically creating a few 100k item FiniteMaps. I don't think that should exceed the memory on my laptop.... -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

1 0

File path programme
by Mark Carroll 24 Jan '05

24 Jan '05

I tried writing a little command-line utility to find the relative path of one thing from another thing (with Unix-like systems in mind). For example, $ ./pathfromof /etc/init.d/ /etc/X11/XF86Config-4 ../X11/XF86Config-4 $ ./pathfromof /tmp/baz/ /tmp/foo/ . $ ls -l /tmp/baz lrwxr-xr-x 1 markc markc 8 2005-01-20 12:01 /tmp/baz -> /tmp/foo It turned out surprisingly complex, though, and doesn't feel very neat or tidy at all, nor is it very portable given that I couldn't find generic library functions for manipulating bits of filepaths. Anyhow, it's at http://www.chiark.greenend.org.uk/~markc/PathFromOf.hs and may yet have egregious bugs. It seems to me like it could certainly be improved in various ways. If anyone has any thoughts, as to how I could improve my style, make more use of standard libraries, etc., I'd certainly appreciate them. Thanks, Mark

7 7

HaXmL and the IO Monad
by John Goerzen 24 Jan '05

24 Jan '05

I've been playing with HaXmL lately. I've had a need to convert one XML document to another, and HaXmL was very nice for that. Along the way, I've discovered that I need to do some I/O as part of the conversion (specifically due to timezone-related calculations). Much of HaXML is based around the CFilter type: type CFilter = Content -> [Content] That is, most of the stuff one does in HaXML is a function with that type. Try as I might, I could not figure out a nice way to integrate I/O into this system. A simple IO CFilter wouldn't work, since there has to be input available when it runs. Content -> IO [Content] didn't work either, since the IO ripples up all the way to the top, messing up the nice code everywhere. I finally resorted to unsafePerformIO to get it done. But I'd like to know the proper solution. I do hope that this is not it :-) Thanks, John

4 3

Re: [Haskell-cafe] weird behavior using HUnit
by Keith Wansbrough 24 Jan '05

24 Jan '05

> > GHC's memory profiling? > > I just gave it a try: when compiled with -prof -auto-all, my program > is memory hungry in both cases, so I cannot really compare... [cc'd back to list in case anyone else finds this useful; hope that's OK] Ah. The cost-centre annotations get in the way of the optimiser, preventing certain optimisations from being performed. It's possible that the new entry point you introduce with testParseLog is similarly preventing something from being inlined. The way to tell (sadly!) is to look at the intermediate code being generated by GHC. In fact there are several intermediate codes to look at. Most of the optimisation work is done while the program is in a form called "Core"; if you look at the result of the optimiser (sometimes called the "simplifier", confusingly) just before this Core is translated to STG you will get the most readable and useful information. http://www.haskell.org/ghc/docs/latest/html/users_guide/options-debugging.h… tells you how, and also explains how to read the output. -ddump-simpl is probably what you want, but it's a while since I've had a look - I could be wrong. Compare what you get with and without that HUnit line that's causing trouble, and see how the critical function is affected. HTH. --KW 8-)

1 0

weird behavior using HUnit
by Frédéric Gobry 24 Jan '05

24 Jan '05

Hello, I just experienced a weird problem while using HUnit. My code (a simple apache log analyser) used to run in constant space (thanks to the good suggestions and examples I received from the list :-)), and I wanted to add some unit tests. To my great surprise, the code started to eat up lots of memory again. I've isolated the problem down. It seems that if I declare my test suite with the line: testParseLog = HUnit.runTestTT (HUnit.TestList [_testUpdate]) then my code does not run in constant space anymore. Note that the testParseLog is not actually used, but only exported from the module, so that I can run it with ghc -e testParseLog. The code is attached. The line in question is at the end of ParseLog.hs, and I compiled the whole with ghc-6.2.2 (debian testing) Any hint ? thanks in advance, Frédéric -- Frédéric Gobry Infoscience DIT-KIS / EPFL Tel: +41216932288 http://people.epfl.ch/frederic.gobry

1 1

Randomly balanced binary trees
by Dominic Fox 23 Jan '05

23 Jan '05

Some more code that might be of interest to someone. Based on a suggestion by Alistair Turnbull, I've written a Haskell implementation of a randomly balanced binary tree. This merges tree updates with a stream of random numbers, which are used to shuffle the order of nodes in the tree so that it remains balanced. The code is posted together with a short explanation here: http://codepoetics.com/poetix/index.php?p=72 I would be especially interested in any suggestions relating to optimisation. Dominic

1 0

can't 'make install-docs'
by Daniel Fischer 21 Jan '05

21 Jan '05

Hi, I've just installed ghc-6.2.2, but couldn't get the docs made. I got the following: Text/Regex.raw-hs Text/Regex/Posix.raw-hs Text/Show.raw-hs Text/Show/Functions.raw-hs \ --package=base \ --dump-interface=base.haddock \ --use-index=../doc-index.html --use-contents=../index.html \ /bin/sh: line 1: t: command not found gmake[2]: [html/haddock.css] Error 127 (ignored) /usr/bin/install -c -m 644 html/* /usr/local/share/ghc-6.2.2/html/libraries/base /usr/bin/install: cannot stat `html/*': No such file or directory gmake[2]: *** [install-docs] Error 1 gmake[1]: *** [install-docs] Error 1 gmake[1]: Leaving directory `/usr/lib/ghc-6.2.2/libraries' gmake: *** [install-docs] Error 1 What can I do about it? helpless, Daniel

1 0

RE: [Haskell-cafe] Can't do basic time operations with System.Time
by Simon Marlow 21 Jan '05

21 Jan '05

On 20 January 2005 22:12, John Goerzen wrote: > I have a simple desire. I have a string that I need to parse as a > date/time string in the local timezone, then convert it to standard > seconds-since-epoch format. This is trivial in C, Perl, Python, etc. > but seems impossible to do reliably in Haskell. I'm hoping someone > can tell me where I've gone wrong. > > My initial idea was to parse the string, generate a CalendarTime > object, use toClockTime to convert it to seconds-since-epoch, and > then grab the value out of that. There were some problems, though: > what to put in ctTZ and ctIsDST? I initially loaded them with 0 and > False, though that turned out to be clearly wrong. > > My next idea was to take the ctTZ result from toCalendarTime, then use > that for all the CalendarTime objects I'd generate. That was wrong, > too, during daylight savings time. I don't think I should have to > re-implement the algorithms for determining whether a given date is > under DST worldwide. > > What I really need is just a wrapper around mktime() that just calls > mktime and doesn't do anything else. All the post-processing that > System.Time is doing is what's causing me trouble. I'd just like it > to ignore ctTZ, ctTZName, and ctIsDST. That would yield behavior > identical to the C library. If you set ctTZ to the UTC offset outside DST, and set ctIsDST to False, then toClockTime will do the DST calculation for you. ctTZ is the actual UTC offset (ie. it is adjusted for DST). Hence, toClockTime ignores ctIsDST when performing the conversion: it isn't necessary. I can't tell what's wrong here, if anything (general brokenness in the System.Time API notwithstanding). Ah *lightbuilb* - I think I see: you want to take a calendar time without any TZ information, assume it is a time at the current geographical location, and produce a CalendarTime for that. Hmm, it looks like the current API doesn't support that - toClockTime assumes you know the timezone. That's a shame. There's one way that's almost correct: take your initial calendar time, set ctTZ to your non-DST UTC offset, then call toClockTime and toCalendarTime on the result, and you'll get an appropriate ctTZ for that time. Plug the new ctTZ into the original time, and toClockTime again (you can shortcut this by adjusting the ClockTime directly). I'll leave it up to you how to handle the boundaries properly :-) Cheers, Simon

4 4

Re: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Udo Stenzel 21 Jan '05

21 Jan '05

Ben Rudiak-Gould <Benjamin.Rudiak-Gould(a)cl.cam.ac.uk> schrieb am 21.01.05 02:37:34: > If you're reading from a random-access file, there's no way [select] can tell > you when the file data is buffered, because it doesn't know which part > of the file you plan to read. The OS may try to guess for readahead > purposes, but select()'s behavior can't depend on that guess. The Glibc documentation says, "select determines if there is data available (more precisely, if a call to read(2) will not block)." I think, this is reasonably precise. The OS does know, where you are going to read (at the file pointer) and if you seek() or pread() instead, well, that is no call to read(2) and may change everything. Thus the question is, does select() reliably tell if read() would block or does it check for something else? Is the documentation wrong (on some platforms)? > This is another example of why the world would be better off with the > file/stream model. Have I convinced anyone? Uhm, well, me thinks, open() and read() on files quite accurately model a stream already... Udo. __________________________________________________________ Mit WEB.DE FreePhone mit hoechster Qualitaet ab 0 Ct./Min. weltweit telefonieren! http://freephone.web.de/?mc=021201

3 2

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was:Re: Somerandomnewbiequestions
by Simon Marlow 21 Jan '05

21 Jan '05

On 21 January 2005 16:27, Keean Schupke wrote: > Having read around I have found that select does return readable for > all file IO on a block device... > > I wonder if ghc could use non-blocking mode (files opened with the > O_NONBLOCK) flag? GHC does use the O_NONBLOCK flag. Cheers, Simon

1 0

RE: [Haskell-cafe] Can't do basic time operations with System.Time
by Simon Marlow 21 Jan '05

21 Jan '05

On 21 January 2005 14:31, John Goerzen wrote: > I checked the following code into MissingH. I would be pleased if you > could take it for fptools. I should note that I am using an Integer > rather than an Int to represent seconds, since I think that is proper > given the size of values we might be encountering. If you do take it > for fptools, you could probably rewrite normalizeTimeDiff to use the > very similar code in timeDiffToSecs (shameless almost-stealing here > <g>) Have you seen this, BTW: http://www.haskell.org/~simonmar/time/NewTime.html and a prototype implemention here: http://www.haskell.org/~simonmar/time/NewTime.hsc Everything to do with TimeDiff in the current library is generally acknowledged to be broken, so I don't think we'll be doing anything with that, short of completely replacing it. See previous discussions (if you have a lot of free time...). > timelocal :: CalendarTime -> IO Integer > timelocal ct = > do guessct <- toCalendarTime guesscl > let newct = ct {ctTZ = ctTZ guessct} > return $ timegm newct > where guesscl = toClockTime ct This looks useful, given that it was what you wanted and it isn't already provided. I'd prefer to drop it into the existing library, and have it return a ClockTime, though. Perhaps: -- | converts the given CalendarTime into a ClockTime, -- ignoring the ctTZ field of CalendarTime and instead -- using the prevailing local timezone (including daylight -- savings adjustments) at the given time. localTimeToClockTime :: CalendarTime -> IO ClockTime that's more or less a direct interface to mktime(). Cheers, Simon

2 1

Math libraries for Haskell
by Dmitri Pissarenko 21 Jan '05

21 Jan '05

Hello! Is there a math library for Haskell, using which one can calculate eigenvalues of matrices? Thanks in advance Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

6 7

Reading images
by Dmitri Pissarenko 21 Jan '05

21 Jan '05

Hello! I need to write a function in Haskell, which 1) reads a greyscale image (for instance, in JPEG, PNG or the like) and 2) transforms it into a n X m matrix A, where Aij contains an integer value (in the range 0 to 255). That integer value is zero for a completely black pixel, 255 for a completely white pixel and lies between zero and 255 for a grey pixel. In my program, I need ONLY to read an image and to transform it into such matrix. Which graphics library can you recommend, if no other image manipulation operations are required? TIA Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

5 4

Re: [Haskell] Implicit parallel functional programming
by Ben Lippmeier 21 Jan '05

21 Jan '05

Satnam Singh wrote: > Ample looks interesting. What license does it use? I had a quick look > over the source and can't find anything. Is there a port to Windows or > does it not do any OS specific UI/graphics? By default, we're releasing it under GPL. I guess I should place a copy of the license somewhere in the tarball... For the graphs it produces, it just emits a gnuplot source file (textfile, easy) and then automagically calls gnuplot to display that file. It would probably work straight out of the box under cygwin (or similar) with an appropriate build of gnuplot in your current path. Failing that, you (or I) could easilly comment out the "call gnuplot" stage and end up with a vanilla console-IO application. If it gives you any trouble then send me a mail and i'll fix it. ... There's also a paper that goes with it, which used to be on Clem's page but I see that the link is broken now, i'll get fixed. ... > > a (very slow) simulator you might want to poke around with. I wrote it > based around Clem Baker-Finch's "Abstract machine for parallel lazy > evaluation", which supports fully speculative implicit parallelism. > > There's a link to it on my homepage at > http://cs.anu.edu.au/people/Ben.Lippmeier >

1 0

Can't do basic time operations with System.Time
by John Goerzen 20 Jan '05

20 Jan '05

Hi, I have a simple desire. I have a string that I need to parse as a date/time string in the local timezone, then convert it to standard seconds-since-epoch format. This is trivial in C, Perl, Python, etc. but seems impossible to do reliably in Haskell. I'm hoping someone can tell me where I've gone wrong. My initial idea was to parse the string, generate a CalendarTime object, use toClockTime to convert it to seconds-since-epoch, and then grab the value out of that. There were some problems, though: what to put in ctTZ and ctIsDST? I initially loaded them with 0 and False, though that turned out to be clearly wrong. My next idea was to take the ctTZ result from toCalendarTime, then use that for all the CalendarTime objects I'd generate. That was wrong, too, during daylight savings time. I don't think I should have to re-implement the algorithms for determining whether a given date is under DST worldwide. What I really need is just a wrapper around mktime() that just calls mktime and doesn't do anything else. All the post-processing that System.Time is doing is what's causing me trouble. I'd just like it to ignore ctTZ, ctTZName, and ctIsDST. That would yield behavior identical to the C library. -- John

1 0

lex
by Daniel Fischer 20 Jan '05

20 Jan '05

Hi, does anybody know, why 'lex' isn't faithful to the Haskell-syntax? Since it isn't difficult to make it ignore comments, handle qualified names and recognize octal/hexadecimal literals (the system, be it hugs or ghc, does it, and I filled in the required code this evening, so for a good programmer it would be a matter of half an hour at most), I suppose there must be a reason, only I can't think of one. If you have any good ideas or even know the reason, please tell me. Thanks in advance, Daniel

1 0

RE: [Haskell-cafe]Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 20 January 2005 11:30, Keean Schupke wrote: > Simon Marlow wrote: > >> Yes, except that you forgot that not all foreign calls can run >> >> concurrently with Haskell code. Only the "safe" ones can. >> >> > Okay, now I understand what is going on. Why is there extra overhead > for a 'safe' call? A safe call must - save its state on the Haskell stack - save its thread state object on a queue, so GC can find it - tidy up the stack so GC can take place - release the RTS lock - possibly start a new OS thread if the pool is empty of these, releasing the RTS lock is probably the most expensive. Also, if another OS thread gets scheduled before the call returns, we have an expensive context switch on return. In contrast, an unsafe call is just an inline C call. Cheers, Simon

4 4

Problems with compiling wxFruit
by Dmitri Pissarenko 20 Jan '05

20 Jan '05

Hello! I'm trying to compile wxFruit sample program paddleball (http://zoo.cs.yale.edu/classes/cs490/03-04b/bartholomew.robinson/) When I try to compile file paddle.hs (see below where it is availeble) using the call <call> ghc -fglasgow-exts -farrows -package wx -iC:\dapWork\haskell-learning\afrp-0.4 \src:C:\dapWork\haskell-learning paddle.hs </call> I'm getting the error message <error-message> paddle.hs:10: Failed to load interface for `WXFruit': Could not find interface file for `WXFruit' (use -v to see a list of the files searched for) paddle.hs:11: Failed to load interface for `AFRP': Could not find interface file for `AFRP' (use -v to see a list of the files searched for) paddle.hs:12: Failed to load interface for `AFRPUtilities': Could not find interface file for `AFRPUtilities' (use -v to see a list of the files searched for) </error-message> The file WXFruit.hs is located in the same directory as paddle.hs. AFRP.hs and AFRPUtilities.hs are located in the directory C:\dapWork\haskell-learning\afrp- 0.4\src. Apparently, those packages are not installed properly. What should I do in order to compile paddle.hs? Thanks in advance PS: All files related to this example (paddle.hs and wxFruit.hs) are available at http://dapissarenko.com/resources/2005_01_20_haskell_learning/wxFruitSample… in a 7 MB zip archive. -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

3 3

RE: [Haskell-cafe] Re: Hugs vs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 11 January 2005 14:15, Gracjan Polak wrote: > Simon Marlow wrote: > > There's a big lock on File. If you want to do truly concurrent > reading, > you can make multiple FileInputStreams, each of which has > its own file > descriptor (the Unix implementation uses dup(2)). > > > > Original and descriptor returned by dup or dup2 share file pointer. *blink* You're right! Serves me right for assuming that POSIX would have sensible semantics. Perhaps this API isn't implementable, in its current state. Cheers, Simon

10 26

RE: [Haskell-cafe]Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 20 January 2005 10:01, Keean Schupke wrote: > Simon Marlow wrote: > >> We're getting a bit confused here. Keean: the original question was >> about whether a disk read will stop all other *Haskell* threads. >> Not OS threads. The two are quite different beasts in GHC. >> >> Cheers, >> Simon >> >> > But if GHC is running with the -threaded flag, then other > Haskell-threads can keep running using the second OS-thread, even > though one Haskell-thread (and its associated OS thread) is blocking > - right? If the call to read() was "safe" (i.e. the FFI "safe" attribute), then yes. But GHC currently does and "unsafe" call to read(), even with -threaded, which doesn't give other threads a chance to run. Perhaps it should be a safe call. That's going to hurt performance unless you really need to parallelise disk I/O, though. Maybe it wouldn't hurt too much, someone should measure it. > In other words even with disk IO (as I said the kernel would not > busy-wait - so there are > only two options, this OS-thread is put to sleep, or the data is > already in a buffer and is > returned immediately), all the other Haskell-threads should not block > (provided it is > running with -threaded) > > Have I got that right? Yes, except that you forgot that not all foreign calls can run concurrently with Haskell code. Only the "safe" ones can. Cheers, Simon

2 1

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 20 January 2005 09:56, Keean Schupke wrote: > Why is disk a special case? I have never heard that all processes > under linux wait for a disk read... You were talking about Haskell threads, not processes! These are quite different things. > The kernel most certainly does not busy wait for disks > to respond, so the only alternative is that the process that needs to > wait (and only that process) is put to sleep. In which case a second > thread would be unaffected. > > Linux does not busy wait in the Kernel! (don't forget the kernel does > read-ahead, > so it could be that read really does return 'immediately' and without > any delay > apart from at the end of file - In which case asynchronous IO just > slows you down with extra context switches). The question is whether Haskell threads block when one of them is reading from the disk, and this has nothing to do with what happens in the kernel. I never said that Linux busy waits in the kernel. The reason that disk I/O is different is because select() treats it differently, and select() is what GHC's runtime currently uses to multiplex I/O. Cheers, Simon

2 1

RE: [Haskell-cafe]Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 19 January 2005 20:31, Glynn Clements wrote: > Keean Schupke wrote: > >>>> Okay, my ignorance of Posix is showing again. Is it currently the >>>> case, then, that every GHC thread will stop running while a disk >>>> read is in progress in any thread? Is this true on all platforms? >>> >>> It's true on Unix-like systems, I believe. Even with -threaded. It >>> might not be true on Win32. >> >> I think this is not true on linux, where a thread is just a process >> created with special flags to keep the same fds and memory. >> >> As threads on linux are scheduled like processes, one thread >> blocking should not affect the others? > > That should be true of all POSIX-like thread implementations > (including Linux, whose threads aren't quite POSIX-compliant, e.g. in > regard to signal handling, but aren't that far off). > > Essentially, blocking system calls only block the calling kernel > thread. > > OTOH, if you are implementing multiple user-space threads within a > single kernel thread, if that kernel thread blocks, all of the > user-space threads within it will be blocked. We're getting a bit confused here. Keean: the original question was about whether a disk read will stop all other *Haskell* threads. Not OS threads. The two are quite different beasts in GHC. Cheers, Simon

2 1

RE: [Haskell-cafe]Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 20 Jan '05

20 Jan '05

On 19 January 2005 20:33, Glynn Clements wrote: > Simon Marlow wrote: > >> We do use a thread pool. But you still need as many OS threads as >> there are blocked read() calls, unless you have a single thread >> doing select() as I described. > > How does the select() help? AFAIK, select() on a regular file or block > device will always indicate that it is readable, even if a subsequent > read() would have to read the data from disk. Again we've lost track of the discussion a bit. Yes you're right, but I was answering a different question. Cheers, Simon

1 0

Re: Why is getArgs in the IO monad?
by Ashley Yakeley 20 Jan '05

20 Jan '05

In article <41ECD49F.9020601(a)imperial.ac.uk>, Keean Schupke <k.schupke(a)imperial.ac.uk> wrote: > Surely both requirements can be satisfied if the programs arguments are made > parameters of main: > > main :: [String] -> IO () > > Keean. Better yet, it should be an implicit parameter so as not to break existing programs. main :: (?args :: [String]) => IO () You could do the same with standard input and output. -- Ashley Yakeley, Seattle WA

6 13

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 19 Jan '05

19 Jan '05

We do use a thread pool. But you still need as many OS threads as there are blocked read() calls, unless you have a single thread doing select() as I described. BTW our Haskell Workshop paper from last year describes this stuff: http://www.haskell.org/~simonmar/papers/conc-ffi.ps.gz Cheers, Simon On 19 January 2005 15:07, Keean Schupke wrote: > Why not use a thread-pool, and a "safe" call to read, provided there > is an OS thread available, > defaulting to "unsafe" if no thread is available... You could make the > thread pool size an argument... > > Keean. > > Simon Marlow wrote: > >> On 19 January 2005 13:50, William Lee Irwin III wrote: >> >> >> >>> On 19 January 2005 09:45, Ben Rudiak-Gould wrote: >>> >>> >>>>> Okay, my ignorance of Posix is showing again. Is it currently the >>>>> case, then, that every GHC thread will stop running while a disk >>>>> read is in progress in any thread? Is this true on all platforms? >>>>> >>>>> >>> On Wed, Jan 19, 2005 at 01:39:05PM -0000, Simon Marlow wrote: >>> >>> >>>> It's true on Unix-like systems, I believe. Even with -threaded. >>>> It might not be true on Win32. >>>> >>>> >>> How does forkOS fit into this picture? It's described in the >>> documentation as allowing concurrent execution of system calls >>> and other activity by other threads. >>> >>> >> >> forkOS doesn't fix this. It forks another OS thread which can be >> used to make concurrent foreign calls, if they are not marked >> "unsafe". However, the standard I/O library, in -threaded mode, does >> read like this: >> >> - non-blocking, "unsafe", read() to see what's there >> - if read() would block, then hand off to another >> Haskell thread which does select() on all the outstanding >> IO requests. >> >> This scheme is just for efficiency. We could (and used to) just call >> "safe" read() for every read - that would give you the right >> concurrency with -threaded, but unfortunately you'd really notice >> the difference if you had 1000s of threads all doing IO, because >> each one would need its own OS thread. The current scheme is rather >> snappy (even snappier than non-threaded, as it happens). >> >> You can always do System.Posix.fileRead to get around it. >> >> Cheers, >> Simon >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe

3 2

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 19 Jan '05

19 Jan '05

On 19 January 2005 09:45, Ben Rudiak-Gould wrote: > Glynn Clements wrote: > > >Ben Rudiak-Gould wrote: > > > >>GHC really needs non-blocking > >>I/O to support its thread model, and memory-mapped I/O always > blocks. > > >If, by "blocks", you mean that execution will be suspended until the > >data has been read from the device into the buffer cache, then Unix > >non-blocking I/O (i.e. O_NONBLOCK) also blocks. > > Okay, my ignorance of Posix is showing again. Is it currently the > case, then, that every GHC thread will stop running while a disk read > is in progress in any thread? Is this true on all platforms? It's true on Unix-like systems, I believe. Even with -threaded. It might not be true on Win32. > (By the way, are the GHC folks aware that the description of Win32 I/O > at [2] is wrong? It seems to assume that ReadFile doesn't return until > the buffer is full.) I don't think that description corresponds with the implementation, but then I'm not terribly familiar with that part of the code. It doesn't get used when -threaded is on. Cheers, Simon

4 3

tree with labeled edges as a monad
by Andrew Pimlott 19 Jan '05

19 Jan '05

This is a "have you seen this monad?" post. I was trying to construct a search tree, and decided I wanted to do it in a monad (so I could apply StateT and keep state as I explored the space). I discovered that a tree with labeled leaves is a monad, but I wanted to label internal nodes, and such a tree (eg, Data.Tree.Tree) is not a monad (because it can only have one result type). Finally, I realized I could get a similar effect by labeling the edges and the leaves with different types: data Tree l a = Leaf a | Branch [(l, Tree l a)] instance Monad (Tree l) where return = Leaf Leaf a >>= f = f a Branch c >>= f = Branch [(l, t >>= f) | (l, t) <- c] You might use it as turn = do board <- getBoard move <- lift (Branch [(move, return move) | move <- findMoves board]) applyMove move turn I found this quite pleasing, though I hadn't run across trees as monads before. Has anyone else found this useful? Is it in a library somewhere? Andrew

3 2

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 19 Jan '05

19 Jan '05

On 19 January 2005 16:49, Keean Schupke wrote: > But what about the continuing computation... we do not want > the fastest IO system, but we want the program to comlete the > fastest... So ideally we want 2 threads! > > One runs the Haskell code that is not waiting for IO. (IE other > Haskell threads)... The other runs a select loop as you suggest! > > This way the number of threads is fixed (2) and execution never > 'blocks' for IO. (Simon, what about this scheme?) This is what GHC does, if I understand you correctly. The thread running select() does so in its own OS thread, while another OS thread runs the Haskell code. As long as you use -threaded, that is. Oh, and before GHC 6.4 it was done a different way - the scheduler used to do the select() between running Haskell threads. Cheers, Simon

2 1

RE: [Haskell-cafe] Re: Hugsvs GHC (again)was: Re: Somerandomnewbiequestions
by Simon Marlow 19 Jan '05

19 Jan '05

On 19 January 2005 13:50, William Lee Irwin III wrote: > On 19 January 2005 09:45, Ben Rudiak-Gould wrote: >>> Okay, my ignorance of Posix is showing again. Is it currently the >>> case, then, that every GHC thread will stop running while a disk >>> read is in progress in any thread? Is this true on all platforms? > > On Wed, Jan 19, 2005 at 01:39:05PM -0000, Simon Marlow wrote: >> It's true on Unix-like systems, I believe. Even with -threaded. It >> might not be true on Win32. > > How does forkOS fit into this picture? It's described in the > documentation as allowing concurrent execution of system calls > and other activity by other threads. forkOS doesn't fix this. It forks another OS thread which can be used to make concurrent foreign calls, if they are not marked "unsafe". However, the standard I/O library, in -threaded mode, does read like this: - non-blocking, "unsafe", read() to see what's there - if read() would block, then hand off to another Haskell thread which does select() on all the outstanding IO requests. This scheme is just for efficiency. We could (and used to) just call "safe" read() for every read - that would give you the right concurrency with -threaded, but unfortunately you'd really notice the difference if you had 1000s of threads all doing IO, because each one would need its own OS thread. The current scheme is rather snappy (even snappier than non-threaded, as it happens). You can always do System.Posix.fileRead to get around it. Cheers, Simon

3 3

RE: [Haskell-cafe] GHC for .NET?
by Simon Peyton-Jones 19 Jan '05

19 Jan '05

| "The GHC compiler for .NET is currently under development at | Microsoft Research, Cambridge". | | Hmm. That location sounds familiar :-) Does anyone know if this is | actually going to happen? Or if there's any code anywhere, however | experimental, to try? It'd make a lot of sense to give GHC a .NET back end, and it's a question that comes up regularly. The reason that we haven't done it here, at GHC HQ, is because it's a more substantial undertaking than might at first appear (see below). Furthermore, it'd permanently add a complete new back-end platform for us to maintain. Given our rather limited development effort (= Simon and me), we have so far not bitten the bullet, and we have no immediate plans to do so. It'd be a good, well-defined project for someone else to tackle, and there is some good groundwork already done: * Sigbjorn Finne did a simple interop implementation that allows a Haskell program to be compiled to native code (as now) but to call .NET programs via a variant of the FFI. I don't think this work is in active use, and I'd be surprised if it worked out of the box, but it could probably be revived with modest effort * Andre Santos and his colleagues at UFPE in Brazil are working on a .NET back end, that generates CLR IL, though I don't know where they are up to. * GHC.Net would be extra attractive if there was a Visual Studio integration for GHC. Substantial progress on this has been made in 2004 by Simon Marlow, Krasimir Angelov, and Andre Santos and colleagues. There may be others that I don't know of. If anyone wants to join in this effort, do contact the above folk. And please keep us informed! Simon Here's a summary of why it's a non-trivial thing to do: - The first thing is to generate native CLR Intermediate Language (IL). That's not really hard. Requires thinking about representations for thunks and functions, and it may not be particularly efficient, but it can surely be done. An open question is about whether to generate verifiable IL or not. The trouble here is that Haskell's type system is more expressive than the CLR's in some ways, notably the use of higher-kinded type variables. So, to generate verifiable IL one is bound to need some run-time casts, and it's not clear how to minimise these. At first blush this is *all* you need do. But it isn't! - Next, you need to think about how to inter-operate with .NET libraries. You don't really want to write "foreign import..." for each and every import. You'd like GHC to read the CLR meta-data directly. But there are lots of tricky issues here; see the paper that Mark Shields and I wrote about "Object-oriented style overloading for Haskell". - Now you need to figure out how to implement GHC's primitive operations: the I/O monad arbitrary precision arithmetic concurrency exceptions finalisers stable pointers software transactional memory Not all of these are necessary, of course, but many are used in the libraries. The CLR supports many of them (e.g. concurrency) but with a very different cost model. - Last, you have to figure out what to do for the libraries. GHC has a pretty large library, and you either have to implement the primops on which the library is based (see previous point), or re-implement it. For example, GHC's implementation of I/O uses mutable state, concurrency, and more besides. For each module, you need to decide either to re-implement it using .NET primitives, or to implement the stuff the module is based on. These challenges are mostly broad rather than deep. But to get a production quality implementation that runs a substantial majority of Haskell programs "out of the box" requires a decent stab at all of them.

2 1

RE: [Haskell-cafe] I/O interface
by Simon Marlow 19 Jan '05

19 Jan '05

On 18 January 2005 00:27, Ben Rudiak-Gould wrote: > Marcin 'Qrczak' Kowalczyk wrote: > > >Convenience. I'm worried that it uses separate types for various > >kinds of streams: files, pipes, arrays (private memory), and > sockets. >Haskell is statically typed and lacks subsumption. This > means that >even though streams are unified by using a class, code > which uses >a stream of an unknown kind must be either polymorphic > or use >existential quantification. > > Yes, this is a problem. In my original proposal InputStream and > OutputStream were types, but I enthusiastically embraced Simon M's > idea of turning them into classes. As you say, it's not without its > disadvantages. I recognised this problem, which is why TextInputStream and TextOutputStream are existential wrappers around streams. Most clients will be using the Text streams, so they won't suffer from the polymorphism problem. However, we could also provide a non-overloaded version using one of Ben's solutions: > I see several possibilities here. > > * We could adopt Avery Lee's suggestion (from the discussion in > 2003) to use field labels instead of methods. Advantages: InputStream > and OutputStream behave more like their OOP equivalents, with no loss > of extensibility. Disadvantages: potentially less efficient (no > specialization possible); loses some static type information. Unfortunately GHC isn't nearly as good at optimising records as it is at optimising type class overloading. Of course, type class overloading is just a special case of polymorphic records, but there you go. > * We could use a single type for all input and output streams in > the standard library, but retain the type classes also. > > * We could provide existential wrappers: > > data IStream = (InputStream a) => MkIStream !a > instance InputStream IStream where ... This one gets my vote. BTW, Marcin: the library in the prototype implementation differs somewhat from the version of the interface in the Haddock docs. The docs were written before I started hacking on the prototype. Cheers, Simon

1 0

Re: [Haskell] Re: Why is getArgs in the IO monad?
by Marcin 'Qrczak' Kowalczyk 19 Jan '05

19 Jan '05

Keean Schupke <k.schupke(a)imperial.ac.uk> writes: > Surely both requirements can be satisfied if the programs arguments are made > parameters of main: > > main :: [String] -> IO () >From info '(libc)Error Messages', about program_invocation_name and program_invocation_short_name: *Portability Note:* These two variables are GNU extensions. If you want your program to work with non-GNU libraries, you must save the value of `argv[0]' in `main', and then strip off the directory names yourself. We added these extensions to make it possible to write self-contained error-reporting subroutines that require no explicit cooperation from `main'. This suggests that making global parameters available only as arguments of main would be a bad idea. But they should be settable, to account for the rare case of wanting to substitute something else to a library which reads them itself. -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

2 1

Re: performance question (John Meacham)
by Stijn De Saeger 19 Jan '05

19 Jan '05

thanks Ben and John, your ideas looked like they may speed up things indeed, so i went along with them and reimplemented the whole thing.... to my surprise, the program got considerably slower even ! here is the new code. > data ILtype = II | IE | EI | EE | NII | NIE | NEI | NEE deriving (Eq, Ord) (... I found no increase in performance by using the UNPACK pragma as you suggested, so I just ommitted it in this version...) > data Interval = Range ILtype !Double !Double deriving (Eq, Ord) > instance Show Interval where > show (Range iltype x y) = case iltype of > II -> if x == y then (show x) > else "[" ++ (show x) ++ ".." ++ (show y) ++ "]" > IE -> "[" ++ (show x) ++ ".." ++ (show y) ++ ")" > EI -> "(" ++ (show x) ++ ".." ++ (show y) ++ "]" > EE -> "(" ++ (show x) ++ ".." ++ (show y) ++ ")" > NII -> "Not " ++ show (Range II x y) > NIE -> "Not " ++ show (Range IE x y) > NEI -> "Not " ++ show (Range EI x y) > NEE -> "Not " ++ show (Range EE x y) the flip of interval types: > ilFlip :: ILtype -> ILtype > ilFlip ilt = case ilt of > II -> NII > IE -> NIE > EI -> NEI > EE -> NEE > NII -> II > NIE -> IE > NEI -> EI > NEE -> EE The complement of Intervals : > intComplement :: Interval -> Interval > intComplement (Range iltype x y) = (Range (ilFlip iltype) x y) membership function for Intervals: > isIn :: Double -> Interval -> Bool > isIn r (Range iltype x y) = case iltype of > II -> r >= x && r <= y > IE -> r >= x && r < y > EI -> r > x && r <= y > EE -> r > x && r < y > NII -> r > y || r < x > NIE -> r > y || r <= x > NEI -> r >= y || r < x > NEE -> r >= y || r <= x As always, any further comments or insights greatly appreciated. stijn.

1 0

styles
by Matthew Roberts 19 Jan '05

19 Jan '05

Haskell seems to be a language that allows for lots of different programming styles. The most obvious being pointed v.s. point free. As a programmer born and raised on OO - I have found the pointed style to suit me better. However, there are other distinctions. I heavily use "let in" and "where" to break up each function into smaller parts while I see other programmers putting everything in one line. I have seen the evolution of a Haskell programmer joke and most of it goes over my head. My question is "Is there standard terminology for the different programming styles in Haskell (besides pointed and point-free)?" Matt

2 1

Re: Books on Haskell
by David Owen 19 Jan '05

19 Jan '05

Hi, I have 3 Haskell books, The Craft of Functional Programming (Thompson), Introduction to Functional Programming Using Haskell (Bird) and The Haskell School of Expression (Hudak). I recommend Thompson's book because it contains good explanations and lots of exercises, although the book is quite big and takes some time to work through. Bird's book is a bit shorter and is good for explanations too but it isn't quite so hands on as it contains fewer exercises. Hudak's I feel is a bit too advanced for a first read, it focusses on using the Hugs graphics library and I think that the graphics examples can sometimes cloud the simple ideas that are trying to be explained. I'll probably try reading it again in the future. All the best Dave O

3 2

About instance
by Ulises Juarez Martinez 18 Jan '05

18 Jan '05

Hi. I have the next definitions: type Ocurrence = (String, Int) type Inside = [Ocurrence] data Pattern = Return Inside | Abort | Filter (Ocurrence -> Bool) Pattern beyond :: Pattern -> Pattern beyond (Filter pred Abort) = Abort -- more definitions of beyond optimous :: Pattern -> Pattern optimous p = fixPoint beyond p where fixPoint f x = if(f x == x) then x else fixPoint f (f x) When I load the program an error is produced: ERROR - An instance of Eq (Event -> Bool) is required to derive Eq Pattern I put: data Pattern = Return Inside | Abort | Filter (Ocurrence -> Bool) Pattern deriving (Eq) and a new error was produced: ERROR - An instance of Eq (Ocurrence -> Bool) is required to derive Eq Pattern Who can I do an instance of Eq (Ocurrence -> Bool)? Is there another option to avoid the error? Regards Ulises _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

2 1

Re: [Haskell-cafe] Unit testing in Haskell
by Graham Klyne 18 Jan '05

18 Jan '05

I use hunit, and find it works very well. #g -- At 20:05 11/01/05 +0100, Dmitri Pissarenko wrote: >Hello! > >When programming in an imperative language like Java, unit tests are a very >important development tool IMHO. > >I want to try out unit testing in Haskell and wonder what experienced >Haskellers >think about unit testing in Haskell in general and the hUnit testing framework >(see URL below) in particular? > >http://hunit.sourceforge.net/ > >What other unit testing frameworks for Haskell do you use? > >TIA > >dap >-- >Dmitri Pissarenko >Software Engineer >http://dapissarenko.com >_______________________________________________ >Haskell-Cafe mailing list >Haskell-Cafe(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell-cafe ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

performance question
by Stijn De Saeger 18 Jan '05

18 Jan '05

Hello all, A question on that most elusive of subjects.... performance in haskell (GHC 6.2) Using the GHC profiler, I obtained the following analysis results (i hope the code doesn't come out too ugly by mail): total time = 0.92 secs (46 ticks @ 20 ms) total alloc = 83,373,032 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc isIn Main 50.0 22.8 getCon Main 13.0 16.7 o' Main 8.7 6.6 satisfies Main 6.5 0.0 powerList Main 6.5 46.9 CAF Main 6.5 0.1 showCon Main 4.3 0.3 MAIN MAIN 4.3 0.0 a' Main 0.0 6.7 The problem child, that isIn function, has got about 78000 entries in the profile log. I should probably mention that this is an incredibly dumbed down version of the program, the dimensions of the data it is supposed to handle are such that, on a trial run I killed the process after about 15 minutes, when I found out it hadn't even completed 3% of its task. sad stuff, really. Anyways, 'isIn' is a predicate that checks whether a given Double lies within an interval, where intervals are defined as ... define an interval bound, either inclusive (I) or exclusive (E) > data Bound = I Double | E Double deriving (Eq, Show, Ord) > data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord) where Nil acts as the complement of an interval, this is reflected in the isIn function. .... > isIn :: Double -> Interval -> Bool > isIn r (Nil x y) = not (isIn r (Il x y)) > isIn r (Il (I x) (I y)) = r >= x && r <= y > isIn r (Il (I x) (E y)) = r >= x && r < y > isIn r (Il (E x) (I y)) = r > x && r <= y > isIn r (Il (E x) (E y)) = r > x && r < y I tried rewriting it to something that intuitively 'feels' like it should be faster, but i have no real idea about the cost of the respective haskell expressions: ... version 2 > isIn :: Double -> Interval -> Bool > isIn r (Nil x y) = not (isIn r (Il x y)) > isIn r (Il x y) = case x of > (I x') -> if r >= x' then case y of > (I y') -> r <= y' > (E y') -> r < y' > else False > (E x') -> if r > x' then case y of > (I y') -> r <= y' > (E y') -> r < y' > else False ... which indeed turns out to be a tad bit faster, according to the new profile log. total time = 0.80 secs (40 ticks @ 20 ms) total alloc = 64,404,104 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc isIn Main 30.0 0.0 getCon Main 25.0 21.6 powerList Main 15.0 60.7 showCon Main 7.5 0.3 o' Main 7.5 8.6 CAF Main 7.5 0.1 MAIN MAIN 5.0 0.0 a' Main 2.5 8.6 But it can hardly be called impressive. Can anyone see another obvious optimization, or have I just hit the ceiling because of the sheer number of function calls to isIn? I am still pretty new to haskell, and I find it hard to wrap my head around the way the compiler deals with my code. If someone has a few leads on general performance heuristics in haskell/GHC, I would be happy to read them too... thanks for your time. stijn

3 2

Books on Haskell
by Dmitri Pissarenko 18 Jan '05

18 Jan '05

Hello! I've completed reading of "Yet another Haskell tutorial" and now want to learn Haskell more thoroughly. I'm searching for a book, in which the features of Haskell are explained in the form of examples and exercises (like in the book "Clause and Effect" on PROLOG). My purpose in exploring Haskell is to determine whether I can program much more productively by using Haskell instead of Java/C#. In order to do that, I have to learn Haskell quite thoroughly. What book can you recommend? TIA Dmitri Pissarenko -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

3 3

Re: [Haskell-cafe] Matroids in Haskell
by Michael Matsko 17 Jan '05

17 Jan '05

Dimitri Matriods are generalization of vector spaces. Basically, they are defined by a set of linear dependence axioms and basis exchange properties. Oxley's "Matriod Theory" is the standard reference. There are a multitude of equivalent formulations. Mike Matsko ----- Original Message ----- From: Dmitri Pissarenko <mailing-lists(a)dapissarenko.com> Date: Friday, January 14, 2005 2:00 pm Subject: Re: [Haskell-cafe] Matroids in Haskell > Hello! > > Gerhard Navratil wrote: > > Recently I had a course on matroids and would like to investigate > the> topic a little further. Did anybody write (or start writing) a > > Haskell-implementation for matroids? > > What is a matroid? > > Thanks > > Dmitri Pissarenko > -- > Dmitri Pissarenko > Software Engineer > http://dapissarenko.com > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

3 2

FFI and C99 "complex"
by Aaron Denney 17 Jan '05

17 Jan '05

Basically, what's the best way to deal with C99's complex types? Pragmatically, how do I deal with them in function definitions now? Is there any chance they'll get added to a later version of the FFI addendum? -- Aaron Denney -><-

2 2

Is it possible to print out types of instances in scope
by Jeremy Shaw 16 Jan '05

16 Jan '05

Hello, Is it possible to write a function that would display all the instances of a class currently in scope[1]? For example, for 'Show a' it should output something like: The instances of 'Show a' currently in scope are: Show Int Show Float Show Char Show ... Depending on what modules are imported at compile time, the list would grow or shrink. I am willing to accept all sorts of restrictions at this point in time such as: ~ Yes, but only if the classes are declared in this way (but not for ones declared in the standard library) ~ Yes, but it requires template haskell It is currently my belief that the compiler "knows" the answer, but there is no way to get the list from the compiler... I would be interested in any information, links, examples, papers, etc, that you can provide that would tell me: ~ Yes it can be done ~ It could be done with a compiler extension ~ It could never be done ~ It could be done, but it would be a really horrible idea, and here's why So don't hold back :) Thanks! Jeremy Shaw. [1] I suppose by 'currently in scope' I mean all the instances that type checker is considering when it type checks the function at compile time. But I am really not picky about what I mean right now as I can't get anything remotely ressembling this to happen.

3 4

Efficiency Question
by Daniel Fischer 15 Jan '05

15 Jan '05

Hi folks, toying a bit with splitAt and take, I have met yet another thing, I don't understand. In the Hugs Prelude, splitAt is defined splitAt n xs | n <= 0 = ( [],xs) splitAt _ [] = ([],[]) splitAt n (x:xs) = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs whereas in the report it is described as (take n xs,drop n xs) -- I have no problem with that, since the report explicitely states that the functions need not be implemented as given there --, let's call that function bSplit (b was chosen for 'bad'). Now, as expected, splitAt takes fewer reductions than bSplit, splitAt (n+1) takes 18 reductions more than splitAt n, bSplit (n+1) takes 32 more than bSplit n (24 for take, 8 for drop). So far so good, now changing to ghci and testing that on a long list ([1 .. 1000000], [1 .. 500000]), splitting at half, then printing the two middle numbers. The first surprise was that there bSplit was faster than splitAt (roughly twice as fast). Does anybody know how that can be?? The second surprise was the variation of time needed. For the longer list, splitAt usually took 0.45 - 0.48 secs, occasionally about 0.9 secs (I think that will be due to gc), bSplit usually took 0.22 - 0.25 secs, occasionally about 0.7 secs (gc, probably). For the shorter list, splitAt took 0.22 - 0.28 secs (0.7 with gc), bSplit took 0.10 - 0.20 secs (0.6 with gc). Now, what's the explanation for that? Differences of, say, 0.03 secs or so I happily attribute to an occasional interrupt or something, but the difference between 0.10 and 0.20 I would like an explanation for. Another thing, while toying, I found out that a comparison (n <= 0) takes three reductions more than (n < 1) according to my hugs, so changing the definition of splitAt thus, we require (3*n) reductions less. But the number of reductions and speed are different things, as witnessed by the above, so would it be an improvement to replace "n <= Integerliteral"-queries by "n < Integerliteral"-queries or doesn't that make any difference at all in execution time? Finally, in several contexts I needed to cons an element to one of a pair of lists, so I defined infixr 5 &,§ (&) :: a -> ([a],[b]) -> ([a],[b]) x & (xs,ys) = (x:xs,ys) (§) :: b -> ([a],[b]) -> ([a],[b]) y § (xs,ys) = (xs,y:ys). I find them useful (though I don't like the symbols, if you have any better ideas, thx) and for splitAt, (&) saves another reduction per step. Now, I would like to have such operators supplied by the language, so is there space for them in the Prelude or in List, or does hardly anyone besides me ever need them? Have a wonderful weekend ye all, Daniel

4 7

Linear shuffle
by Gracjan Polak 15 Jan '05

15 Jan '05

Hi, I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: shuffle :: [a] -> IO [a] shuffle [] = return [] shuffle x = do r <- randomRIO (0::Int,length x - 1) s <- shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s) This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? -- Gracjan

10 18

Efficiency Question
by Derek Elkins 15 Jan '05

15 Jan '05

> Another thing, while toying, I found out that a comparison (n <= 0) > takes three reductions more than (n < 1) according to my hugs, so > changing the definition of splitAt thus, we require (3*n) reductions > less. But the number of reductions and speed are different things, as > witnessed by the above, so would it be an improvement to replace "n <= > Integerliteral"-queries by "n < Integerliteral"-queries or doesn't > that make any difference at all in execution time? I don't know about in Hugs, but in (compiled, optimized) GHC it should make no difference. Presumably, if you are running something in an interpreter micro-optimizing isn't worthwhile. > Finally, in several contexts I needed to cons an element to one of a > pair of lists, so I defined > > infixr 5 &,§ > > (&) :: a -> ([a],[b]) -> ([a],[b]) > x & (xs,ys) = (x:xs,ys) > > (§) :: b -> ([a],[b]) -> ([a],[b]) > y § (xs,ys) = (xs,y:ys). Well, to start, the type signatures are unnecessarily restrictive. Then, the function that also is not in the Report, but does come up quite a bit by people who get into a point-free or categorical style is the bifunctor, (***) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d) f *** g = \(a,b) -> (f a,g b) this is an instance of (***) in Control.Arrow, hence the name. So, your first function is, (&) x = (x:) *** id or using another function from Control.Arrow, (&) x = first (x:) I can say that I have wanted (***), I can't say that I've ever wanted your two functions. Also, first (x:) seems to be more self-documenting.

2 1

Re: [Haskell-cafe] Efficiency Question
by Tom Pledger 15 Jan '05

15 Jan '05

Daniel Fischer wrote: [snip] >Another thing, while toying, I found out that a comparison (n <= 0) takes >three reductions more than (n < 1) according to my hugs, so changing the >definition of splitAt thus, we require (3*n) reductions less. > That difference looks like it comes from the default definitions of (<) and (<=) in Ord, and the default definition of (/=) in Eq. There's potential for Hugs to scrounge a little extra performance by going straight to case expressions in its Prelude: Prelude> 1 >= 0 True (28 reductions, 42 cells) Prelude> 1 > 0 True (25 reductions, 39 cells) Prelude> let x `gt` y = case x `compare` y of GT -> True; _ -> False in 1 `gt` 0 True (23 reductions, 37 cells) Prelude> let x `ge` y = case x `compare` y of LT -> False; _ -> True in 1 `ge` 0 True (23 reductions, 37 cells) Regards, Tom

1 0

Re: [Haskell-cafe] Problem with wxHaskell
by Atwood, John Wesley 14 Jan '05

14 Jan '05

> Jinwoo Lee <jinwoo68(a)gmail.com> > You can remove that error message by including following in > package.conf file. > > Package > {name = "readline", > auto = True, > import_dirs = ["$libdir/imports"], > source_dirs = [], > library_dirs = ["$libdir"], > hs_libraries = ["HSreadline"], > extra_libraries = ["readline", "advapi32"], > include_dirs = [], > c_includes = ["HsReadline.h"], > package_deps = ["base"], > extra_ghc_opts = [], > extra_cc_opts = [], > extra_ld_opts = [], > framework_dirs = [], > extra_frameworks = []}, > > Jinwoo Lee > > Always remember that you are unique. Just like everyone else. > jinwoo68(a)gmail.com You'll still run into the problem: Failed to load interface for `Graphics.UI.WXCore.Dialogs': Bad interface file: C:\Program Files\wxhaskell-0.8\lib/imports/Graphics/ UI/WXCore/Dialogs.hi mismatched interface file versions: expected 6022, found 6021 The right fix would be to recompile wxHaskell from source, but since I don't have cygwin installed on a handy machine, I tried editing the .hi files, jamming in the 6022 version number. That worked, at least for the examples I tried. I used the old DOS command, debug (I thought TextPad would respect binary files, but it didn't). the 1 byte change is at offset 1b (or 11b in debug). John

1 0

Re: [Haskell-cafe] Linear shuffle
by Atwood, John Wesley 14 Jan '05

14 Jan '05

> Gracjan Polak <gracjan(a)acchsh.com> wrote: > John Meacham wrote: > > Oleg wrote a great article on implementing the perfect > shuffle. with > > some sample code. > > > > http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle > > > > Thats the kind of answer I was hoping to get :) Thanks. > > > shuffle could be useful in standard library. At least Python > has it. I > was translating some small Python program, the hardest part was the > missing shuffle function. What do you think? Also, note that, in a lazy language, the algorithm's complexity will be dependent on the number of cards drawn from the deck, are possibly sub-linear in the number of cards in the deck. John

1 0

Matroids in Haskell
by Gerhard Navratil 14 Jan '05

14 Jan '05

Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? It would save me some time figuring out if this part of mathematics is useful for my work ... Thanks in advance, Gerhard ======================================== Gerhard Navratil Teaching- And Research-Assistant Technical University Vienna, Austria Institute of Geoinformation and Cartography Gusshausstr. 27-29, 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12712 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at

3 2

Linear Shuffle
by Okasaki, C. DR EECS 14 Jan '05

14 Jan '05

Clearly, you can do a perfect shuffle in O(N) time using mutable arrays, using the standard imperative algorithm. You can also do it in O(N) expected time using *immutable* arrays, using Haskell's bulk array operations. 1. Start with a list of length N. If N < 2, stop. 2. Pair each element with a random index in the range [1,2N] (or [0,2N-1]). 3. Use "accum" to create an array of size 2N, where slot I contains a list of all the elements paired with I. 4. Map the shuffle function recursively across the array to re-shuffle any slots that got more than one element. 5. Append all the slots together into the result list. If you leave out step 4, you get an algorithm that runs in O(N) worst-case time, rather than expected time, but you no longer have a perfect shuffle (although it might be good enough). Upping the size of the array from 2N to 3N or 4N will help reduce collisions, but will not entirely eliminate them. With step 4, you can imagine pathological cases where everything gets put in the same slot, but with a reasonable random number generator, it is vanishingly unlikely that you will have enough collisions to drive the cost higher than linear. Again, upping the size of the array from 2N to 3N or 4N makes this even more unlikely. -- Chris

1 0