[Haskell-cafe] replacement
Write a function with three parameters, two atoms and a list, (say p1, p2 and L) that returns the list, L, with all occurrences of the first given atom, p1, replaced by the second one, p2. If P2 be nil, the given atom should be deleted and the returned list cannot contain anything in place of it, no matter how deep it occurred in the list. Note: Remember it says that no matter how deep it occurred in the list..It means thatwe may have nested list example: replace 1 2 [1 2 3 4] = [2 2 3 4] replace 1 2 [[1 2 3][3 4 5 1]] = [[2 2 3][3 4 5 1]] - Ahhh...imagining that irresistible new car smell? Check outnew cars at Yahoo! Autos.___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Export Haskell Libraries
On Thu, 2007-04-12 at 23:38 -0700, SevenThunders wrote: I saw a lot of options for places to put sources and targets, but I couldn't quite figure out how to configure it to place the object file output. No doubt it's there, I just couldn't find it in the 45 min.s or so that I looked for it. runghc Setup.hs configure --help give the full list. The one you want is --scratchdir (or just -b). It seems that ghc itself is doing some kind of dependency analysis to determine the final call to gcc. Yes, ghc knows which packages are required and the description for each package lists the packages it depends on and any C libs and other linker flags and search paths it needs. Duncan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: k-minima in Haskell
[EMAIL PROTECTED] wrote: You have n elements, and you need to locate a specific k-element permutation. There are n! / (n-k)! such permutations. You therefore need log(n! / (n-k)!) bits of information. A binary comparison provides one bit of information. So the number of comparisons that you need to get that much information is: O(log(n! / (n-k)!)) = O(n log n - (n-k) log (n-k)) = O(n log (n/(n-k)) + k log (n-k)) That looks right to me. If k n, then this simplifies to O(n + k log n), and if k is close to n, it simplifies to O(n log n + k). Ian Lynagh wrote: Hmm, is something wrong with the following?: [...] Total: O(n + k log k) Mh, I'm not sure. At least, we have log (n! / (n-k)!) = log n! - log (n-k)! = log 1 + log 2 + log 3 + ... + log (n-k) + ... + log n - log 1 - log 2 - log 3 - ... - log (n-k) = log (n-k +1) + ... + log (n-k +k) which is greater than (k log (n-k)) and smaller than (k log n). For k=1, this estimate yields a minimum time of (log n) to find the minimum of a list. While not wrong, this clearly underestimates the necessary O(n). I think that estimating (n log (n/(n-k)) to n for k n is not correct because the logarithm of 1 = n/n is 0 and not 1 :) Ian Lynagh wrote: [1] http://en.wikipedia.org/wiki/Selection_algorithm Thanks for the link, Ian. It clearly shows that a lazy take k . qsort takes only O(n + k log k) time. I posted an analysis as follow up to the old thread on haskell-general http://article.gmane.org/gmane.comp.lang.haskell.general/15110 Regards, apfelmus ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
On 4/14/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? I have never felt I was writing a lot of boilerplate. There are a lot of abstraction mechanisms in Haskell to avoid boilerplate. Second, if Haskell should be more successful in the real world there has to be a way of demonstrating basic ideas of a big program to customers. How would you do this? Everybody knows UML class diagrams, for example. In contrast, nobody knows about termgraphs or lambda *g*. I've never had to show a UML or ER diagram to any business people--usually they want a slideshow that is far simpler and a little prettier. The fact that nobody knows about termgraphs or lambda in your group means that you probably shouldn't be considering Haskell (for the same reason my bosses always asked me to document everything--in case you get hit by a bus). Thank you very much for contributing to the discussion. Please assume, that you have to generate the code from a model. Further assume, that you have no choice and are not allowed to discuss the sense of this approach :-) How should the code look like? I am not sure if you are trying to solve a real problem or not. If you are solving a real problem, where you already happen to have an EMF model which you are required to generate code from, then I recommend to just do everything in Java using the existing tools built for EMF. If you decide to still keep working in Haskell, and it works out well, please share your solution because I think many people here will be very interested. wxHaskell, OOHaskell, and O'Haskell are all starting points for this type of project. - Brian ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multithreading speedup
Thanks again to the answers Stefan, Il giorno Apr 14, 2007, alle ore 1:41 AM, Stefan O'Rear ha scritto: On Sat, Apr 14, 2007 at 01:31:58AM +0200, Fawzi Mohamed wrote: Il giorno Apr 14, 2007, alle ore 12:33 AM, Stefan O'Rear ha scritto: On Sat, Apr 14, 2007 at 12:27:10AM +0200, Fawzi Mohamed wrote: I was trying to speed up a program that I wrote and so I thought about using multiple threads. I have a quite easy parallel program and I did the following do subRes - MVar.newMVar [] putStrLn starting threads subV - flip mapM [0 .. (nThreads - 1)] $ ( \i - do subR - MVar.newEmptyMVar let writeRes r = do { MVar.putMVar subR r } forkOS (do Getting rid of that forkOS will help a LOT - forkOS is very expensive and gives no benefit. It exists only for the benefit of FFI libs like OpenGL that use thread local state. Plain forkIO uses a thread pool in the runtime; it is even more parallel than forkOS, and extremely cheap. Yes indeed using forkIO (that I had removed only trying to find a way to make my program faster) one gets basically the same results as with forkOS. thread(IO) 3.10user 0.02system 0:01.68elapsed 184%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1037minor)pagefaults 0swaps The fact that you are using forkOS is a dead giveaway of a documentation bug somewhere. Please report it, so nobody else makes this mistake! No actually I had used forkIO before, but seeing no speedup I tried also forkOS hoping that using it would speed things up... let r=eval (startData !! i) writeRes $! r putStr $ writtenRes) return subR ) putStrLn started threads toFold - mapM MVar.takeMVar subV putStrLn about to fold return $ foldl1 mergeRes toFold [...]Actually my code should be equivalent to parMap rwhnf, but I get the following results: parMap 3.63user 0.02system 0:01.97elapsed 185%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1039minor)pagefaults 0swaps threads(OS) 3.14user 0.02system 0:01.68elapsed 187%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1041minor)pagefaults 0swaps Those look equally parallel to me :) exactly the same code, and parmap is 17% slower with respect to creating threads manually for each element in the list and waiting for them all to finish... I can understand that maybe this way one is guaranteed that if the original program ends than the par version will end too (one can spark bottom), but it is just less efficient if it is known that one needs the data of the threads to partially calculate it together with them. actually a parMap that executes the last element of the list before going on to evaluate it, should be very close to the example with explicit threads (if the workload is more or less balanced). Sure enough using mParMap :: (a-b) - [a] - [b] mParMap f (l0:l1:lr) = let n0 = f l0 nr = mParMap f (l1:lr) in n0 `par` (nr `seq` (n0:nr)) mParMap f (l0:[]) = let n0 = f l0 in n0 `seq` n0:[] mParMap f [] = [] I get timings similar to the thread example. mParMap 3.15user 0.02system 0:01.72elapsed 184%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1040minor)pagefaults 0swaps Actually I think that 99% of the time when one wants a parallel map he wants something like this, not like the parallel map in strategies, maybe there should be a parList' defined this way and a corresponding parMap' I suppose that it is because I have a thread for each element in the list plus a main thread vs just one thread per element in the list, but I am not sure, if someone has some ideas... With threads (now the I managed to have some speedup) I can use a workers/queue approach and have a better load balancing. Threads are supposed to be cheap. If implementing a thread pool by hand ever gives a speedup, it's a bug. but making my worker threads if I know the number of worker will be more efficient, my program is extremely parallel, but putting a par everywhere would be very memory costly and would probably break the program in the wrong places, I know where I should spark threads so that I have few high-level tasks and coarse grain parallelism, and if I know the number of workers I can do much more efficiently by hand. Furthermore I can put the tasks in a queue in order of decreasing cost and get a rather good load balancing without having to think too much about a static distribution. So having a thread pool by hand does make sense, doing it with OS threads and trying to beat the GHC runtime does not. by the way is there a way to know how many processors are available to the program (to make the strategy or thread control depend on it)? anyone can answer to this? thanks Fawzi
Re: [Haskell-cafe] replacement
Hi Write a function with three parameters, two atoms and a list, (say p1, p2 and L) that returns the list, L, with all occurrences of the first given atom, p1, replaced by the second one, p2. If P2 be nil, the given atom should be deleted and the returned list cannot contain anything in place of it, no matter how deep it occurred in the list. Is this homework? http://www.haskell.org/haskellwiki/Homework_help example: replace 1 2 [1 2 3 4] = [2 2 3 4] replace 1 2 [[1 2 3][3 4 5 1]] = [[2 2 3][3 4 5 1]] If it is, use Lisp. Try assigning a type to this in Haskell, its not particularly easy, and would require clever type class stuff. Thanks Neil ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Translating perl - haskell, string fill ins with an error on invalid inputseems awfullycomplex. Is there a way to simplify?
by utilizing Text.Printf.printf, extracting some more common functionality for the lookups, and changing the error handling (check for errors before giving results, but use throwError instead of error, letting the caller decide whether errors are fatal or not), we arrive at something like: financial_output :: (Functor m, MonadError String m) = String - String - String - String - m String financial_output company displaymode startDate endDate = fmap financial_script $ mapM lookupWith lookups where financial_script [companyFile,modeString,titleEnd] = gnuplot_timeseries_settings ++ \n ++ printf plot [\%s\:\%s\] '%s'%s title \%s %s\ startDate endDate companyFile modeString company titleEnd lookups = [ (no company file for , company, company_to_companyfile) , (no mode string for , displaymode, displaymode_to_modestring) , (no title end for , displaymode, displaymode_to_titleend) ] lookupWith (msg,key,assocs) = maybe (throwError $ msg ++ key) return $ lookup key assocs which perhaps isn't all that bad? the main thing i miss in Haskell for this kind of code generators are here-documents. there are workarounds (Hugs has a form of here docs, string interpolation isn't difficult to hack up, unlines gets rid of ++ and \n), and for more complex code generators, use of Text.PrettyPrint may be more appropriate, but for everyday scripting with code generation, nothing is as simple, readable, or portable as good old here-documents. hth, claus ps. calling the modified function: Main either error putStrLn $ financial_output ibm point start end Program error: no mode string for point Main either error putStrLn $ financial_output ibm points start end set terminal png transparent nocrop enhanced size 600,400 set pm3d implicit at s set xdata time # The x axis data is time set timefmt %d-%b-%y # The dates in the file look like 10-Jun-04 set format x %b %d #On the x-axis, we want tics like Jun 10 plot [start:end] 'data/ibm.dat'using 1:2 with linespoints title ibm daily prices ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multithreading speedup
On 4/14/07, Fawzi Mohamed [EMAIL PROTECTED] wrote: but making my worker threads if I know the number of worker will be more efficient, my program is extremely parallel, but putting a par everywhere would be very memory costly and would probably break the program in the wrong places, I know where I should spark threads so that I have few high-level tasks and coarse grain parallelism, and if I know the number of workers I can do much more efficiently by hand. Furthermore I can put the tasks in a queue in order of decreasing cost and get a rather good load balancing without having to think too much about a static distribution. So having a thread pool by hand does make sense, doing it with OS threads and trying to beat the GHC runtime does not. I think you should probably consider the extremely lightweight forkIO threads as your work items and the GHC runtime as your thread pool system (it will find out how many threads you want using the RTS options and distribute it for you). If you're worried about memory efficiency you can tweak the initial stack sizes for threads etc. using runtime options. It's still true that you don't want to fork off trivial computations in a separate thread, BUT that's true for manual work item queues as well (you'd want each work item to be a substantial amount of computation because there is overhead per item). E.g. if you have a list you might not want one thread per element (and you wouldn't want one work item per element either) if the per element tasks are fairly trivial, so you'd first group the list into chunks, and then let each chunk be a work item (i.e. spawn a forkIO thread to process it). I'd be interested in seeing benchmarks on this, but I do think that you'll be better off just spawning a lightweight thread per task, rather than first wrapping it in some data structure as a work item, then putting it in a queue, then popping items of the queue into threads. Seems that doing it that way would just be duplicating work. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Left-factoring with Parsec
x = x a + b Now use high school algebra x = x*a + b x - x*a = b x*(1-a) = b x = b / (1-a) x = b * 1/(1-a) Now you have to remember that the Taylor series expansion of 1/(1-a) is 1/(1-a) = 1 + a + a^2 + a^3 + a^4 + ... OK, now put your grammar hat back on. What's 1 | a | aa | aaa | | ... it's just an arbitrary number of a:s, i.e., a* (or 'many a' in parsec). So finally expr = b a* nice!-) different viewpoints yield new perspectives. this made me wonder what those missing algebra operations would mean in terms of parsing/language generation; it hurts a bit to think about your algebraic manipulations in that way, but if i got the interpretations right, they might be quite useful additions: l1 - l2: things in l1 that are not in l2; generalising elimination of keywords from valid ids l1 / l2: things that can be completed to be in l1, via suffixes in l2; standard tool in ides thanks for the interesting detour, claus ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multithreading speedup
Il giorno Apr 14, 2007, alle ore 2:45 PM, Sebastian Sylvan ha scritto: I think you should probably consider the extremely lightweight forkIO threads as your work items and the GHC runtime as your thread pool system (it will find out how many threads you want using the RTS options and distribute it for you). If you're worried about memory efficiency you can tweak the initial stack sizes for threads etc. using runtime options. It's still true that you don't want to fork off trivial computations in a separate thread, BUT that's true for manual work item queues as well (you'd want each work item to be a substantial amount of computation because there is overhead per item). E.g. if you have a list you might not want one thread per element (and you wouldn't want one work item per element either) if the per element tasks are fairly trivial, so you'd first group the list into chunks, and then let each chunk be a work item ( i.e. spawn a forkIO thread to process it). yes, but to build the optimal chunk size one would like to know the number of working threads. So again, any way to know it at runtime? or it is a bad practice to ask? I'd be interested in seeing benchmarks on this, but I do think that you'll be better off just spawning a lightweight thread per task, rather than first wrapping it in some data structure as a work item, then putting it in a queue, then popping items of the queue into threads. Seems that doing it that way would just be duplicating work. good idea, thanks, I will try.. Fawzi ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Do monads imply laziness?
This is probably an off-topic question, but I can't think of a better forum to ask it: does the existance of monads imply laziness in a language, at least at the monadic level? Consider the following: a purely functional, eagerly evaluated programming language, that uses monads to encapsulate the awkward squad. In this programming language, a program generates an IO monad whose encapsulating computation performs side effecting affections- it writes to stdout, say. But this generated monad never has it's value evaluated- the monad is tossed away uninspected. Does the side effect happen? If the answer is at least potientially no, then monads are lazily evaluated, and thus monads imply laziness (at least at the monadic level). On the other hand, if the answer is yes, then monads do not imply laziness. Thanks, Brian ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do monads imply laziness?
On Sat, Apr 14, 2007 at 10:56:44AM -0400, Brian Hurt wrote: This is probably an off-topic question, but I can't think of a better forum to ask it: does the existance of monads imply laziness in a language, at least at the monadic level? Consider the following: a purely functional, eagerly evaluated programming language, that uses monads to encapsulate the awkward squad. In this programming language, a program generates an IO monad whose encapsulating computation performs side effecting affections- it writes to stdout, say. But this generated monad never has it's value evaluated- the monad is tossed away uninspected. Does the side effect happen? If the answer is at least potientially no, then monads are lazily evaluated, and thus monads imply laziness (at least at the monadic level). On the other hand, if the answer is yes, then monads do not imply laziness. First off, having monadic IO does not mean that there are side effects at ANY level, consider: data IOTree = PutChar Char IOTree | GetChar (Char - IOTree) type IO = Cont IOTree putChar ch = Cont $ \x - PutChar ch (x ()) getChar = Cont $ \x - GetChar x No effects, monadic IO! Secondly, all real languages delay evaluation on a function, so that IOTree will not be constructed all at once, but incrementally as input arrives. If you want it more incremental in a strict language, it would be simple: data IOTree = PutChar Char (() - IOTree) | GetChar (Char - IOTree) --- Just for fun, here is code for monadic IO in the pure subset of O'Caml (a strict functional language). All side effects are in 'interp'. type iotree = Stop | Put of char * (unit - iotree) | Get of (char - iotree);; type 'a io = ('a - iotree) - iotree;; let putChar ch cont = Put (ch, cont) ;; let getChar cont = Get cont ;; let exit cont = Stop ;; let (=) act aft cont = act (fun v - aft v cont) ;; let return vl cont = cont vl ;; let rec interp0 tree = match tree with Stop - () | Put (ch, ct) - print_char ch ; interp0 (ct ()) | Get ct - interp0 (ct (input_char stdin)) ;; let interp act = interp0 (act (fun x - Stop)) ;; -- Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Efficient use of ByteString and type classes in template system
Hi Haskell Café! I'm writing a perl/python like string templating system which I plan to release soon: darcs get http://darcs.johantibell.com/template The goal is to provide simple string templating; no inline code, etc.. An alternative to printf and ++. Example usage: import qualified Data.ByteString as B import Text.Template helloTemplate = Hello, $name! Would you like some ${fruit}s? helloContext = [(name, Johan), (fruit, banana)] test1 = B.putStrLn $ substitute (B.pack helloTemplate) helloContext I want to make it perform well, especially when creating a template once and then rendering it multiple times. Compiling the template is a separate step from rendering in this use case: compiledTemplate = template $ B.pack helloTemplate test2 = B.putStrLn $ render compiledTemplate helloContext A template is represented by a list of template fragments, each fragment is either a ByteString literal or a variable which is looked up in the context when rendered. data Frag = Lit ByteString | Var ByteString newtype Template = Template [Frag] This leads me to my first question. Would a lazy ByteString be better or worse here? The templates are of limited length. I would say the length is usually between one paragraph and a whole HTML page. The Template data type already acts a bit like a lazy ByteString since it consists of several chunks (although the chunck size is not adjusted to the CPU cache size like with the lazy ByteString). Currently the context in which a template is rendered is represented by a type class. class Context c where lookup :: ByteString - c - Maybe ByteString instance Context (Map String String) where lookup k c = liftM B.pack (Map.lookup (B.unpack k) c) instance Context (Map ByteString ByteString) where lookup = Map.lookup -- More instance, for [(String, String)], etc. I added this as a convenience for the user, mainly to work around the problem of not having ByteString literals. A typical usage would have the keys in the context being literals and the values some variables: someContext = Map.fromList [(name, name), (fruit, fruit)] I'm not sure if this was a good decision, With this I'm halfway to the (in)famous Stringable class and it seems like many smarter people than me have avoided introducing such a class. How will this affect performace? Take for example the rendering function: render :: Context c = Template - c - ByteString render (Template frags) ctx = B.concat $ map (renderFrag ctx) frags renderFrag :: Context c = c - Frag - ByteString renderFrag ctx (Lit s) = s renderFrag ctx (Var x) = case Text.Template.lookup x ctx of Just v - v Nothing - error $ Key not found: ++ (B.unpack x) How will the type dictionary 'c' hurt performance here? Would specializing the function directly in render help? render (Template frags) ctx = B.concat $ map (renderFrag f) frags where f = flip Text.Template.lookup ctx renderFrag f (Var x) = case f x of I can see the implementation taking one of the following routes: - Go full Stringable, including for the Template - Revert to Context = Map ByteString ByteString which was the original implementation. - Some middle road, without MPTC, for example: class Context c where lookup :: ByteString - c ByteString ByteString - Maybe ByteString This would allow the user to supply some more efficient data type for lookup but not change the string type. Having a type class would allow me to provide things like the possibility to create a Context from a record where each record accessor function would server as key. Something like: data Person { personName :: String, personAge :: Int } would get converted (using Data?) to: personContext = [(personName, show $ personName aPerson), (personAge, show $ personAge aPerson)] but not actually using a Map but the record itself. I guess my more general question is: how do I reason about the performance of my code or any code like this? Are there any other performance improvements that could be made? Also, I would be grateful if someone could provide some feedback on the implementation, anything goes! I still have some known TODOs: - Import error messages for invalid uses of $. - Improve the regex usage overall. - Add some more functions; the plan is to add those function which could be expressed in efficiently with the current interface. An example is things like renderAndWrite, when writing doing a B.concat first is unnecessary. Cheers, Johan Tibell ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Calling C function in Mac OS X
I wish to optimize Haskell code using ByteString, direct reading Doubles form it, direct writing Doubles to it. I've tried Don Stewart's code http://hpaste.org/26 that uses calling to C functions to implement necessary readDouble showDouble. readDouble works ok. showDouble always return nan in Mac OS X (but works well in Windows). I'm using GHC 6.6 in Mac (http://www.haskell.org/ghc/download_ghc_66.html#macosxppc) and in Windows (http://www.haskell.org/ghc/download_ghc_66.html#windows). I've made showInt based on showDouble: http://hpaste.org/1390 It works well in Mac OS X. It seems that problem happens only when I send CDouble (or CLDouble) to C function. My conf: PowerBook G4, Mac OS X 10.4.9, powerpc-apple-darwin8-gcc-4.0.1 What may cause this? How to fix it? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Calling C function in Mac OS X
On Sat, Apr 14, 2007 at 07:58:25PM +0400, Sergey Perminov wrote: I wish to optimize Haskell code using ByteString, direct reading Doubles form it, direct writing Doubles to it. I've tried Don Stewart's code http://hpaste.org/26 that uses calling to C functions to implement necessary readDouble showDouble. readDouble works ok. showDouble always return nan in Mac OS X (but works well in Windows). I'm using GHC 6.6 in Mac (http://www.haskell.org/ghc/download_ghc_66.html#macosxppc) and in Windows (http://www.haskell.org/ghc/download_ghc_66.html#windows). I've made showInt based on showDouble: http://hpaste.org/1390 It works well in Mac OS X. It seems that problem happens only when I send CDouble (or CLDouble) to C function. My conf: PowerBook G4, Mac OS X 10.4.9, powerpc-apple-darwin8-gcc-4.0.1 foreign import ccall unsafe static stdio.h snprintf c_printf_double :: Ptr CChar - CSize - Ptr CChar - CInt - IO CInt is illegal (and slow). snprintf is a varargs function, and varargs functions are allowed to use a completely different calling convention from non-varargs functions. I'm pretty sure the FFI allows nasal demons for what you just did, using a non-varargs call for a varargs function... In any case the fundamental issue is i386 vs. ppc. i386 has so few registers that everything is passed on the stack, and the ordinary convention supports varargs too. ppc normally puts things in registers, but does different stuff for varargs. There is no way to use varargs functions from the FFI. Also, snprintf is an INTERPRETER - you won't gain much if every time you need to print a double you do a dynamic dispatch on the format string! If you care about performance enough to be using the FFI at all, you probably ought to hand-code the printer, not call snprintf. Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Do monads imply laziness?
Brian Hurt wrote: This is probably an off-topic question, but I can't think of a better forum to ask it: does the existance of monads imply laziness in a language, at least at the monadic level? Consider the following: a purely functional, eagerly evaluated programming language, that uses monads to encapsulate the awkward squad. In this programming language, a program generates an IO monad whose encapsulating computation performs side effecting affections- it writes to stdout, say. But this generated monad never has it's value evaluated- the monad is tossed away uninspected. Does the side effect happen? If the answer is at least potientially no, then monads are lazily evaluated, and thus monads imply laziness (at least at the monadic level). On the other hand, if the answer is yes, then monads do not imply laziness. Thanks, Brian Firstly, this question is not off-topic. Next, strictness and purity have nothing to do with monads. Finally, monadic values -represent- actions, they aren't the actions themselves. If you throw away a string representing some action that you were going to pass to an interpreter, the action it represents never happens, but this has nothing to do with laziness. Monadic IO in Haskell can be understood very much like that. The value of main gets passed to an IO interpreter, and all the work on the Haskell side is just building expressions for that interpreter (and thus it is now easy to see why this preserves purity). Laziness is not involved at all (except, as one person found out on c.l.f a long time ago, () is less useful in a strict language than in a pure one, e.g. repeatM_ m = m repeatM_ m doesn't do anything in a strict language). ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] LL(1) parsing of declarators
I'm writing a code generator for C, and I'm trying to parse a C-like input language using LL(1) (parsec specifically). The syntax of declarators is giving me trouble: (simplified) declaration = qualifiers (declarator `sepBy1` char ',') qualifiers = many1 name declarator = name now if we have name name, they are both parsed by the greedy many1 in qualifiers! I can make this work with some ugly rearranging: declaration = fdeclarator many (char ',' declarator) fdeclarator = name many1 name declarator = name is there a more elegant way? Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
G'day all. I wrote: O(log(n! / (n-k)!)) = O(n log n - (n-k) log (n-k)) = O(n log (n/(n-k)) + k log (n-k)) That looks right to me. If k n, then this simplifies to O(n + k log n), and if k is close to n, it simplifies to O(n log n + k). Quoting Ian Lynagh [EMAIL PROTECTED]: Hmm, is something wrong with the following?: [...] Total: O(n + k log k) The problem with with my simplifications. :-) But as an exercise, prove: O(n log (n/(n-k)) + k log (n-k)) = O(n + k log k) Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe