[Haskell-cafe] fgl Data.Graph examples
Can someone post some simple examples of using the Data.Graph library? So I can define a simple graph let g = buildG (1,2) [(1,2), (2,1)] but how do i label my edges and nodes? i want to be able to name my nodes, and add weights to the edges and be able to update those weights as well. Thanks, Anatoly ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to use arrays efficiently?
Hi, I have a list of index-value pairs and I want to get a list which is sorted by the index and which contains index-wise sums of all the values. Here is a function that does this (and a bit more). --- pixelHistogram samples = let index s t = let x = round $ (fromIntegral imageWidth) * (1-s) y = round $ (fromIntegral imageHeight) * (1-t) in y*imageWidth + x indexedSamples = [(index s t, color) | (s, t, color) - samples] pixelArray :: Array Int Color pixelArray = accumArray (\+) black (0, imageWidth*imageHeight) indexedSamples in elems pixelArray --- The problem is that this function is very inefficient. It seems that the whole indexedSamples list is stored in memory when creating pixelArray. When I do some profiling I see that the heap consumption of this function grows linearly. If I just write the samples list to a file instead of first summing them, I get a nice and flat heap profile. So how to do this efficiently? Thanks, Lauri ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
Hello Lauri, Friday, May 16, 2008, 12:19:29 PM, you wrote: pixelArray :: Array Int Color it's boxed array which means that its elements are stored as thunks computed only when you actually use them. try UArray instead: http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] runInteractiveCommand: program ends before writing or reading all the output
On Thu, 2008-05-15 at 21:04 -0400, Olivier Boudry wrote: I tried to place a length text `seq` before the mapM_ writeExport to force the process output to be read but the result was even worst (only one line printed). Apparently withtout the `evaluate` function it causes more troubles than it solves. Yes, you should prefer evaluate over seq (or return $!) in the IO monad because you sometimes have to distinguish between the evaluation that happens when you construct your IO actions, and the evaluation that happens when you run your IO actions. The evaluate action does the latter and its ordered with respect to the other IO actions. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Std lib equivalent for liftM concat . sequence
A couple of days ago I had need for: concatM :: Monad m = [m [a]] - m [a] concatM = liftM concat . sequence but found no such thing in the std libs, except perhaps for msum (I don't want to add instances for MonadPlus. Should I have to?). Have I missed something trivial? Alistair ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Std lib equivalent for liftM concat . sequence
Hello Alistair, Friday, May 16, 2008, 2:12:45 PM, you wrote: concatM = liftM concat . sequence but found no such thing in the std libs, except perhaps for msum (I don't want to add instances for MonadPlus. Should I have to?). Have I missed something trivial? 1. it's easy to define yourself 2. it's not widely used. at least, i have in my program for, foreach, concatMapM, filterM and lot of other monadic operations, but no one concatM -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] elem of infinite set of tuple
I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a - [0..], b - [0..] ] If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled. From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite. -- View this message in context: http://www.nabble.com/elem-of-infinite-set-of-tuple-tp17272802p17272802.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? UArray source code is far too cryptic for me. Regards, Lauri On Fri, May 16, 2008 at 11:37 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Lauri, Friday, May 16, 2008, 12:19:29 PM, you wrote: pixelArray :: Array Int Color it's boxed array which means that its elements are stored as thunks computed only when you actually use them. try UArray instead: http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] elem of infinite set of tuple
On Fri, May 16, 2008 at 04:42:31AM -0700, leledumbo wrote: I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a - [0..], b - [0..] ] If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled. From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite. Didn't you just answer your own question? -- David Roundy Department of Physics Oregon State University ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] elem of infinite set of tuple
It's not exactly a question of Haskell's behaviour. The list [ (a,b) | a - [0..], b - [0..] ] is such that apart from pairs starting with zero, no other pair is associated with a finite index. In other words, [ (a,b) | a - [0..], b - [0..] ] is not a correct 'enumeration' of all pairs of nonnegative integers. You need to reorder them if you need a finite index associated with every pair. On Fri, May 16, 2008 at 5:12 PM, leledumbo [EMAIL PROTECTED] wrote: I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a - [0..], b - [0..] ] If I try to query elemOf (1,1), the program keeps searching and searching but it never makes it. But if I query elemOf (0,1) (or anything as long as the first element is 0), it can find it easily. I wonder how it's handled. From my point of view, instead of starting from (1,0), the program starts from (0,0), which will never finish since the limit of the second element is infinite. -- View this message in context: http://www.nabble.com/elem-of-infinite-set-of-tuple-tp17272802p17272802.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] How to use arrays efficiently?
Hello Lauri, Friday, May 16, 2008, 3:44:19 PM, you wrote: impossible. you can try parallel arrays Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? UArray source code is far too cryptic for me. Regards, Lauri On Fri, May 16, 2008 at 11:37 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Lauri, Friday, May 16, 2008, 12:19:29 PM, you wrote: pixelArray :: Array Int Color it's boxed array which means that its elements are stored as thunks computed only when you actually use them. try UArray instead: http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulat mailto:[EMAIL PROTECTED] -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fgl Data.Graph examples
Hi, I'm new to this, but I'll give it a shot. import Data.Graph.Inductive There are several ways to build a graph. Let's say, node labels are 'String's and edge labels are 'Double's. Edge labels would be the weights. grs :: [Gr String Double] The below four lines generate the same graph. From labeled nodes and edges: grs = [mkGraph [(2, start), (1, end)] [(2, 1, 1.0)], insEdge (2, 1, 1.0) $ insNodes [(2, start), (1, end)] empty, From contexts: ([], 2, start, [(1.0, 1)]) (([], 1, end, []) empty), buildGr [([], 2, start, [(1.0, 1)]), ([], 1, end, [])]] Test graph equality: gr = head grs same = all (equal gr) (tail grs) You can populate the graph using () and ins... functions while using 'newNodes' to get a bunch of unused node indexes ('Node's) to avoid collisions. Deleting nodes also delete all connected edges, but trying to insert an edge to a non-existent node will create an exception. So nodes get in first. grd = delNode 1 gr -- no problem grd' = insEdge (2, 1, 1.0) grd -- exception There are some functions to work on edges. For instance, this divides all weights on your graph by 2: gr2 = emap (/ 2) gr This makes the graph undirected: gr2u = undir gr2 There are other map and fold functions. 'gfold' is very powerful. It all depends on your motive though. I don't think there is a straightforward way to tweak individual nodes and edges other than using graph construction tools. Maybe someone could shed a light on this. Thanks, -- Gokhan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
Thanks again. Here is my solution in case that somebody else runs into similar problem. This isn't very elegant and I would be interested to know if somebody has a better solution. Surely many people have encountered this kind of problem where you want to force evaluation of some expression at given point of program flow. Here evaluation of sum must be forced for every update of array element or otherwise memory consumption is proportional to the number of samples (100 000) instead of being proportional to the size of the array (10). --- import Data.Array.IO import Test.QuickCheck import System.Random uniformSampler :: Gen Double uniformSampler = choose (0,1) withSeed sampler seed = generate 1 (mkStdGen seed) sampler ac = 10 sc = 10 triplet = do i - uniformSampler s - uniformSampler t - uniformSampler return (round $ i * fromIntegral ac, (s,t)) sampling = sequence $ repeat triplet samples = take sc $ withSeed sampling 1 showElems xs = foldr1 (++) [show x ++ \n | x - xs] main = do a1 - newArray (0,ac) 0 :: IO (IOUArray Int Double) a2 - newArray (0,ac) 0 :: IO (IOUArray Int Double) let addtoElem i s t = do s' - readArray a1 i writeArray a1 i (s'+s) t' - readArray a2 i writeArray a2 i (t'+t) writes = [addtoElem i s t | (i,(s,t)) - samples] sequence writes ss - getElems a1 ts - getElems a2 putStrLn $ showElems (zip ss ts) --- Regards, Lauri On Fri, May 16, 2008 at 2:52 PM, Abhay Parvate [EMAIL PROTECTED] wrote: As far as I know, you can't. It needs machine representable types, such as Int, Double, Char, etc. But making a tuple of three UArray Int Double may help. 2008/5/16 Lauri Oksanen [EMAIL PROTECTED]: Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? UArray source code is far too cryptic for me. Regards, Lauri On Fri, May 16, 2008 at 11:37 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Lauri, Friday, May 16, 2008, 12:19:29 PM, you wrote: pixelArray :: Array Int Color it's boxed array which means that its elements are stored as thunks computed only when you actually use them. try UArray instead: http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] elem of infinite set of tuple
On Fri, May 16, 2008 at 07:58:40AM -0400, Dan Doel wrote: On Friday 16 May 2008, leledumbo wrote: I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a - [0..], b - [0..] ] FYI: The control-monad-omega package on hackage.haskell.org can handle this sort of thing (liberties taken with ghci formatting): Prelude :m + Control.Monad.Omega Prelude Control.Monad.Omega (1,1) `elem` runOmega (do x - each [0..] ; y - each [0..] ; return (x,y)) True Prelude Control.Monad.Omega It does breadth-first instead of depth-first search. Note however that it's not a true monad, as it doesn't satisfy the associativity law, unless you ignore the order of the elements. The point is discussed by Spivey and Seres in their chapter in The Fun of Programming. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] elem of infinite set of tuple
On Fri, 16 May 2008, David Roundy wrote: On Fri, May 16, 2008 at 07:58:40AM -0400, Dan Doel wrote: On Friday 16 May 2008, leledumbo wrote: I don't know how Haskell should behave on this. Consider this function: elemOf (x,y) = (x,y) `elem` [ (a,b) | a - [0..], b - [0..] ] FYI: The control-monad-omega package on hackage.haskell.org can handle this sort of thing (liberties taken with ghci formatting): Prelude :m + Control.Monad.Omega Prelude Control.Monad.Omega (1,1) `elem` runOmega (do x - each [0..] ; y - each [0..] ; return (x,y)) True Prelude Control.Monad.Omega It does breadth-first instead of depth-first search. You could also just use [ (b,a-b) | a - [0..], b - [0..a]] I wonder whether Georg Cantor could imagine that his diagonalization method would be practically applied some day. http://de.wikipedia.org/wiki/Cantor-Diagonalisierung ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
On Fri, 16 May 2008, Lauri Oksanen wrote: Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? Maybe an (UArray (Int,Int) Double) could help, where the second index range is fixed to (0,2). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
Lauri Oksanen [EMAIL PROTECTED] writes: Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? As (UArray Int Double, UArray Int Double, UArray Int Double). Or as UArray Int Double, but with a specialized lookup function: mylookup array index = (array!3*index, array!3*index+1, array!3*index+2) I guess it would be possible to have UArray Int (# Double, Double, Double #) - packing all three Doubles unboxed into the array, but I've no clue how to go about automating that. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
Yes, of course. How blind of me. Here is one more question. If you change IOUArray to IOArray and add $! in front of the two summations in the previous code, it still works correctly. But can you do similar trick with Array and accumArray? I have tried to put $! in different places in the first code that I posted but nothing seems to work. On Fri, May 16, 2008 at 4:26 PM, Henning Thielemann [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Lauri Oksanen wrote: Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? Maybe an (UArray (Int,Int) Double) could help, where the second index range is fixed to (0,2). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] How to use arrays efficiently?
Hello Ketil, Friday, May 16, 2008, 5:27:29 PM, you wrote: I guess it would be possible to have UArray Int (# Double, Double, Double #) - packing all three Doubles unboxed into the array, but I've no clue how to go about automating that. unoxed tuple doesn't have a box so it cannot be instance of typeclass. actually, ordinary tuple will solve this problem unless one problem in GHC - it's UArray indexing primitives use *element* indexes inatead of *byte* indexes. although at least we can implement UArray ix (a,a), UArray ix (a,a,a) and so on -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] How to use arrays efficiently?
Hello Lauri, Friday, May 16, 2008, 5:45:50 PM, you wrote: Yes, of course. How blind of me. Here is one more question. If you change IOUArray to IOArray and add $! in front of the two summations in the previous code, it still works correctly. But can you do similar trick with Array and accumArray? I have tried to put $! in different places in the first code that I posted but nothing seems to work. accumArray internally uses more or less the same code with imperative array as you wrote. so if you replace accumArray with your implementation with all those $! - it will work. otherwise you just don't get any chance :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ChessLibrary project
All, I've made my first code drop for a new project I'm working on (though it's really an extension of work I've been doing for about 5 years). Information and code can be found at http://code.haskell.org/ChessLibrary/ . Comments and suggestions warmly welcomed. Also, I'm looking for an experienced haskeller to serve as a mentor for this project - just to provide regular code reviews and architectural advice, mainly. Thanks for looking! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Starting Haskell with a web application
Where can I find the sources of the latest WASH? I couldn't find them in HackageDB (and neither with Google). -- Immanuel Normann 2008/3/6 Lars Viklund [EMAIL PROTECTED]: On Wed, Mar 05, 2008 at 10:52:07AM -0800, Bryan O'Sullivan wrote: Jonathan Gardner wrote: There's also WASH, but that has an even lower profile. I couldn't tell you if it sees much use, or even builds with recent compilers. The HTML component of WASH builds rather cleanly with GHC 6.8.2 after enabling the following extensions: MultiParamTypeClasses FlexibleContexts FlexibleInstances TypeSynonymInstances I use it for my statically generated blog, together with sqlite3. I've modified WASH/HTML to spit out reasonably correct XHTML as well. As for the rest of WASH, I have no idea since I had no need for it. -- Lars Viklund | [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Std lib equivalent for liftM concat . sequence
Seems to be close to sequence :: [ListT m a] - ListT m a Hmm? On 16 May 2008, at 14:12, Alistair Bayley wrote: A couple of days ago I had need for: concatM :: Monad m = [m [a]] - m [a] concatM = liftM concat . sequence but found no such thing in the std libs, except perhaps for msum (I don't want to add instances for MonadPlus. Should I have to?). Have I missed something trivial? Alistair ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] NW Functional Programming Interest Group
All, Apologies for multiple listings. It's that time again. Our growing cadre of functionally-minded north westerners is meeting at the The Seattle Public Library *University Branch* 5009 Roosevelt Way N.E. *Seattle*, WA 98105 206-684-4063 from 18:30 - 20:00 on May 28th. Note the change in venue Agenda - JP has graciously offered to give a talk on darcs - we also need to continue to fill the talk pipeline Hope to see you there. Monadically yours, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proving my point
test.l (line 7, column 1): unexpected end of input expecting (, Lambda abstraction, Let binding, Atom, end of input or Function application I obviously don't know anything about Parsec's inner workings. I'm going to investigate as soon as I stopped despairing. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Std lib equivalent for liftM concat . sequence
Oops, I was very wrong. Sorry. On 16 May 2008, at 20:13, Miguel Mitrofanov wrote: Seems to be close to sequence :: [ListT m a] - ListT m a Hmm? On 16 May 2008, at 14:12, Alistair Bayley wrote: A couple of days ago I had need for: concatM :: Monad m = [m [a]] - m [a] concatM = liftM concat . sequence but found no such thing in the std libs, except perhaps for msum (I don't want to add instances for MonadPlus. Should I have to?). Have I missed something trivial? Alistair ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] fgl Data.Graph examples
Thank you, that's exactly what i was looking for. I don't think there is a straightforward way to tweak individual nodes and edges other than using graph construction tools. Maybe someone could shed a light on this. I think i can define updateEdge in terms of insEdge and delEdge ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to use arrays efficiently?
You'd have to write a wrapper that implements an array of triples as a triple of arrays. This isn't too hard. There's a new library in the works that should make this a lot easier -- Don abhay.parvate: As far as I know, you can't. It needs machine representable types, such as Int, Double, Char, etc. But making a tuple of three UArray Int Double may help. 2008/5/16 Lauri Oksanen [EMAIL PROTECTED]: Thanks for help. I did some tests with UArray and it does the trick. The problem remaining is, how to implement UArray Int (Double, Double, Double)? UArray source code is far too cryptic for me. Regards, Lauri On Fri, May 16, 2008 at 11:37 AM, Bulat Ziganshin [EMAIL PROTECTED] wrote: Hello Lauri, Friday, May 16, 2008, 12:19:29 PM, you wrote: pixelArray :: Array Int Color it's boxed array which means that its elements are stored as thunks computed only when you actually use them. try UArray instead: [3]http://haskell.org/haskellwiki/Modern_array_libraries -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] [6]http://www.haskell.org/mailman/listinfo/haskell-cafe References Visible links 1. mailto:[EMAIL PROTECTED] 2. mailto:[EMAIL PROTECTED] 3. http://haskell.org/haskellwiki/Modern_array_libraries 4. mailto:[EMAIL PROTECTED] 5. mailto:Haskell-Cafe@haskell.org 6. http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fun with Darcs
Duncan Coutts wrote: On Thu, 2008-05-15 at 01:01 +0400, Bulat Ziganshin wrote: Hello Andrew, Thursday, May 15, 2008, 12:49:32 AM, you wrote: touch. Now, let's see what this IDE actually looks li-- oh you have GOT to be KIDDING me! It can't find the right GTK DLL?!? gtk2hs includes *developer* gtk2 environment. Which includes all the runtime dlls. while it should work fine (as far as it's in your path), you may try to install *runtime* gtk2 environment from http://sourceforge.net/project/showfiles.php?group_id=71914package_id=255391 I would not recommend that. I'd use the dlls that come with gtk2hs. Well, gmane shows that Duncan sent a second message about this - but since I didn't receive it in my mailbox, I can't reply quoting that. [Most irritating...] Anyway, running Leksah today, it doesn't complaing about missing GTK DLLs at all, so you must be right about the search path thing. [Now instead it crashes with a completely different error.] I built a copy of Leksah at work, and noticed that I didn't get the issue with a missing icon, so apparently the Darcs repo must have changed in the last few hours. (Indeed, I guess I could ask Darcs and find out!) The copy I built at work [with GHC 6.8.1] worked just fine - not that I could figure out how to use it. ;-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proving my point
Achim Schneider wrote: test.l (line 7, column 1): unexpected end of input expecting (, Lambda abstraction, Let binding, Atom, end of input or Function application I obviously don't know anything about Parsec's inner workings. I'm going to investigate as soon as I stopped despairing. Wait... unexpected end of input; expecting [...] end of input [...] That's just *wrong*...! ;-) But don't despaire - show us your parser and what it's supposed to parse, and I'm sure somebody [maybe even me] will be able to tell you what's up. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Don Stewart wrote: I've written an extended post on how to understand and reliably optimise code like this, looking at it all the way down to the assembly. The result are some simple rules to follow for generated code as good as gcc -O2. Enjoy, http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast A well-written piece, as always. My feelings are ambivilent. On the one hand, it's reassuring that such good performance can be obtained without resorting to calling C, explicit unboxed types, GHC-specific hacks, strictness annotations, manual seq calls, strange case expressions, or really anything remotely odd. It's fairly plain Haskell '98 that most beginners would be able to read through and eventually understand. And yet it's fast. On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Obviously most people would prefer to write declarative code and feel secure that the compiler is going to produce something efficient. If the muse takes me, maybe I'll see if I can't find a less ugly way to do this... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
Andrew Coppin wrote: Janis Voigtlaender wrote: http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf It is well-known that trees with substitution form a monad. ...OK, I just learned something new. Hanging around Haskell Cafe can be so illuminating! :-) Now, if only I could actually comprehend the rest of the paper... o_O I'll probably regret this for the rest of my life, but... As best as I can tell, a monad is essentially a container of some kind, together with a function that puts stuff into a container, and another function that maps over the container and combines the results in some way. That would rather suggest that *any* container type is potentially a monad of some kind. [Although possibly not a *useful* one...] Since a tree is a kind of container, yes, it should be a monad. [I'm still not really sure whether it's useful.] Presumably a set monad would work something like the list monad. One could imagine an array monad [although counting the size of the result set before allocating the array would seem rather expensive]. Perhaps a dictionary could be a monad? I'm not precisely sure how that would work. Hmm, what other kinds of random containers could you make a monad out of? [And would you bother?] On the other hand, Maybe is a rather odd kind of container, but a very useful monad... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
andrewcoppin: Don Stewart wrote: I've written an extended post on how to understand and reliably optimise code like this, looking at it all the way down to the assembly. The result are some simple rules to follow for generated code as good as gcc -O2. Enjoy, http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast A well-written piece, as always. My feelings are ambivilent. On the one hand, it's reassuring that such good performance can be obtained without resorting to calling C, explicit unboxed types, GHC-specific hacks, strictness annotations, manual seq calls, strange case expressions, or really anything remotely odd. It's fairly plain Haskell '98 that most beginners would be able to read through and eventually understand. And yet it's fast. On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Obviously most people would prefer to write declarative code and feel secure that the compiler is going to produce something efficient. If the muse takes me, maybe I'll see if I can't find a less ugly way to do this... I don't understand what's ugly about: go s l x | x m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1) And the point is that it is *reliable*. If you make your money day in, day out writing Haskell, and you don't want to rely on radical transformations for correctness, this is a sensible idiom to follow. Nothing beats understanding what you're writing at all levels of abstraction. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Hello Andrew, Friday, May 16, 2008, 10:56:36 PM, you wrote: On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Obviously most people would prefer to write declarative code and feel secure that the compiler is going to produce something efficient. if i understood correctly, fusion system about which Don plan to told next time, is just about translating high-level code into lower-level one behind the scenes. but it works only on limited subset of programs. it's what we have now - haskell is very inefficient language -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Andrew Coppin wrote: On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Buh? This is hard to read? mean n m = go 0 0 n where go s l x | x m = (s::Double) / fromIntegral (l::Int) | otherwise = go (s+x) (l+1) (x+1) One can in fact imagine a world in which the compiler does this transformation for you, though it takes a bit of squinting. http://reddit.com/r/programming/info/6jjhg/comments/c040ybt b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Bryan O'Sullivan wrote: Andrew Coppin wrote: On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Buh? This is hard to read? Look closer: it's hardER to read. mean xs = sum xs / fromIntegral (length xs) mean = go 0 0 n where go s l x | x m = s / fromIntegra l | otherwise = go (s+x) (l+1) (x+1 One version makes it instantly clear, at a glance, what is happening. The other requires you to mentally walk round a look, imperative style, to figure out what's happening. It's not a *big* deal, but it's unfortunate. I'm more worried about what happens in less trivial examples. [Let's face it, who wants to compute the sum of the numbers from 1 to N?] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Andrew Coppin [EMAIL PROTECTED] wrote: Wait... unexpected end of input; expecting [...] end of input [...] That's just *wrong*...! ;-) But don't despaire - show us your parser and what it's supposed to parse, and I'm sure somebody [maybe even me] will be able to tell you what's up. This is what I came up with while simplifying the parser: import Text.Parsec identifier = do whiteSpace s - many1 letter whiteSpace return s whiteSpace = do eof | ((many $ choice [ char ' ', newline ]) return ()) main = do let syn = runParser (do char '\\' many1 identifier char ':' whiteSpace identifier whiteSpace ) () \\a b print syn Admittedly, this is a quite degenerate case crouching in at least 10 corners simultaneously. Anyway, I get % ./test Left (line 1, column 5): unexpected end of input expecting end of input, letter or : and if I change it to whiteSpace = do (many eof return ()) | ((many $ choice [ char ' ', newline ]) return ()) Left (line 1, column 3): unexpected expecting letter, end of input or : Please, please don't ask me for the rationale of using eof like this, you would get the same answer as if you'd ask me why I cast a stone into the sea. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Andrew Coppin wrote: Bryan O'Sullivan wrote: Andrew Coppin wrote: On the other hand, this is the anti-theisis of Haskell. We start with a high-level, declarative program, which performs horribly, and end up with a manually hand-optimised blob that's much harder to read but goes way faster. Buh? This is hard to read? Look closer: it's hardER to read. mean xs = sum xs / fromIntegral (length xs) mean = go 0 0 n where go s l x | x m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1 One version makes it instantly clear, at a glance, what is happening. The other requires you to mentally walk round a look, imperative style, to figure out what's happening. It's not a *big* deal, but it's unfortunate. I'm more worried about what happens in less trivial examples. [Let's face it, who wants to compute the sum of the numbers from 1 to N?] Hm, it seems like you're expecting magic, aren't you? Of course the first equation is easier to read, but it's no surprise that this may actually be slower. Like the imperative bubblesort is easier to read than the imperative quicksort but far slower. Put differently, making Haskell as fast as C is easy: just write a slower C program! Namely one that is as easy to read as the Haskell version. If you implement mean xs = sum xs / fromIntegral (length xs) directly in C, I bet you'll be delighted to discover that they perform similarly (using linked lists in the C version). Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Don Stewart wrote: I don't understand what's ugly about: go s l x | x m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1) And the point is that it is *reliable*. If you make your money day in, day out writing Haskell, and you don't want to rely on radical transformations for correctness, this is a sensible idiom to follow. Nothing beats understanding what you're writing at all levels of abstraction. What sets Haskell apart from every other programming language ever used in mainstream programming? You might say conciseness, or the ability to use lazy evaluation to structure your code in usual ways, or something like that. I would say what sets Haskell apart is abstraction. There are other things, but this is the big one. Haskell allows you to abstract almost everything. The result is often highly succinct yet very readable programs. It would seem a terribly shame if you always have to throw away Haskell's key advantage to get decent runtime performance. If you're trying to get a real program to work, right now, then yes, you may have no choice. But that doesn't mean we shouldn't strive for ways to keep code high-level yet performant. [I'm curios about your other comment. Does anybody, anywhere in the world, actually make *money* using Haskell? This seems rather unlikely to me...] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
apfelmus wrote: Andrew Coppin wrote: Look closer: it's hardER to read. mean xs = sum xs / fromIntegral (length xs) mean = go 0 0 n where go s l x | x m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1 One version makes it instantly clear, at a glance, what is happening. The other requires you to mentally walk round a look, imperative style, to figure out what's happening. It's not a *big* deal, but it's unfortunate. I'm more worried about what happens in less trivial examples. [Let's face it, who wants to compute the sum of the numbers from 1 to N?] Hm, it seems like you're expecting magic, aren't you? Well, obviously it would be nice, wouldn't it? ;-) Of course the first equation is easier to read, but it's no surprise that this may actually be slower. Like the imperative bubblesort is easier to read than the imperative quicksort but far slower. I'm just saying, I prefer it when somebody posts some tiny snippet of Haskell that does the same thing as a 40-line C program, and then show how using some novel technique they just invented, the Haskell version actually outperforms C even though it's more reasable and more maintainable. Hey, who *wouldn't* like to have their cake and eat it too? :-) But yeah, I get the point. Everybody wants me to be quiet and go away. So I'll go be quiet now... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
Am Freitag, 16. Mai 2008 21:33 schrieb Achim Schneider: Andrew Coppin [EMAIL PROTECTED] wrote: Wait... unexpected end of input; expecting [...] end of input [...] That's just *wrong*...! ;-) But don't despaire - show us your parser and what it's supposed to parse, and I'm sure somebody [maybe even me] will be able to tell you what's up. This is what I came up with while simplifying the parser: import Text.Parsec identifier = do whiteSpace s - many1 letter whiteSpace return s whiteSpace = do eof | ((many $ choice [ char ' ', newline ]) return ()) main = do let syn = runParser (do char '\\' many1 identifier char ':' whiteSpace identifier whiteSpace ) () \\a b print syn running char '\\' on input \\a b, okay, no problem. running many1 identifier on remaining input a b 1. whiteSpace: no eof, many (choice [char ' ', newline) returns [], all fine, nothing consumed 2. many1 letter, remainin input begins with 'a', okay, many1 letter returns a, remaining input b 3. whiteSpace: n eof, one ' ' ~ ' ' consumed, remains b first identifier parsed, try another one. whiteSpace again consumes nothing, many1 letter returns b, remaining input is null. whiteSpace finds eof, second identifier parsed, all input consumed. Now there are two options for a successful parse, a) another identifier b) ':' a) 1. whiteSpace, finds eof, consumes nothing, success 2. many1 letter fails immediately, nothing consumed, overall, identifier fails without consuming anything. b) char ':' fails without consumption. Drat, I want an identifier or a ':' here, I don't expect end of input yet. unexpected end of input expecting Lemme look what would I need here to continue. Ah, an identifier, how would that start? Oh, yes it could start with end of input what else? many (choice [char ' ', newline]), 'many', hmm doesn't require anything specific, I'll skip that, what then? many1 letter, oh, yes , letter Or I could continue with char ':' here, so or \:\ Oops, bad definition of whiteSpace, I'd say. Don't accept an eof unless you really don't want to continue. Admittedly, this is a quite degenerate case crouching in at least 10 corners simultaneously. Anyway, I get % ./test Left (line 1, column 5): unexpected end of input expecting end of input, letter or : and if I change it to whiteSpace = do (many eof return ()) | ((many $ choice [ char ' ', newline ]) return ()) Left (line 1, column 3): unexpected expecting letter, end of input or : Sure thing, (many eof) never fails, so the new whiteSpace is in fact many eof return () So after having parsed the first identifier, we're trying to either parse another one or a ':'. First, identifier is tried. many eof succeeds, now try letter, that fails. so we have a successful start into many eof, hence, for identifier to succeed, we need more eofs or a letter next ~ expecting end of input, letter Or we have no more identifiers, then we need or \:\ Please, please don't ask me for the rationale of using eof like this, you would get the same answer as if you'd ask me why I cast a stone into the sea. And why did you do that? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
On Fri, 16 May 2008, Achim Schneider wrote: Andrew Coppin [EMAIL PROTECTED] wrote: Wait... unexpected end of input; expecting [...] end of input [...] That's just *wrong*...! ;-) But don't despaire - show us your parser and what it's supposed to parse, and I'm sure somebody [maybe even me] will be able to tell you what's up. This is what I came up with while simplifying the parser: import Text.Parsec identifier = do whiteSpace s - many1 letter whiteSpace return s whiteSpace = do eof | ((many $ choice [ char ' ', newline ]) return ()) main = do let syn = runParser (do char '\\' many1 identifier char ':' whiteSpace identifier whiteSpace ) () \\a b print syn Admittedly, this is a quite degenerate case crouching in at least 10 corners simultaneously. Anyway, I get % ./test Left (line 1, column 5): unexpected end of input expecting end of input, letter or : Confusing, isn't it? It's almost the right message, too. I'm pretty sure the misbehaviour's because eof doesn't consume - see what happens if you put an error message on all of whiteSpace? and if I change it to whiteSpace = do (many eof return ()) | ((many $ choice [ char ' ', newline ]) return ()) Left (line 1, column 3): unexpected expecting letter, end of input or : Which is broken for your purposes, but that's because many always succeeds so the changed whiteSpace doesn't actually eat whitespace. Please, please don't ask me for the rationale of using eof like this, you would get the same answer as if you'd ask me why I cast a stone into the sea. As a matter of general practice I'd suggest including eof exactly once, as in: topLevel = do {r - realTopLevel; eof; return r} realTopLevel = ... Which isn't to say that you haven't run into something confusing and possibly broken here, of course. -- [EMAIL PROTECTED] The reason for this is simple yet profound. Equations of the form x = x are completely useless. All interesting equations are of the form x = y. -- John C. Baez ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
On Fri, 16 May 2008, Philippa Cowderoy wrote: Confusing, isn't it? It's almost the right message, too. I'm pretty sure the misbehaviour's because eof doesn't consume - see what happens if you put an error message on all of whiteSpace? It is indeed, and because the error merging code can't tell eof's don't consume from the don't consume try returns when its parm fails - nor is there any equivalent distinction in the error values. Which is to say: it's broken, but at least I know how to fix it in the library. -- [EMAIL PROTECTED] The reason for this is simple yet profound. Equations of the form x = x are completely useless. All interesting equations are of the form x = y. -- John C. Baez ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Daniel Fischer [EMAIL PROTECTED] wrote: [very helpful stuff] Please, please don't ask me for the rationale of using eof like this, you would get the same answer as if you'd ask me why I cast a stone into the sea. And why did you do that? To cast away something I don't understand. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Achim Schneider wrote: Guess who ran into that with a separate token for layout-inserted braces? It can't be me, as I attempted to be as lazy as possible, not going for a tokenising pass, and ended up being too lazy. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Andrew Coppin [EMAIL PROTECTED] wrote: But yeah, I get the point. Everybody wants me to be quiet and go away. So I'll go be quiet now... Yes and no. Everybody wants you to be quiet and go to your study, writing a compiler that's Smart Enough(tm). We will let you out as soon as you're finished and supply you with pizza and crackers from time to time. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
On Fri, 16 May 2008, Achim Schneider wrote: Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Achim Schneider wrote: Guess who ran into that with a separate token for layout-inserted braces? It can't be me, as I attempted to be as lazy as possible, not going for a tokenising pass, and ended up being too lazy. Nah, you just picked the wrong way to attempt discipline. I don't use separate tokenising/lexing passes in a lot of my code (though you can't really avoid it when you want to do layout), it's a matter of knowing how it's done. Unless you've got a lexical structure that prevents it (which is to say, there're situations in which two tokens following each other aren't allowed to have whitespace between them), it's a good idea to have your token productions eat any whitespace following them, and then your toplevel becomes: do {whitespace; r - realTopLevel; eof; return r} and then you need never worry about it again. -- [EMAIL PROTECTED] Ivanova is always right. I will listen to Ivanova. I will not ignore Ivanova's recomendations. Ivanova is God. And, if this ever happens again, Ivanova will personally rip your lungs out! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
Achim Schneider wrote: Andrew Coppin [EMAIL PROTECTED] wrote: But yeah, I get the point. Everybody wants me to be quiet and go away. So I'll go be quiet now... Yes and no. Everybody wants you to be quiet and go to your study, writing a compiler that's Smart Enough(tm). We will let you out as soon as you're finished and supply you with pizza and crackers from time to time. I... I think you just described my ideal place of employment! 0_0 It sure as hell beats the living daylights out of the nonesense I just spent 9-5 today dealing with. :-S ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Achim Schneider wrote: Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Achim Schneider wrote: Guess who ran into that with a separate token for layout-inserted braces? It can't be me, as I attempted to be as lazy as possible, not going for a tokenising pass, and ended up being too lazy. Nah, you just picked the wrong way to attempt discipline. I don't use separate tokenising/lexing passes in a lot of my code (though you can't really avoid it when you want to do layout), it's a matter of knowing how it's done. Unless you've got a lexical structure that prevents it (which is to say, there're situations in which two tokens following each other aren't allowed to have whitespace between them), it's a good idea to have your token productions eat any whitespace following them, and then your toplevel becomes: do {whitespace; r - realTopLevel; eof; return r} and then you need never worry about it again. My problem is that realTopLevel = expr, and that I get into an infinite recursion, never closing enough parens, never hitting eof. Additionally, two passes are definitely easier to reason about, and it's wise to be lazy there. Btw: Is there any way to make Parsec return a tree of things it tried? The end-user error messages are quite often just not informative enough while debugging the parser itself. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
On Fri, 16 May 2008, Don Stewart wrote: I don't understand what's ugly about: go s l x | x m = s / fromIntegral l | otherwise = go (s+x) (l+1) (x+1) I suspect you've been looking at low-level code too long. How about the total lack of domain concepts? Try: mean n m = let (sum, length, _) = go (0,0,n) in sum / fromIntegral length where go :: (Double, Int, Double) - (Double, Int, Double) go t@(s,l,x) | x m = t | otherwise = go (s+x) (l+1) (x+1) as a starting point. I might consider generalising to a while HOF while I'm at it, because ultimately this is a while loop. Admittedly that would be relying on the implementation doing a little inlining, which you're not reliant on. Given the audience it'd be good to see some of the working to pull it off via fusion in a comment too: -- [1 .. d ] = unfoldr (let f n | n d = Nothing -- f n = Just (n,n+1) in f) 1 -- sum = foldr ... -- length = foldr ... -- sumAndLength = foldr ... (as calculated from the above) -- mean [1 .. d] = s / l where -- (sum, length) = sumAndLength [1 .. d] -- = sumAndLength . unfoldr ... -- = foldr ... . unfoldr ... -- = ... Some things it might be nice to have and/or know about: * We really ought to be able to build the sumAndLength fold by building the appropriate tuple and tuple function from its components - with there being a standard idiom for naming them, and a library of such things to hand. Same thing for go, too - this means we retain the domain concepts in its implementation by default. The interesting thing about go is that we ourselves running the guts of an unfold at the same time, which means it supplies our termination criteria - I suspect I ought to post a 'most general' form of go on that basis soon? * Does nesting unboxed tuples work appropriately? I was about to suggest a standard way of doing the wiring for the tupling as well, but so long as nesting unboxed tuples works and the optimiser 'gets it' then there's an arrow instance that ought to do nicely! While not quite as low-level, the resulting code should hopefully be easy bait for GHC's optimiser (if not, someone please yell!), while both retaining much of the domain info of the original code and conveying much about how it's made to go fast. Nothing beats understanding what you're writing at all levels of abstraction. How about ensuring that a casual reader can do the same quickly? -- [EMAIL PROTECTED] Performance anxiety leads to premature optimisation ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
On Fri, 16 May 2008, Achim Schneider wrote: My problem is that realTopLevel = expr, and that I get into an infinite recursion, never closing enough parens, never hitting eof. Have you run into the left-recursion trap, by any chance? This doesn't work: expr = do expr; ... You can cover common cases with combinators like many* and chain* though. Btw: Is there any way to make Parsec return a tree of things it tried? The end-user error messages are quite often just not informative enough while debugging the parser itself. If you're willing to accept a little pain, you can write a few helper functions akin to ? that keep a log in Parsec's state and extract it from there. -- [EMAIL PROTECTED] Society does not owe people jobs. Society owes it to itself to find people jobs. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]
On Fri, 16 May 2008, Andrew Coppin wrote: Obviously most people would prefer to write declarative code and feel secure that the compiler is going to produce something efficient. Ultimately the only way to do this is to stick to Einstein's advice - make things as simple as possible but no simpler. This means that if you care about speed then somewhere, the structure that enables a fast implementation needs to be declared so that the compiler can work with it. For example, you might not want to hand-fuse (I know I get bored of it pretty quickly) but the possibility of fusion will have to be clear. If you don't want to have to do it yourself (or don't know how!) and you want to be confident that something's going to run fast, that means a library covering a range of known cases that'll all go quickly. Don has been a major contributor here! But it's hard work, and if you don't understand how fast code is structured then ultimately you won't be able to predict - there'll never be a guarantee that lets you be completely ignorant. -- [EMAIL PROTECTED] 'In Ankh-Morpork even the shit have a street to itself... Truly this is a land of opportunity.' - Detritus, Men at Arms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C.
Andrew Coppin [EMAIL PROTECTED] writes: I'm more worried about what happens in less trivial examples. [Let's face it, who wants to compute the sum of the numbers from 1 to N?] Inspired by Don's blog post, and coincidentally working on a program where profiling points to one particular, short function as responsible for 60% of the work, I thought this would be a good time to look into core and reveal the deep secrets of my code. This is the function: mkAnn :: ByteString - Annotation mkAnn = pick . B.words where pick (_db:up:rest) = pick' up $ getGo rest pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev) getGo = dropWhile (not . B.isPrefixOf (pack GO:)) A bit clunky, but simple enough: given a line of input, break into words, pick word number two, the word starting with GO: and the second-to-next word. Here are the data types involved: data Annotation = Ann !UniProtAcc !GoTerm !EvidenceCode deriving (Show) newtype GoTerm = GO Int deriving (Eq,Ord) type UniProtAcc = ByteString data EvidenceCode = ... -- many nullary constructors Unfortunately, this results in no less than four pages of core, with tons of less intelligible identfiers and nested cases and whatnot... any idea why this would be so slow? -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C.
ketil: Andrew Coppin [EMAIL PROTECTED] writes: I'm more worried about what happens in less trivial examples. [Let's face it, who wants to compute the sum of the numbers from 1 to N?] Inspired by Don's blog post, and coincidentally working on a program where profiling points to one particular, short function as responsible for 60% of the work, I thought this would be a good time to look into core and reveal the deep secrets of my code. This is the function: mkAnn :: ByteString - Annotation mkAnn = pick . B.words where pick (_db:up:rest) = pick' up $ getGo rest pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev) getGo = dropWhile (not . B.isPrefixOf (pack GO:)) read $ B.unpack go Looks suspicious. You're unpacking to lists. ByteString performance rule 1: don't unpack to lists. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
On Fri, May 16, 2008 at 12:03 PM, Andrew Coppin [EMAIL PROTECTED] wrote: Since a tree is a kind of container, yes, it should be a monad. [I'm still not really sure whether it's useful.] Not so much containers in general, but 'flattenable' containers. You can flatten a list of lists to a list like this: [[1,2,3],[4,5],[6]] - [1,2,3,4,5,6] Similarly you can 'flatten' some kinds of trees of trees by grafting the contained trees directly into the containing tree. But consider containers that always contain exactly two elements. It's not immediately obvious how to flatten such a thing because a container of containers will have 4 elements so at the least you'll have to throw two elements away. In fact, you can use the Reader monad as a fixed size container monad. On the other hand, Maybe is a rather odd kind of container, but a very useful monad... Do you really find it odd? It's like many ordinary household containers: there's room to contain one object, but it might in fact be empty. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C.
Ketil Malde wrote: mkAnn :: ByteString - Annotation mkAnn = pick . B.words where pick (_db:up:rest) = pick' up $ getGo rest pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev) getGo = dropWhile (not . B.isPrefixOf (pack GO:)) It seems at first face miraculously coincidental that the dropWhile in the getGo definition knows to stop dropping when there are exactly 4 elements, in order to match the pattern in the second parameter of the pick' definition, whose argument is provided by (getGo Rest). What magic makes this true? Just curious... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C.
Dan Weston wrote: Ketil Malde wrote: mkAnn :: ByteString - Annotation mkAnn = pick . B.words where pick (_db:up:rest) = pick' up $ getGo rest pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev) getGo = dropWhile (not . B.isPrefixOf (pack GO:)) It seems at first face miraculously coincidental that the dropWhile in the getGo definition knows to stop dropping when there are exactly 4 elements, in order to match the pattern in the second parameter of the pick' definition, whose argument is provided by (getGo Rest). What magic makes this true? Just curious... I didn't mean exactly 4, but at least 3. Otherwise, I'm still curious! :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Philippa Cowderoy [EMAIL PROTECTED] wrote: On Fri, 16 May 2008, Achim Schneider wrote: My problem is that realTopLevel = expr, and that I get into an infinite recursion, never closing enough parens, never hitting eof. Have you run into the left-recursion trap, by any chance? This doesn't work: expr = do expr; ... expr = do {e - parens expr; return $ Nest e} | lambda | _let | try app | atom There's at least one token before any recursion, so I guess not. After all, it terminates. It's my state that does not succeed in directing the parser not to mess up, so I'm reimplementing the thing as a two-pass but stateless parser now. Definitely the easier and clearer thing to do: I can have an end of line token that carries the number of trailing spaces, so I got perfect indent information without any pain involved, at all, and don't have to make parsers fail based on state. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Write Haskell as fast as C.
Dan Weston [EMAIL PROTECTED] writes: mkAnn :: ByteString - Annotation mkAnn = pick . B.words where pick (_db:up:rest) = pick' up $ getGo rest pick' up' (go:_:ev:_) = Ann (B.copy up') (read $ B.unpack go) (read $ B.unpack ev) getGo = dropWhile (not . B.isPrefixOf (pack GO:)) It seems at first face miraculously coincidental that the dropWhile in the getGo definition knows to stop dropping when there are exactly 4 elements, in order to match the pattern in the second parameter of the pick' definition, whose argument is provided by (getGo Rest). What magic makes this true? Just curious... You want the long story? :-) This is for parsing the GOA file format, which contains links between proteins from the UniProt database to Gene Onthology (GO) terms. The format is not quite as regular as one would wish, but the second word is always the protein id, and whenever the GO term turns up, it is followed by something I forget (an InterPro reference perhaps) and then the evidence code - which I want. You feel happier now, I can tell. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Proving my point
On Sat, 17 May 2008, Achim Schneider wrote: There's at least one token before any recursion, so I guess not. After all, it terminates. It's my state that does not succeed in directing the parser not to mess up, so I'm reimplementing the thing as a two-pass but stateless parser now. In most cases, you're better off stateless unless you've got a really good reason for it. Or at least, not using the state for anything that affects the parse itself. Definitely the easier and clearer thing to do: I can have an end of line token that carries the number of trailing spaces, so I got perfect indent information without any pain involved, at all, and don't have to make parsers fail based on state. Definitely! Are you doing some form of layout? It's certainly not worth doing in one pass IMO, I ended up with a three pass design much like that in the Haskell 98 report. Well, that's an understatement - I took the algorithm from it! -- [EMAIL PROTECTED] There is no magic bullet. There are, however, plenty of bullets that magically home in on feet when not used in exactly the right circumstances. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Proving my point
Philippa Cowderoy [EMAIL PROTECTED] wrote: On Sat, 17 May 2008, Achim Schneider wrote: Definitely the easier and clearer thing to do: I can have an end of line token that carries the number of trailing spaces, so I got perfect indent information without any pain involved, at all, and don't have to make parsers fail based on state. Definitely! Are you doing some form of layout? Yes, /pair x y m: m x y /fst z: z \p q: p /snd z: z \p q: q /numbers: pair one two /run: pair (fst numbers) (snd numbers) run is supposed to work (/ indicates a let). I'm trying to purge scheme out of my mind by implementing something that looks quite like it, and then change it. The rule is simple: An indented line continues the previous, and a non-indented closes every opened paren except one from the previous line, eof closing all that are left. I still have to think about recursive lets, but I guess I will go unlambda and just include a Y combinator, keeping the syntax simple. OTOH, I'm thinking about experimenting with a thing remotely resembling varargs and streams, being able to generate and consume possibly infinite argument streams, somewhat equalling tuples, lists and application. Just playing around, you know. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] alex + happy parser problem
Hi, To learn alex and happy, I'm trying to write a parser for a simple expression language. When I wrote my own lexer and just used happy, it was fine. When I used the basic wrapper of alex it was also fine. However, when I use the posn wrapper to get position information, I get a strange exception when the parse error occurs at the end of the input. For example, parsing 1 + yields Internal Happy error rather than something like Parse error at line 1, column 5 The lexer and parser are attached. Can anyone see what I'm doing wrong? calling parse 1+ yields a Internal Happy error instead of a parse error as I would expect. Thanks, Sean -- -- Lexer -- { module ExprLexer ( Token(..), AlexPosn(..), alexScanTokens, tokenPosn ) where } %wrapper posn $digit = 0-9 tokens :- $digit+ { (\p s - Int p (read s)) } [\+] { (\p s - Sym p (head s)) } { data Token = Sym AlexPosn Char | Int AlexPosn Int deriving (Eq, Show) tokenPosn (Sym p _) = p tokenPosn (Int p _) = p } -- --- Parser -- { module ExprParser where import ExprLexer (Token(..), alexScanTokens, tokenPosn, AlexPosn(..)) } %name parseExp %tokentype { Token } %token int { Int _ $$ } '+' { Sym _ '+' } %right '+' %% Exp : Exp '+' Exp { Add $1 $3 } | int { Const $1 } { data Expr = Const Int | Add Expr Expr deriving Show parse :: String - Expr parse = parseExp . alexScanTokens happyError :: [Token] - a happyError tks = error (Parse error at ++ lcn ++ \n) where lcn = case tks of [] - end of file tk:_ - line ++ show l ++ , column ++ show c where AlexPn _ l c = tokenPosn tk } ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ghc on Ubuntu Linux?
Hello, I am running ghc and tools on Ubuntu. I seem to be running into very strange problems between ghc-pkg and the Ubuntu package manager. Suddenly runhaskell Setup.hs configure just stops working ... Are any other ghc/Ubuntu users running into problems? If so, please tell me what problems. This is killing my Haskell work! Regards, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ghc on Ubuntu Linux?
ghc-pkg list gives me [EMAIL PROTECTED]:~$ ghc-pkg list /usr/local/lib/ghc-6.8.2/package.conf: Cabal-1.2.3.0, GLUT-2.1.1.1, HUnit-1.2.0.0, OpenGL-2.2.1.1, QuickCheck-1.1.0.0, array-0.1.0.0, base-3.0.1.0, bytestring-0.9.0.1, cgi-3001.1.5.1, containers-0.1.0.1, directory-1.0.0.0, fgl-5.4.1.1, filepath-1.1.0.0, (ghc-6.8.2), haskell-src-1.0.1.1, haskell98-1.0.1.0, hpc-0.5.0.0, html-1.0.1.1, mtl-1.1.0.0, network-2.1.0.0, old-locale-1.0.0.0, old-time-1.0.0.0, packedstring-0.1.0.0, parallel-1.0.0.0, parsec-2.1.0.0, pretty-1.0.0.0, process-1.0.0.0, random-1.0.0.0, readline-1.0.1.0, regex-base-0.72.0.1, regex-compat-0.71.0.1, regex-posix-0.72.0.2, rts-1.0, stm-2.1.1.0, template-haskell-2.2.0.0, time-1.1.2.0, unix-2.3.0.0, xhtml-3000.0.2.1 I am using version ghc-6.8.2. V On Fri, May 16, 2008 at 11:51 PM, Galchin, Vasili [EMAIL PROTECTED] wrote: Hello, I am running ghc and tools on Ubuntu. I seem to be running into very strange problems between ghc-pkg and the Ubuntu package manager. Suddenly runhaskell Setup.hs configure just stops working ... Are any other ghc/Ubuntu users running into problems? If so, please tell me what problems. This is killing my Haskell work! Regards, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Short circuiting and the Maybe monad
Dan Piponi-2 wrote: In fact, you can use the Reader monad as a fixed size container monad. Interesting that you say that. Reader seems to me more as an anti-container monad. -- View this message in context: http://www.nabble.com/Short-circuiting-and-the-Maybe-monad-tp17200772p17288351.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe