Re: [Haskell-cafe] Export Haskell Libraries
Duncan Coutts wrote: So it's easy if you link the system using ghc. If you want to link it all using gcc instead, yeah, that's a bit harder. You can see most of the flags ghc passes to gcc as they're just in the package configuration for the rts and base packages (ghc-pkg display rts / base). It should be fairly straightforward to generate a gnu linker script from all this that you could use with gcc when linking your whole system. By tucking the ghc flags away in a linker scrupt you will not terrify your fellow developers with all the odd -u flags. That was my first thought and in fact I did write such a script. The only problem is I'm afraid that the link stages for the software I have integrate to may be rather complex and I thought that maybe this would not be the best approach if there were order dependencies etc. But maybe it's not so bad. In the end I managed to capture all the dependencies in CMake so I'm hoping that will make it a little easier to do the final integration. As for the issue of cabal putting generated files in a directory other than the source tree, you can tell cabal exactly which directory to use, so it's not that non-portable to go grubbing around in it to find the .o files you need to link into the archive file. 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. Alternatively you could just let cabal build the .a file. It can include externally generated .o files into the archive. Alternatively you can just use two .a files, keeping your other .o's in a separate file. Or you could even combine the two archives together as a later build step. Yes, this would be an attractive approach I think. Is it a matter of passing the correct flags to ghc, Ghc-options: -? At first glance, looking at the basic tutorial it seemed like to build a library one uses a line like Exposed Modules: A B C However I thought this would build Haskell only libraries.Then there is the business of merging libraries, which I suppose is done with ar and ranlib by extracting all the object files from one library and then adding them back in to the other. If it had to portable to windows as well I wonder if this would work. Actually it's not too bad if you ignore all the 50 -u flags. Apart from that, the single runtime library you want is just three: HSbase, HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp, dl and rt. running ghc -v for all my haskell code forced me to link to these libraries ultimately: HShaskell98 HSregex-compat HSregex-posix HSregex-base HSparsec HSbase HSbase_cbits HSrts m gmp dl rt There is a project for this year's Google Summer of Code to use dynamic libraries on Linux. Perhaps this would make the situation better for you since dynamic libs record their own dependencies much better. Ideally you would only have to link to your own Haskell package built as a .so and that would pull in the dependencies on HSbase.so, HSrts.so and the other system libs. Duncan Then it would be very similar to the windows build steps and probably a bit easier since one wouldn't have to mess with dlltools and converting libraries to ms vc formats etc. Really all that's needed though is a tool that can automagically wrap a homegrown static or even dynamic library that contains the needed components of the GHC run time library along with the additional user code. I know all the object files are available as are of course the libraries themselves, so such a script is not impossible. It seems that ghc itself is doing some kind of dependency analysis to determine the final call to gcc. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- View this message in context: http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9973642 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weaving fun
Matthew Brecknell wrote: Jan-Willem Maessen: Interestingly, in this particular case what we obtain is isomorphic to constructing and reversing a list. Jan-Willem's observation also hints at some interesting performance characteristics of difference lists. It's well known that difference lists give O(1) concatenation, but I haven't seen much discussion of the cost of conversion to ordinary lists. The conversion cost seems to be O(n), where n is the number of concatenations performed to build the difference list. The O(n) conversion cost is amortized over deconstructing the list thanks to laziness. So the head element is O(1). If head were O(n) then it would never be a win over using reverse. [snip] Slightly more interesting is the observation that the grouping of difference list concatenations has a significant impact on the conversion cost, and in particular, on when the cost is incurred. When concatenations are grouped to the right, we get lazy conversion. Grouped to the left, we get strict(er) conversion. AFAIK, constructing a difference list using (.) is exactly like constructing a tree. The cost of converting to a normal list and getting the head element requires traversing the tree from the root to the first element. So if you construct it with just appends then the first element is the left node of the root, which is very fast. And if you construct it with prepends then the first element requires traversing the whole list. Since the list can only be deconstructed in order the sensible way to build a difference list is with appends. Note that pre-pending a huge list will blow the stack (for at least GHC). -- Chris ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Parsing indentation-based languages with Parsec
Hi, first time list poster :) I've searched around a bit but haven't been able to find any examples of this. I want to be able to parse a language (such as Haskell, Python) which has only EOL as the 'statement' separator and has indentation levels to indicate block structure. Whilst doing this I want to use Parsec's nice library. The first thing I noticed was that Parsec's whiteSpace parser will ignore EOL as just whiteSpace, so I need to redefine that. Is this the correct way to do it? I've only been using Haskell for a week or so so I'm not too sure on the record structures and updating them... lexer :: P.TokenParser () lexer = ( P.makeTokenParser emptyDef { commentLine= #, nestedComments = True, identStart = letter, identLetter= letter, opStart= oneOf +*/-=, opLetter = oneOf +*/-=, reservedNames = [], reservedOpNames = [], caseSensitive = False } ) { --update lexer fields P.whiteSpace = do --just gobble spaces many (char ' ') return () } (I got the basic code from the tutorial contained within the Parsec docs.) For handling the indented blocks I thought I would use something to hold current indentation state, as Parsec has support for threading state through all the parsers. Is this the right way to go about this? Has anyone done the 'groundwork' with parsing such languages so I don't need to reinvent this? Thanks in advance, - porges. signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: k-minima in Haskell
[EMAIL PROTECTED] wrote: Quoting apfelmus [EMAIL PROTECTED]: You mean O(k * log n + n) of course. Erm, yes. You can do it in an imperative language by building a heap in O(n) time followed by removing k elements, in O(k log n) time. Ah, sorry, there are indeed to variants not comparable to each other. Threading a heap of k elements over the entire list needs O(n log k + k) time and putting all of the list into a heap takes O(k log n + n) time. For say k = O(sqrt(n)), the former is slower than the latter but it only needs to keep O(k) list elements in memory. I think that every k-minima algorithm of the form take k . sort has to keep all list elements in memory: the sort may not throw away anything because it cannot know how many elements are requested. Regards, apfelmus ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Why Perl is more learnable than Haskell
Hello kynn, Thursday, April 12, 2007, 7:10:56 AM, you wrote: rather pragmatic. I have not been able to find enough support in Haskell for everyday tasks (e.g. read a stream from a socket; parse it into a simple data structure; process the data in the structure; print out the results to a socket; look here: http://haskell.org/haskellwiki/Library/AltBinary -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A monad using IO, Reader, Writer, State and Error
Hi all, for my current project I need a monad that is an instance of MonadIO, MonadReader, MonadWriter, MonadState, and MonadError. I see two ways for defining such a monad using the mtl. 1) type MyMonad = ErrorT E (RWST R W S IO) and 2) type MyMonad = RWST R W S (ErrorT E IO) I can't figure out what is the difference between these two definitions and therefore which one is more suitable for my problem. Or are the equivalent and it is unimportant which one I use? Or is it even better define a new type like newtype MyMonad a = MyMonad { runMyMonad :: R - S - IO (Either E a,S,W) } and declare instances for all 5 type classes? Thanks for your help in advance, Martin. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
You may be missing a few recursive calls there :-) Indeed. I'm confused. Is this a legitimate stable quicksort, or not? (My guess is, it is indeed legit as written.) This was also the first I have heard of stability as a sort property. http://perldoc.perl.org/sort.html may shed some light on this... A stable sort means that for records that compare equal, the original input ordering is preserved. Mergesort is stable, quicksort is not. Is this description a fair characterization of stability for the current discussion? I'm a bit confused but if I understand correctly sort from the prelude is non stable quicksort, which has O(k n^2) as the worst case, whereas stable quicksort has O( k* log n + n). non-stable quicksort is just sort from the prelude: qsort [] = [] qsort (x:xs) = qsort (filter ( x) xs) ++ [x] ++ qsort (filter (= x) xs) If any in the above was incorrect, please holler. 2007/4/12, Stefan O'Rear [EMAIL PROTECTED]: On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote: On 4/11/07, Stefan O'Rear [EMAIL PROTECTED] wrote: If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) You may be missing a few recursive calls there :-) Indeed. Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
And for reference, here is again stefan's stable quicksort from his earlier post. sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) This is the code whose legitimacy I am requesting confirmation of. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: You may be missing a few recursive calls there :-) Indeed. I'm confused. Is this a legitimate stable quicksort, or not? (My guess is, it is indeed legit as written.) This was also the first I have heard of stability as a sort property. http://perldoc.perl.org/sort.html may shed some light on this... A stable sort means that for records that compare equal, the original input ordering is preserved. Mergesort is stable, quicksort is not. Is this description a fair characterization of stability for the current discussion? I'm a bit confused but if I understand correctly sort from the prelude is non stable quicksort, which has O(k n^2) as the worst case, whereas stable quicksort has O( k* log n + n). non-stable quicksort is just sort from the prelude: qsort [] = [] qsort (x:xs) = qsort (filter ( x) xs) ++ [x] ++ qsort (filter (= x) xs) If any in the above was incorrect, please holler. 2007/4/12, Stefan O'Rear [EMAIL PROTECTED]: On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote: On 4/11/07, Stefan O'Rear [EMAIL PROTECTED] wrote: If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) You may be missing a few recursive calls there :-) Indeed. Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A monad using IO, Reader, Writer, State and Error
Martin Huschenbett wrote: Hi all, for my current project I need a monad that is an instance of MonadIO, MonadReader, MonadWriter, MonadState, and MonadError. I see two ways for defining such a monad using the mtl. 1) type MyMonad = ErrorT E (RWST R W S IO) and 2) type MyMonad = RWST R W S (ErrorT E IO) I can't figure out what is the difference between these two definitions and therefore which one is more suitable for my problem. Or are the equivalent and it is unimportant which one I use? It affects where and how you can catch and respond to errors. The main difference is that in (1) the final result includes 's' and 'w' in the event of an error and in (2) the final result does not include 's' and 'w' in the event of an error. Assume op :: MyMonad a (1) runErrorT op :: RWST r w s IO (Either e a) runRWST r s (runErrorT op) :: IO (Either e a, s, w) and catchError :: (ErrorT e (RWST r w s IO a)) - (e - (ErrorT e (RWST r w s IO a))) - (ErrorT e (RWST r w s IO a)) (2) runRWST r s op :: ErrorT e IO a runErrorT (runRWST r s op) :: IO (Either e (a,s,w)) The useful outer instance is catchError :: (RWST r w s (ErrorT e IO) a) - (e - (RWST r w s (ErrorT e IO) a)) - (RWST r w s (ErrorT e IO) a) The not very useful inner instance catchError :: (ErrorT e IO a) - (e - (ErrorT e IO a)) - (ErrorT e IO a) you have the (somewhat silly) option to use this to form lift (catchError io handler) :: (RWST r w s (ErrorT e IO) a) but the outer instance is usually better. So (1) gives (Left e,s,w) or (Right a,s,w) and (2) gives (Left e) or (Right (a,s,w)) Or is it even better define a new type like newtype MyMonad a = MyMonad { runMyMonad :: R - S - IO (Either E a,S,W) } and declare instances for all 5 type classes? Thanks for your help in advance, Martin. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
Trying to understand this better I also came across http://groups.google.de/group/fa.haskell/browse_thread/thread/1345c49faff85926/8f675bd2aeaa02ba?lnk=stq=%22I+assume+that+you+want+to+find+the+k%27th+smallest+element%22rnum=1hl=en#8f675bd2aeaa02ba where apfulmus gives an implementation of mergesort, which he claims runs in O(n) time instead of the expected O(n log n) Does that mean you can have the k minima in O(n) time, where n is length of list, which would seem to be an improvement? mergesort [] = [] mergesort xs = foldtree1 merge $ map return xs foldtree1 f [x] = x foldtree1 f xs = foldtree1 f $ pairs xs where pairs []= [] pairs [x] = [x] pairs (x:x':xs) = f x x' : pairs xs merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = if x = y then x:merge xs (y:ys) else y:merge (x:xs) ys 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: And for reference, here is again stefan's stable quicksort from his earlier post. sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) This is the code whose legitimacy I am requesting confirmation of. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: You may be missing a few recursive calls there :-) Indeed. I'm confused. Is this a legitimate stable quicksort, or not? (My guess is, it is indeed legit as written.) This was also the first I have heard of stability as a sort property. http://perldoc.perl.org/sort.html may shed some light on this... A stable sort means that for records that compare equal, the original input ordering is preserved. Mergesort is stable, quicksort is not. Is this description a fair characterization of stability for the current discussion? I'm a bit confused but if I understand correctly sort from the prelude is non stable quicksort, which has O(k n^2) as the worst case, whereas stable quicksort has O( k* log n + n). non-stable quicksort is just sort from the prelude: qsort [] = [] qsort (x:xs) = qsort (filter ( x) xs) ++ [x] ++ qsort (filter (= x) xs) If any in the above was incorrect, please holler. 2007/4/12, Stefan O'Rear [EMAIL PROTECTED]: On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote: On 4/11/07, Stefan O'Rear [EMAIL PROTECTED] wrote: If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) You may be missing a few recursive calls there :-) Indeed. Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
Rereading this, I see in fact apfelmus explains this is O(n + k*log n) for the first k elements, which this discussion also maintains is the best case. So, there's no discrepancy. I think this is a very valuable post to read for the explanation. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: Trying to understand this better I also came across http://groups.google.de/group/fa.haskell/browse_thread/thread/1345c49faff85926/8f675bd2aeaa02ba?lnk=stq=%22I+assume+that+you+want+to+find+the+k%27th+smallest+element%22rnum=1hl=en#8f675bd2aeaa02ba where apfulmus gives an implementation of mergesort, which he claims runs in O(n) time instead of the expected O(n log n) Does that mean you can have the k minima in O(n) time, where n is length of list, which would seem to be an improvement? mergesort [] = [] mergesort xs = foldtree1 merge $ map return xs foldtree1 f [x] = x foldtree1 f xs = foldtree1 f $ pairs xs where pairs []= [] pairs [x] = [x] pairs (x:x':xs) = f x x' : pairs xs merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = if x = y then x:merge xs (y:ys) else y:merge (x:xs) ys 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: And for reference, here is again stefan's stable quicksort from his earlier post. sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) This is the code whose legitimacy I am requesting confirmation of. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: You may be missing a few recursive calls there :-) Indeed. I'm confused. Is this a legitimate stable quicksort, or not? (My guess is, it is indeed legit as written.) This was also the first I have heard of stability as a sort property. http://perldoc.perl.org/sort.html may shed some light on this... A stable sort means that for records that compare equal, the original input ordering is preserved. Mergesort is stable, quicksort is not. Is this description a fair characterization of stability for the current discussion? I'm a bit confused but if I understand correctly sort from the prelude is non stable quicksort, which has O(k n^2) as the worst case, whereas stable quicksort has O( k* log n + n). non-stable quicksort is just sort from the prelude: qsort [] = [] qsort (x:xs) = qsort (filter ( x) xs) ++ [x] ++ qsort (filter (= x) xs) If any in the above was incorrect, please holler. 2007/4/12, Stefan O'Rear [EMAIL PROTECTED]: On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote: On 4/11/07, Stefan O'Rear [EMAIL PROTECTED] wrote: If you want to be really explicit about it, here is a sort that will work: sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) You may be missing a few recursive calls there :-) Indeed. Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: k-minima in Haskell
For various reasons I had a similar problem that I solved iteratively simply with a sorted list of the actual best elements. The only particular things were 1. keep element count (to easily know if the element should be inserted in any case) 2. keep the list in reverse order to have the biggest element as first, and make the common case (list stays the same) fast 3. make the list strict (avoid space leaks) not the best in worst case of decreasingly ordered elements O(n*k), but good enough for me. A set + explicit maximal element would probably be the best solution. Fawzi -- | keeps the score of the n best (high score) -- (uses list, optimized for small n) data NBest a = NBest Int [a] deriving (Eq) -- | merges an element in the result with given ranking function merge1 :: Int - (a - Double) - a - NBest a - NBest a merge1 n rankF fragment (NBest m []) | m==0 n0 = NBest 1 [fragment] | m==0 = NBest 0 [] | otherwise = error empty list and nonzero count merge1 n rankF fragment (NBest m (xl@(x0:xs))) | nm = NBest (m+1) (insertOrdered fragment xl) | rankF fragment (rankF x0) = NBest n (insertOrdered fragment xs) | otherwise = NBest m xl where insertOrdered x (x1:xr) | rankF x = rankF x1 = x:x1:xr | otherwise = let r = insertOrdered x xr in x1 `seq` r `seq` x1:r where insertOrdered x [] = [x] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weaving fun
On 4/11/07, Chris Kuklewicz [EMAIL PROTECTED] wrote: ... My previous weave, uses composition of (xs:) thunks instead of pairs: weave :: [[a]] - [a] weave [] = [] weave xss = helper id xss where helper :: ([[a]] - [[a]]) - [[a]] - [a] helper _rest ([]:_xss) = [] -- done helper rest [] = weave (rest []) helper rest ((x:xs):xss) = x : helper (rest . (xs:)) xss One might imagine an 'optimized' case like in weave': -- helper rest ((x:[]):xss) = let yss = rest ([]:[]) -- in x : helper (const yss) xss ... Nice! The iteration over the list can be abstracted using foldr: weave :: [[a]] - [a] weave [] = [] weave xss = foldr f (\rest - weave $ rest []) xss id where f [] _ = \_- [] f (x:xs) g = \rest - x : g (rest . (xs:)) This is beginning to look scary :-) To enable your last optimization you can replace the last alternative of 'f' by: f (x:xs) g = \rest - x : g (\l - rest $ case xs of [] - [[]] xs - xs:l ) The funny thing is that this definition looks very similar to my first weave. However the reverse parts are now removed because of the difference list trick: weave :: [[a]] - [a] weave ll = work ll [] [] where work ll = foldr f (\rst acc - work (reverse rst) [] acc) ll f [] g = \_ acc - reverse acc f (x:xs) g = \rst acc - g (xs:rst) (x:acc) Thanks, Bas van Dijk ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
G'day all. Quoting Thomas Hartman [EMAIL PROTECTED]: Does that mean you can have the k minima in O(n) time, where n is length of list, which would seem to be an improvement? It's worth considering what the theoretical minimum is. 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). Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] generate Haskell code from model
Hello everybody, I would like to start a discussion on how to generate best-practice Haskell code from a model, e.g. from EMF. It seems to be very difficult and unconvenient to simulate OOP with Haskell (as described in the paper Object-oriented style overloading for Haskell). However, I think it might be possible to generate something useful out of a model to not start from scratch an implementation. For example, I could imagine to generate for every class a module, import and export lists and a type class (with some restrictions) at the very least. In the EMF book there is an example, PurchaseOrder, look at http://www.awprofessional.com/content/images/0131425420/samplechapter/budinskych02.pdf at page 11. How would you like generated code from this model to look like? The most obvious way would be something like this: data PurchaseOrder = PurchaseOrder {shipTo::String, billTo:: String, items::[Item]} data Item = Item {productName::String, quantity::Int, price::Float} This does not work well if function names are reused or inheritance comes into play, however, even this might be a useful starting point (better than nothing). The benefits of the model+generate approach are well known. Best practices in programming are propagated, for Haskell e.g. use different modules for different things, use the tedious import/export lists, Haddock your code... What are your ideas? Best regards, Steffen -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weaving fun
The fun never ends... Bas van Dijk wrote: On 4/11/07, Chris Kuklewicz [EMAIL PROTECTED] wrote: ... My previous weave, uses composition of (xs:) thunks instead of pairs: weave :: [[a]] - [a] weave [] = [] weave xss = helper id xss where helper :: ([[a]] - [[a]]) - [[a]] - [a] helper _rest ([]:_xss) = [] -- done helper rest [] = weave (rest []) helper rest ((x:xs):xss) = x : helper (rest . (xs:)) xss The difference list is built with id and (rest . (xs:)) and (rest []) One might imagine an 'optimized' case like in weave': -- helper rest ((x:[]):xss) = let yss = rest ([]:[]) -- in x : helper (const yss) xss ... Nice! The iteration over the list can be abstracted using foldr: weave :: [[a]] - [a] weave [] = [] weave xss = foldr f (\rest - weave $ rest []) xss id where f [] _ = \_- [] f (x:xs) g = \rest - x : g (rest . (xs:)) That abstraction kills my ability to quickly see what is going on. Renaming this to weavefgh and adding type signatures: weavefgh :: [[a]] - [a] weavefgh [] = [] weavefgh xss = h xss id h :: [[a]] - ([[a]] - [[a]]) - [a] h = foldr f g g :: ([[a]] - [[a]]) - [a] g rest = weavefgh (rest []) f :: [a] - (([[a]] - [[a]]) - [a]) - ([[a]] - [[a]]) - [a] f [] _ = \_- [] f (x:xs) g = \rest - x : g (rest . (xs:)) Here we can see that the foldr builds a function h which is supplied id. let xss = [x1:x1s,x2:x2s] in h xss = foldr f g [(x1:x1s),(x2:x2s)] = (x1:x1s) `f` (foldr f g [(x2:x2s)]) = f (x1:x1s) (foldr f g [(x2:x2s)]) = \rest - x1 : (foldr f g [(x2:x2s)]) (rest . (x1s:)) h xss id = x1 : (foldr f g [(x2:x2s)]) (id . (x1s:)) demanding the next element will compute... = x1 : (f (x2:x2s) (foldr f g []) (id . (x1s:)) = x1 : (\rest - x2 : (foldr f g []) (rest . (x2s:))) (id . (x1s:)) = x1 : x2 : (foldr f g []) (id . (x1s:) . (x2s:)) demanding the next element will compute... = x1 : x2 : g (id . (x1s:) . (x2s:)) = x1 : x2 : weavefgs ((id . (x1s:) . (x2s:)) []) = x1 : x2 : weavefgh [x1s,x2s] which now can been see to work as desired. The end of the foldr is g which calls weavefgh which, if there is still work, call h/foldr again. This is beginning to look scary :-) To enable your last optimization you can replace the last alternative of 'f' by: f (x:xs) g = \rest - x : g (\l - rest $ case xs of [] - [[]] xs - xs:l ) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Export Haskell Libraries
It seems that what you want is a standalone .a file that you can then link into other programs without any special options. In principle this should be possible: you just need to include .o files for the RTS and libraries, and fortunately we already have those (HSrts.o, HSbase.o etc.) because they're needed by GHCi. You won't need the -u options because the whole base package will be linked in anyway. I can't immediately think of a reason this wouldn't work, but I could be wrong... Cheers, Simon SevenThunders wrote: Duncan Coutts wrote: So it's easy if you link the system using ghc. If you want to link it all using gcc instead, yeah, that's a bit harder. You can see most of the flags ghc passes to gcc as they're just in the package configuration for the rts and base packages (ghc-pkg display rts / base). It should be fairly straightforward to generate a gnu linker script from all this that you could use with gcc when linking your whole system. By tucking the ghc flags away in a linker scrupt you will not terrify your fellow developers with all the odd -u flags. That was my first thought and in fact I did write such a script. The only problem is I'm afraid that the link stages for the software I have integrate to may be rather complex and I thought that maybe this would not be the best approach if there were order dependencies etc. But maybe it's not so bad. In the end I managed to capture all the dependencies in CMake so I'm hoping that will make it a little easier to do the final integration. As for the issue of cabal putting generated files in a directory other than the source tree, you can tell cabal exactly which directory to use, so it's not that non-portable to go grubbing around in it to find the .o files you need to link into the archive file. 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. Alternatively you could just let cabal build the .a file. It can include externally generated .o files into the archive. Alternatively you can just use two .a files, keeping your other .o's in a separate file. Or you could even combine the two archives together as a later build step. Yes, this would be an attractive approach I think. Is it a matter of passing the correct flags to ghc, Ghc-options: -? At first glance, looking at the basic tutorial it seemed like to build a library one uses a line like Exposed Modules: A B C However I thought this would build Haskell only libraries.Then there is the business of merging libraries, which I suppose is done with ar and ranlib by extracting all the object files from one library and then adding them back in to the other. If it had to portable to windows as well I wonder if this would work. Actually it's not too bad if you ignore all the 50 -u flags. Apart from that, the single runtime library you want is just three: HSbase, HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp, dl and rt. running ghc -v for all my haskell code forced me to link to these libraries ultimately: HShaskell98 HSregex-compat HSregex-posix HSregex-base HSparsec HSbase HSbase_cbits HSrts m gmp dl rt There is a project for this year's Google Summer of Code to use dynamic libraries on Linux. Perhaps this would make the situation better for you since dynamic libs record their own dependencies much better. Ideally you would only have to link to your own Haskell package built as a .so and that would pull in the dependencies on HSbase.so, HSrts.so and the other system libs. Duncan Then it would be very similar to the windows build steps and probably a bit easier since one wouldn't have to mess with dlltools and converting libraries to ms vc formats etc. Really all that's needed though is a tool that can automagically wrap a homegrown static or even dynamic library that contains the needed components of the GHC run time library along with the additional user code. I know all the object files are available as are of course the libraries themselves, so such a script is not impossible. It seems that ghc itself is doing some kind of dependency analysis to determine the final call to gcc. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Translating perl - haskell, string fill ins with an error on invalid input seems awfully complex. Is there a way to simplify?
Answering my own plea for help, I now have the following, which seems neater to me. company_to_companyfile = [(ibm,data/ibm.dat),(cisco,data/cisco.dat)] displaymode_to_modestring = [(points, using 1:2 with linespoints), (candles,using 1:($2+$3+$4+$5)/4:4:3 with yerrorbars)] displaymode_to_titleend = [(points,daily prices),(candles,opening prices)] financial_output_wrapper :: String - String - String - String - IO () financial_output_wrapper company displaymode startDate endDate = do let maybeCompanyFile = lookup company company_to_companyfile case maybeCompanyFile of Nothing - error $ no company file for ++ company _ - return () let maybeModeString = lookup displaymode displaymode_to_modestring case maybeModeString of Nothing - error $ no mode string for ++ displaymode _ - return () let maybeTitleEnd = lookup displaymode displaymode_to_titleend case maybeTitleEnd of Nothing - error $ no title end for ++ displaymode _ - return () let maybeScript = gen_gnuplot_financial_script company ( maybeCompanyFile ) ( maybeModeString ) ( maybeTitleEnd ) startDate endDate case maybeScript of Just script - putStrLn script _ - error $ bad script gen_gnuplot_financial_script :: String - Maybe String - Maybe String - Maybe String - String - String - Maybe String gen_gnuplot_financial_script company (Just companyfile ) ( Just modestring) ( Just titleEnd ) startDate endDate = Just $ gnuplot_timeseries_settings ++ \n ++ plot [\ ++ startDate ++ \:\ ++ endDate ++ \] ++ ' ++ companyfile ++ ' ++ modestring ++ title \ ++ company ++ ++ titleEnd ++ \ 2007/4/12, Thomas Hartman [EMAIL PROTECTED]: I was translating some perl code to haskell as a learning exercise and wound up with the following. (below) Simple code that accepts some string arguments, and prints a string -- so, of type String - String - String - String - IO (). I like to be concise, but I get the feeling something went awry. What seems to be costing me the most is checking whether the various arguments are legitimate, and printing a helpful error message if not. I was able to achieve this by using Maybe and error on failed pattern match, but as said, seems kind of overly complicated. Is there a simpler way to do the following, eg for function gen_gnuplot_financial_script :: String - String - String - String - IO () ? By the way this is being used in http://code.google.com/p/gnuplotwebinterface/ ** module Common where gnuplot_png_settings = set terminal png transparent nocrop enhanced size 600,400\n ++ set pm3d implicit at s gnuplot_math_settings = gnuplot_png_settings ++ \n ++ set border 4095 \n\ \ set xlabel \x\ \n\ \ set ylabel \y\ gnuplot_timeseries_settings = gnuplot_png_settings ++ \n ++ set xdata time # The x axis data is time \n ++ set timefmt \%d-%b-%y\ # The dates in the file look like 10-Jun-04 \n ++ set format x \%b %d\ #On the x-axis, we want tics like Jun 10 gen_gnuplot_math_script :: String - String - IO () gen_gnuplot_math_script style function = let maybePlotCmd = lookup style style_to_plotcmd style_to_plotcmd = [(math-2d,plot),(math-3d,splot)] in case maybePlotCmd of Just plotcmd - putStrLn $ gnuplot_math_settings ++ \n ++ plotcmd ++++ function _- error $ bad style: ++ style gen_gnuplot_financial_script :: String - String - String - String - IO () gen_gnuplot_financial_script company displaymode startDate endDate = let maybeCompanyFile = lookup company company_to_companyfile maybeModeString = lookup displaymode displaymode_to_modestring maybeTitleEnd= lookup displaymode displaymode_to_titleend company_to_companyfile = [(ibm,data/ibm.dat),(cisco,data/cisco.dat)] displaymode_to_modestring = [(points, using 1:2 with linespoints), (candles,using 1:($2+$3+$4+$5)/4:4:3 with yerrorbars)] displaymode_to_titleend = [(points,daily prices),(candles,opening prices)] in case ( maybeCompanyFile, maybeModeString, maybeTitleEnd ) of ( Just companyfile, Just modestring,
Re: [Haskell-cafe] k-minima in Haskell
Hello, My Hugs tells me this: Prelude let sort [] = []; sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l in sort [1,3,2] [1,3,2] Prelude So, no, this is not a working sorting function. Inserting the few missing recursive calls: Prelude let sort [] = []; sort l@(x:_) = sort ( filter (x) l ) ++ filter (==x) l ++ sort ( filter (x) l ) in sort [1,3,2] [1,2,3] Prelude Best regards Thorkil On Friday 13 April 2007 11:38, Thomas Hartman wrote: And for reference, here is again stefan's stable quicksort from his earlier post. sort [] = [] sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l (A stable quicksort, btw) This is the code whose legitimacy I am requesting confirmation of. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: You may be missing a few recursive calls there :-) Indeed. ... ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Translating perl - haskell, string fill ins with an error on invalid input seems awfully complex. Is there a way to simplify?
And this mess can be simplified further by something like financial_output_wrapper company displaymode startDate endDate = do let maybeCompanyFile = lookup company company_to_companyfile validate_arg company company maybeCompanyFile validate_arg argname arg maybeTransformedArg = case maybeTransformedArg of Nothing - error $ no transformed ++ argname ++ arg for ++ arg _ - return () Summary: I like being able to check the validity of user input on an arg-by-arg basis, and now I guess I can. 2007/4/13, Thomas Hartman [EMAIL PROTECTED]: Answering my own plea for help, I now have the following, which seems neater to me. company_to_companyfile = [(ibm,data/ibm.dat),(cisco,data/cisco.dat)] displaymode_to_modestring = [(points, using 1:2 with linespoints), (candles,using 1:($2+$3+$4+$5)/4:4:3 with yerrorbars)] displaymode_to_titleend = [(points,daily prices),(candles,opening prices)] financial_output_wrapper :: String - String - String - String - IO () financial_output_wrapper company displaymode startDate endDate = do let maybeCompanyFile = lookup company company_to_companyfile case maybeCompanyFile of Nothing - error $ no company file for ++ company _ - return () let maybeModeString = lookup displaymode displaymode_to_modestring case maybeModeString of Nothing - error $ no mode string for ++ displaymode _ - return () let maybeTitleEnd = lookup displaymode displaymode_to_titleend case maybeTitleEnd of Nothing - error $ no title end for ++ displaymode _ - return () let maybeScript = gen_gnuplot_financial_script company ( maybeCompanyFile ) ( maybeModeString ) ( maybeTitleEnd ) startDate endDate case maybeScript of Just script - putStrLn script _ - error $ bad script gen_gnuplot_financial_script :: String - Maybe String - Maybe String - Maybe String - String - String - Maybe String gen_gnuplot_financial_script company (Just companyfile ) ( Just modestring) ( Just titleEnd ) startDate endDate = Just $ gnuplot_timeseries_settings ++ \n ++ plot [\ ++ startDate ++ \:\ ++ endDate ++ \] ++ ' ++ companyfile ++ ' ++ modestring ++ title \ ++ company ++ ++ titleEnd ++ \ 2007/4/12, Thomas Hartman [EMAIL PROTECTED]: I was translating some perl code to haskell as a learning exercise and wound up with the following. (below) Simple code that accepts some string arguments, and prints a string -- so, of type String - String - String - String - IO (). I like to be concise, but I get the feeling something went awry. What seems to be costing me the most is checking whether the various arguments are legitimate, and printing a helpful error message if not. I was able to achieve this by using Maybe and error on failed pattern match, but as said, seems kind of overly complicated. Is there a simpler way to do the following, eg for function gen_gnuplot_financial_script :: String - String - String - String - IO () ? By the way this is being used in http://code.google.com/p/gnuplotwebinterface/ ** module Common where gnuplot_png_settings = set terminal png transparent nocrop enhanced size 600,400\n ++ set pm3d implicit at s gnuplot_math_settings = gnuplot_png_settings ++ \n ++ set border 4095 \n\ \ set xlabel \x\ \n\ \ set ylabel \y\ gnuplot_timeseries_settings = gnuplot_png_settings ++ \n ++ set xdata time # The x axis data is time \n ++ set timefmt \%d-%b-%y\ # The dates in the file look like 10-Jun-04 \n ++ set format x \%b %d\ #On the x-axis, we want tics like Jun 10 gen_gnuplot_math_script :: String - String - IO () gen_gnuplot_math_script style function = let maybePlotCmd = lookup style style_to_plotcmd style_to_plotcmd = [(math-2d,plot),(math-3d,splot)] in case maybePlotCmd of Just plotcmd - putStrLn $ gnuplot_math_settings ++ \n ++ plotcmd ++++ function _- error $ bad style: ++ style gen_gnuplot_financial_script :: String - String - String - String - IO () gen_gnuplot_financial_script company displaymode startDate endDate = let maybeCompanyFile = lookup company company_to_companyfile
Re: [Haskell-cafe] Re: Translating perl - haskell, string fill ins with an error on invalid inputseems awfully complex. Is there a way to simplify?
Answering my own plea for help, I now have the following, which seems neater to me. checking Maybes is best done in the Maybe Monad, or if you need specific error messages, using maybe. that, in turn can be abstracted out into a lookup with error message. once the checking is done in the wrapper, there is no need to repeat it in the generator. also, the interface to the generator is too wide for the small amount of extra functionality it provides, so it is probably best inlined, and there seems to be no need to commit to IO so early. i also tend to use [String], with a final unlines before output, but that is a matter of opinion, i guess. financial_output :: String - String - String - String - String financial_output company displaymode startDate endDate = financial_script where financial_script = gnuplot_timeseries_settings ++ \n ++ plot [\ ++ startDate ++ \:\ ++ endDate ++ \] ++ ' ++ companyFile ++ ' ++ modeString ++ title \ ++ company ++ ++ titleEnd ++ \ companyFile = lookupWith (error $ no company file for ++ company) company company_to_companyfile modeString = lookupWith (error $ no mode string for ++ displaymode) displaymode displaymode_to_modestring titleEnd= lookupWith (error $ no title end for ++ displaymode) displaymode displaymode_to_titleend lookupWith error key assocs = maybe error id $ lookup key assocs hth, claus ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
On Fri, Apr 13, 2007 at 07:32:20AM -0400, [EMAIL PROTECTED] wrote: Quoting Thomas Hartman [EMAIL PROTECTED]: Does that mean you can have the k minima in O(n) time, where n is length of list, which would seem to be an improvement? It's worth considering what the theoretical minimum is. 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). Hmm, is something wrong with the following?: Tuple each element with its position: O(n) Find kth smallest element in linear time, as per [1]: O(n) Filter list for elements = kth smallest: O(n) Sort filtered list by position: O(k log k) map snd to get the positions: O(k) Total: O(n + k log k) (the filter step will take care of elements with the same value as the kth smallest, as the filter is also comparing element positions when the values are the same). Thanks Ian [1] http://en.wikipedia.org/wiki/Selection_algorithm ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Export Haskell Libraries
While we're on the topic, does anyone know if there exists a similarly simple solution like the (last) section Using both Python Haskell with ctypes at http://wiki.python.org/moin/PythonVsHaskell that works on Linux to easily link Haskell libraries/functions into Python? Cheers, Jason On 4/13/07, Simon Marlow [EMAIL PROTECTED] wrote: It seems that what you want is a standalone .a file that you can then link into other programs without any special options. In principle this should be possible: you just need to include .o files for the RTS and libraries, and fortunately we already have those (HSrts.o, HSbase.o etc.) because they're needed by GHCi. You won't need the -u options because the whole base package will be linked in anyway. I can't immediately think of a reason this wouldn't work, but I could be wrong... Cheers, Simon SevenThunders wrote: Duncan Coutts wrote: So it's easy if you link the system using ghc. If you want to link it all using gcc instead, yeah, that's a bit harder. You can see most of the flags ghc passes to gcc as they're just in the package configuration for the rts and base packages (ghc-pkg display rts / base). It should be fairly straightforward to generate a gnu linker script from all this that you could use with gcc when linking your whole system. By tucking the ghc flags away in a linker scrupt you will not terrify your fellow developers with all the odd -u flags. That was my first thought and in fact I did write such a script. The only problem is I'm afraid that the link stages for the software I have integrate to may be rather complex and I thought that maybe this would not be the best approach if there were order dependencies etc. But maybe it's not so bad. In the end I managed to capture all the dependencies in CMake so I'm hoping that will make it a little easier to do the final integration. As for the issue of cabal putting generated files in a directory other than the source tree, you can tell cabal exactly which directory to use, so it's not that non-portable to go grubbing around in it to find the .o files you need to link into the archive file. 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. Alternatively you could just let cabal build the .a file. It can include externally generated .o files into the archive. Alternatively you can just use two .a files, keeping your other .o's in a separate file. Or you could even combine the two archives together as a later build step. Yes, this would be an attractive approach I think. Is it a matter of passing the correct flags to ghc, Ghc-options: -? At first glance, looking at the basic tutorial it seemed like to build a library one uses a line like Exposed Modules: A B C However I thought this would build Haskell only libraries.Then there is the business of merging libraries, which I suppose is done with ar and ranlib by extracting all the object files from one library and then adding them back in to the other. If it had to portable to windows as well I wonder if this would work. Actually it's not too bad if you ignore all the 50 -u flags. Apart from that, the single runtime library you want is just three: HSbase, HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp, dl and rt. running ghc -v for all my haskell code forced me to link to these libraries ultimately: HShaskell98 HSregex-compat HSregex-posix HSregex-base HSparsec HSbase HSbase_cbits HSrts m gmp dl rt There is a project for this year's Google Summer of Code to use dynamic libraries on Linux. Perhaps this would make the situation better for you since dynamic libs record their own dependencies much better. Ideally you would only have to link to your own Haskell package built as a .so and that would pull in the dependencies on HSbase.so, HSrts.so and the other system libs. Duncan Then it would be very similar to the windows build steps and probably a bit easier since one wouldn't have to mess with dlltools and converting libraries to ms vc formats etc. Really all that's needed though is a tool that can automagically wrap a homegrown static or even dynamic library that contains the needed components of the GHC run time library along with the additional user code. I know all the object files are available as are of course the libraries themselves, so such a script is not impossible. It seems that ghc itself is doing some kind of dependency analysis to determine the final call to gcc. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED]
Re: [Haskell-cafe] Weaving fun
On Apr 12, 2007, at 9:39 PM, Matthew Brecknell wrote: Jan-Willem Maessen: Interestingly, in this particular case what we obtain is isomorphic to constructing and reversing a list. Jan-Willem's observation also hints at some interesting performance characteristics of difference lists. It's well known that difference lists give O(1) concatenation, but I haven't seen much discussion of the cost of conversion to ordinary lists. Nice analysis, thanks to both of you. I think a lot of this folklore isn't widely understood, particularly the fact that the closures constructed by difference lists are isomorphic to trees, with nodes corresponding to append/compose and leaves corresponding to empty/ singleton. So you pay the cost for append each time you flatten---the difference list trick is only a win if you flatten to an ordinary list once and/ or consume the entire list each time you flatten it. I'd had an intuitive notion of how this worked, but this spells it out nicely. Of course, once you represent things like so: data DiffList a = Segment [a] | DiffList a :++ DiffList a toList :: DiffList a - [a] toList dl = toListApp dl [] toListApp :: DiffList a - [a] - [a] toListApp (Segment s) = (s++) toListApp (a:++b) = toListApp a . toListApp b You can start thinking about all sorts of other interesting questions, beyond just transforming to a list and eta-abstracting toListApp. The next thing you know, you're writing a better pretty printer or otherwise mucking about with the DiffList type itself to tailor it for your own nefarious purposes. -Jan smime.p7s Description: S/MIME cryptographic signature ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
On 4/13/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Hello everybody, I would like to start a discussion on how to generate best-practice Haskell code from a model, e.g. from EMF. I started learning Haskell precisely to solve problems like this. But, once I got into it, I realized that Haskell is a much better modeling language than the modeling language I was using (MOF/UML, the predecessors to EMF). Furthermore, all the infrastructure built on top of that modeling language was very easy to replace with Haskell code. As a result, I gave up that effort. You said The benefits of the model+generate approach are well known, however I disagree. W3C DOM, MOF, UML, CORBA, and NetBeans 3.x-4.x are all obvious examples of the failure of the model+generate approach. If the modeling language is sufficiently powerful, then it should be feasible to execute the models directly using a (custom-built) interpreter. If the modeling language is weak then it is better to just do the modeling in Haskell or another more powerful language. The MDA idea was that you would have one model and then be able to use that model in a variety of different programming languages, without having to rewrite code in each target language. Now, people are getting this benefit via a code, then translate approach. For example, GWT allows the developer to write Java code, then generate the equivalent Javascript, without any hand-wavy models in between. JRuby lets one write code in Ruby to be used by code in Java; IronPython does the same for other .NET languages. In fact, C# is basically the .NET counterpart to EMF. FWIW, I also think that data based languages like ERD, Relax NG, and XQuery/XPath/XML Schema are a much closer fit to Haskell than EMF. EMF is designed to be translated any object-oriented, class-based, (soley) subtype-polymorphic, single-dispatched, single-inheritance language; i.e. Java. In fact, EMF is really a Java-optimized subset of what was supposed to become part of MOF 2.0. - Brian ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] implementing try for RWST ?
Hello, I defined a newtype like this (the ()s will be replace with something more useful in the future): newtype DryRunIO a = DryRunIO { runDryRunIO :: RWST Bool () () IO a } deriving (Monad, MonadIO, MonadError IOError, MonadFix, Functor, MonadReader Bool, MonadWriter (), MonadState ()) run :: Bool - DryRunIO a - IO a run dryRun action = (runRWST (runDryRunIO action)) dryRun () = \ (a, _, _) - return a and I want to define a function similar to |try| like this: tryDR :: DryRunIO a - DryRunIO (Either IOError a) tryDR m = catchError (m = return . Right) (return . Left) unfortunately, when I use it, it does not work the way I want: *Main run False (tryDR (error cheese)) *** Exception: cheese This is because 'error' raises an |Exception|, not a |IOError|. I would like to instead define tryDR to deal with exceptions: newtype DryRunIO a = DryRunIO { runDryRunIO :: RWST Bool () () IO a } deriving (Monad, MonadIO, MonadError Exception, MonadFix, Functor, MonadReader Bool, MonadWriter (), MonadState ()) tryDR :: DryRunIO a - DryRunIO (Either Exception a) tryDR m = catchError (m = return . Right) (return . Left) But to do this, I need an different instance of MonadError for IO, namely: instance MonadError Exception IO where throwError = throwIO catchError = catch -- (from Control.Exception) However, if I add that to my module I get this error: Functional dependencies conflict between instance declarations: instance MonadError Exception IO -- Defined at /tmp/DR.hs:17:0 instance MonadError IOError IO -- Defined in Control.Monad.Error Where do I go from here? Also, what is the justificiation for the current default of IOError instead of the more general Exception? thanks! j. ps. As a hack I have implemented tryDR as: tryDR' :: DryRunIO a - DryRunIO (Either Exception a) tryDR' (DryRunIO m) = DryRunIO $ RWST $ \r s - catch (runRWST m r s = \(a, s, w) - return (Right a, s, w)) -- uses catch from Control.Exception (\e - runRWST (return $ Left e) r s) However, I think this is buggy, because changes to 's' and 'w' will be lost if 'm' raises an exception. For example in: tryDR' (io $ putStr hello updatePosition (length hello) error goodbye) The updatedPosition would reflect the position before the tryDR, but the cursor on the screen would be somewhere else. It is my hope that the earlier definition does not have this bug. ___ 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 awfully complex. Is there a way to simplify?
financial_script = gnuplot_timeseries_settings ++ \n ++ plot [\ ++ startDate ++ \:\ ++ endDate ++ \] ++ ' ++ companyFile ++ ' ++ modeString ++ title \ ++ company ++ ++ titleEnd ++ \ Also note the existence of Text.Printf if you like that style better. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A monad using IO, Reader, Writer, State and Error
Chris Kuklewicz schrieb: Martin Huschenbett wrote: 1) type MyMonad = ErrorT E (RWST R W S IO) 2) type MyMonad = RWST R W S (ErrorT E IO) So (1) gives (Left e,s,w) or (Right a,s,w) and (2) gives (Left e) or (Right (a,s,w)) Due to this fact i decided to use (1). If the operation fails and I get (Left e,s,w) what are the values of 's' and 'w'? Are they the state and the written things that were produced by the last successfull operation? Regards, Martin. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? 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*. Third, assume you already have a model, want to write the corresponding code yourself? 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? Best regards, Steffen 2007/4/13, Brian Smith [EMAIL PROTECTED]: On 4/13/07, Steffen Mazanek [EMAIL PROTECTED] wrote: Hello everybody, I would like to start a discussion on how to generate best-practice Haskell code from a model, e.g. from EMF. I started learning Haskell precisely to solve problems like this. But, once I got into it, I realized that Haskell is a much better modeling language than the modeling language I was using (MOF/UML, the predecessors to EMF). Furthermore, all the infrastructure built on top of that modeling language was very easy to replace with Haskell code. As a result, I gave up that effort. You said The benefits of the model+generate approach are well known, however I disagree. W3C DOM, MOF, UML, CORBA, and NetBeans 3.x-4.x are all obvious examples of the failure of the model+generate approach. If the modeling language is sufficiently powerful, then it should be feasible to execute the models directly using a (custom-built) interpreter. If the modeling language is weak then it is better to just do the modeling in Haskell or another more powerful language. The MDA idea was that you would have one model and then be able to use that model in a variety of different programming languages, without having to rewrite code in each target language. Now, people are getting this benefit via a code, then translate approach. For example, GWT allows the developer to write Java code, then generate the equivalent Javascript, without any hand-wavy models in between. JRuby lets one write code in Ruby to be used by code in Java; IronPython does the same for other .NET languages. In fact, C# is basically the .NET counterpart to EMF. FWIW, I also think that data based languages like ERD, Relax NG, and XQuery/XPath/XML Schema are a much closer fit to Haskell than EMF. EMF is designed to be translated any object-oriented, class-based, (soley) subtype-polymorphic, single-dispatched, single-inheritance language; i.e. Java. In fact, EMF is really a Java-optimized subset of what was supposed to become part of MOF 2.0. - Brian -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
On 4/13/07, Ian Lynagh [EMAIL PROTECTED] wrote: Tuple each element with its position: O(n) Find kth smallest element in linear time, as per [1]: O(n) Filter list for elements = kth smallest: O(n) Sort filtered list by position: O(k log k) map snd to get the positions: O(k) Total: O(n + k log k) [1] http://en.wikipedia.org/wiki/Selection_algorithm Inspired by the above, I thought I'd see about writing it. Note that attaching the indices prevents equal items from comparing equal. I didn't feel like writing the code for a special data type that ignored a second element for the purposes of comparisons; that just means replacing zip and map send. The user can add stability by selective use of reverse within the continuation functions. There should probably be strictness annotations somewhere, and calls to length should probably be accumulated in partition instead, but the idea should be sound (except for the likelihood of a bad pivot). partition cont _ [] lt eq gt = cont lt eq gt partition cont p (x:xs) lt eq gt = case x `compare` p of LT - partition cont p xs (x:lt) eq gt EQ - partition cont p xs lt (x:eq) gt GT - partition cont p xs lt eq (x:gt) qsort [] = [] qsort (x:xs) = partition qs' x xs [] [x] [] where qs' lt eq gt = qsort lt ++ (eq ++ qsort gt) findfirst _ [] = [] findfirst k (x:xs) = partition ff' x xs [] [x] [] where ff' lt eq gt = let { ll = length lt; lle = ll + length eq } in if k ll then findfirst k lt else if k lle then lt ++ eq ++ findfirst (k - lle) gt elselt ++ take (k - ll) eq getSmallest k = qsort . findfirst k getSmallestIndices k = map snd . getSmallest k . flip zip [0..] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Export Haskell Libraries
In the GHC docs: http://www.haskell.org/ghc/docs/6.4.1/html/users_guide/sec-ffi-ghc.html#using-own-main There can be multiple calls to hs_init(), but each one should be matched by one (and only one) call to hs_exit()[8]. What exactly happens with nested calls? Is there only one runtime created, with a simple counter to know which hs_exit should shut it down? If so, is there a way of having multiple interpreters open safely at the same time? Or does each hs_init() create a new separate concurrent runtime (the preferable alternative)? And what is the cost of creating and destructing the GHC runtime anyway? Can the Haskell interpreter be in a Linux shared-object library, so long as I make sure to call hs_init() after loading and hs_exit() before unloading it? My experiments so far show this working flawlessly, but I vaguely remember an e-mail thread saying GHC couldn't be linked in dynamically. Dan Simon Marlow wrote: It seems that what you want is a standalone .a file that you can then link into other programs without any special options. In principle this should be possible: you just need to include .o files for the RTS and libraries, and fortunately we already have those (HSrts.o, HSbase.o etc.) because they're needed by GHCi. You won't need the -u options because the whole base package will be linked in anyway. I can't immediately think of a reason this wouldn't work, but I could be wrong... Cheers, Simon SevenThunders wrote: Duncan Coutts wrote: So it's easy if you link the system using ghc. If you want to link it all using gcc instead, yeah, that's a bit harder. You can see most of the flags ghc passes to gcc as they're just in the package configuration for the rts and base packages (ghc-pkg display rts / base). It should be fairly straightforward to generate a gnu linker script from all this that you could use with gcc when linking your whole system. By tucking the ghc flags away in a linker scrupt you will not terrify your fellow developers with all the odd -u flags. That was my first thought and in fact I did write such a script. The only problem is I'm afraid that the link stages for the software I have integrate to may be rather complex and I thought that maybe this would not be the best approach if there were order dependencies etc. But maybe it's not so bad. In the end I managed to capture all the dependencies in CMake so I'm hoping that will make it a little easier to do the final integration. As for the issue of cabal putting generated files in a directory other than the source tree, you can tell cabal exactly which directory to use, so it's not that non-portable to go grubbing around in it to find the .o files you need to link into the archive file. 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. Alternatively you could just let cabal build the .a file. It can include externally generated .o files into the archive. Alternatively you can just use two .a files, keeping your other .o's in a separate file. Or you could even combine the two archives together as a later build step. Yes, this would be an attractive approach I think. Is it a matter of passing the correct flags to ghc, Ghc-options: -? At first glance, looking at the basic tutorial it seemed like to build a library one uses a line like Exposed Modules: A B C However I thought this would build Haskell only libraries.Then there is the business of merging libraries, which I suppose is done with ar and ranlib by extracting all the object files from one library and then adding them back in to the other. If it had to portable to windows as well I wonder if this would work. Actually it's not too bad if you ignore all the 50 -u flags. Apart from that, the single runtime library you want is just three: HSbase, HSbase_cbits and HSrts. Those also depend on some system C libs: m, gmp, dl and rt. running ghc -v for all my haskell code forced me to link to these libraries ultimately: HShaskell98 HSregex-compat HSregex-posix HSregex-base HSparsec HSbase HSbase_cbits HSrts m gmp dl rt There is a project for this year's Google Summer of Code to use dynamic libraries on Linux. Perhaps this would make the situation better for you since dynamic libs record their own dependencies much better. Ideally you would only have to link to your own Haskell package built as a .so and that would pull in the dependencies on HSbase.so, HSrts.so and the other system libs. Duncan Then it would be very similar to the windows build steps and probably a bit easier since one wouldn't have to mess with dlltools and converting libraries to ms vc formats etc. Really all that's needed though is a tool that can automagically wrap a homegrown static or even dynamic library that
Re: [Haskell-cafe] Re: Export Haskell Libraries
jasonm wrote: While we're on the topic, does anyone know if there exists a similarly simple solution like the (last) section Using both Python Haskell with ctypes at http://wiki.python.org/moin/PythonVsHaskell that works on Linux to easily link Haskell libraries/functions into Python? Cheers, Jason Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe What I would do is go through the 'usual' export process of exporting Haskell to C. You could use the ***_stub.h files that are produced, but it's usually a bit easier to make your own .h files. After this use swig to wrap the C callable result into Python. A lot of the build tools seem to support SWIG these days. I know that CMake does and probably SCONS does to. What would be nice would be just a touch more automation to handle this. Maybe we can write some Haskell code to script up the process of linking together the correct object files for export on the Haskell side. Or perhaps it suffices to automate it within CMake or SCONS or provide macros or python scripts to do the same. -- View this message in context: http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9984796 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Hi Just to say, I agree with Brian totally! I've been (violently and forcefully) exposed to MOF tools in the past, and at every turn my thought was the Haskell would be clearer, shorter and executable! Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? Can you give an example? Usually higher order functions, monads, laziness etc can combine to make the boilerplate minimal, if not invisible. This is exactly the kind of problem haskell-cafe will excel at. 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*. The UML is not executable, draw a pretty picture. No one knows UML, everyone knows pretty pictures - most people can guess at the meaning of UML because they know the meaning of pictures. As to reverse engineering a diagram from code, that always leads to ugly (and pointless) diagrams. Third, assume you already have a model, want to write the corresponding code yourself? If the model is executable, why do you want to write the code? Thank you very much for contributing to the discussion. Please assume, that you have to generate the code from a model. If the model is the code, then the tool cat can be used to generate the code from the model :-) Further assume, that you have no choice and are not allowed to discuss the sense of this approach :-) Ah, artificial technical limitations are unlikely to be something that people adhere too :) If you can generate Java code from a model, why on earth would you then want to generate Haskell code from it? I see know reason to use the assembly language called Haskell vs the assembly language called Java - since if you are compiling a model to anything, it is just serving as an assembly language. Thanks Neil PS. Apologies - I got a 3rd in my degree module in meta-modelling - apparently giving alternative (better) solutions in Haskell does _not_ get bonus marks. This makes me not like meta-modelling very much. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Export Haskell Libraries
Dan Weston wrote: In the GHC docs: http://www.haskell.org/ghc/docs/6.4.1/html/users_guide/sec-ffi-ghc.html#using-own-main There can be multiple calls to hs_init(), but each one should be matched by one (and only one) call to hs_exit()[8]. What exactly happens with nested calls? Is there only one runtime created, with a simple counter to know which hs_exit should shut it down? If so, is there a way of having multiple interpreters open safely at the same time? Or does each hs_init() create a new separate concurrent runtime (the preferable alternative)? And what is the cost of creating and destructing the GHC runtime anyway? Can the Haskell interpreter be in a Linux shared-object library, so long as I make sure to call hs_init() after loading and hs_exit() before unloading it? My experiments so far show this working flawlessly, but I vaguely remember an e-mail thread saying GHC couldn't be linked in dynamically. Dan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe Thats a good question. I know that on windows multiple calls to loadLibrary end up returning memory to the same shared area, although different processes have their own data block (but still share the code block). Unfortunately the same process with different threads share the same data block, potentially causing issues if static memory gets altered. Thus it's up to the programmer to create and initialize any static memory that should be unique to a thread. Perhaps hs_init() does this, I do not know. -- View this message in context: http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9985245 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
Hi Neil, Just to say, I agree with Brian totally! I've been (violently and forcefully) exposed to MOF tools in the past, and at every turn my thought was the Haskell would be clearer, shorter and executable! This is true only for programming in the small, isn't it? Furthermore, from my point of view Haskell code is very clear if we talk about computations, in contrast the dependencies of data modelling are harder to overview. Humans just like pictures :) Not everybody is a hardcore Haskell hacker. Brian, but don't you think that you have to write a lot of boilerplate code in Haskell? Can you give an example? Usually higher order functions, monads, laziness etc can combine to make the boilerplate minimal, if not invisible. This is exactly the kind of problem haskell-cafe will excel at. I do not mean the code per se. I was talking more about structure, modules, comments, ... Haskell hackers have invented a lot of cool stuff to make their life easier, however this stuff often is complicated to understand :-) or not standard compliant. If you can generate Java code from a model, why on earth would you then want to generate Haskell code from it? I see know reason to use the assembly language called Haskell vs the assembly language called Java - since if you are compiling a model to anything, it is just serving as an assembly language. Hmph, how to disprove this argument? Say, you have generated ddl-code from an ER-model and now want to generate Haskell data structures that operate on this data. How would you procede? This is similar to HaXML that helped you to generate Haskell types for an xml schema. Best regards, Steffen -- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
On 4/13/07, Neil Mitchell [EMAIL PROTECTED] wrote: 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*. The UML is not executable, draw a pretty picture. No one knows UML, everyone knows pretty pictures - most people can guess at the meaning of UML because they know the meaning of pictures. As to reverse engineering a diagram from code, that always leads to ugly (and pointless) diagrams. Speaking of pretty pictures, there's a tool from Business Objects called Gems, which is based on a lazily evaluated, strictly-typed language called CAL, with many similarities to Haskell From http://labs.businessobjects.com/cal/default.asp These pieces of business logic, which we called Gems to give them a nice friendly face, are declarative 'functional' objects. Although unrelated to UML, it provides a nice way of graphically representing functions, check it out: http://resources.businessobjects.com/labs/cal/gem_cutter_manual.pdf Or, if you prefer a (boring) video: http://resources.businessobjects.com/labs/cal/gem_part_1_mov.zip I haven't put much thought on that, but I think it's possible representing (de-sugared) Haskell functions using GraphML and relying on existing renderers for simplicity ... anyone tried that already ? -- Ricardo Guimarães Herrmann You never change things by fighting the existing reality. To change something, build a new model that makes the existing model obsolete - R. Buckminster Fuller ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Partial parsers in Happy
Hi! I'm trying to use a partial monadic parser with Happy (using %partial %monad and %lexer). The problem is that the parser function always seems to eat up one token beyond the matched sequence regardless of what I do. So I can't, for instance, call the parser multiple times to parse a series of blocks, because after the first block is done, it misses the first token of the second block. I'm sure this has to have come up for someone before, but I've been unable to find any references. JCAB ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] multithreading speedup
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 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 I know that the threads really calculate what I want, and as soon as they are finished I get the result. The problem is that I have no speed up, the time is basically the sum of the time for the two threads. I thought that ghc now would take advantage of the two cpus if I compiled with -threaded. Am I wrong, do I need some special flag, a newer version of the compiler (I have 6.6.20070129), or it is just normal? Thanks Fawzi ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multithreading speedup
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 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 I know that the threads really calculate what I want, and as soon as they are finished I get the result. The problem is that I have no speed up, the time is basically the sum of the time for the two threads. I thought that ghc now would take advantage of the two cpus if I compiled with -threaded. Am I wrong, do I need some special flag, a newer version of the compiler (I have 6.6.20070129), or it is just normal? ./MyProgram +RTS -N2 where N is your CPU count. (that said, DO NOT USE THREADS IF AT ALL POSSIBLE, they are ugly and cause heisenbugs, if you want paralelism `par` from Control.Parallel is to be preferred if at all possible since it is deterministic) Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial parsers in Happy
More info: I managed to do a hack that works around it, but it is clearly not acceptable. Part of the Haskell code generated by Happy contains this: --- -- Accepting the parse -- If the current token is 0#, it means we've just accepted a partial -- parse (a %partial parser). We must ignore the saved token on the top of -- the stack in this case. happyAccept 0# tk st sts (_ `HappyStk` ans `HappyStk` _) = happyReturn1 ans happyAccept j tk st sts (HappyStk ans _) = (happyTcHack j (happyTcHack st)) (happyReturn1 ans) That looked suspect. There's a tk parameter that is summarily ignored! So I started mucking with it. I added a new action to recover a token by storing it in the monad's state, so that the lexer function can provide it again, and used it in there: --- -- Accepting the parse -- If the current token is 0#, it means we've just accepted a partial -- parse (a %partial parser). We must ignore the saved token on the top of -- the stack in this case. happyAccept 0# tk st sts (_ `HappyStk` ans `HappyStk` _) = recoverToken tk happyReturn1 ans -- Modification!!! happyAccept j tk st sts (HappyStk ans _) = (happyTcHack j (happyTcHack st)) (happyReturn1 ans) With that modification, everything seems to work correctly (yay!) It is insufficient, though, because this code is generated by Happy, so I'd need to change it by hand every time. The fact that this parameter is there seems to indicate that it might sometimes get used for some purpose, so maybe there's a better way? JCAB On Fri, 13 Apr 2007 15:23:14 -0700, Juan Carlos Arevalo Baeza [EMAIL PROTECTED] wrote: Hi! I'm trying to use a partial monadic parser with Happy (using %partial %monad and %lexer). The problem is that the parser function always seems to eat up one token beyond the matched sequence regardless of what I do. So I can't, for instance, call the parser multiple times to parse a series of blocks, because after the first block is done, it misses the first token of the second block. I'm sure this has to have come up for someone before, but I've been unable to find any references. JCAB ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] generate Haskell code from model
This is true only for programming in the small, isn't it? my favourite opinion on that subject was expressed, back in 1984, in Burstall, Lampson A kernel language for modules and abstract data types http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-1.html paraphrasing: programming-in-the-large should look pretty much like programming-in-the-small. what you need is a simple notation 'for dealing with big objects (pieces of a program) as if they were small ones (numbers); this is the basic good trick in matrix algebra'. meta-mudelling is a popular subject (and my tendency towards puns is not to be construed as a criticism - i like going meta if i can do so without going crazy;-), but the pragmatic focus is on the models, isn't it? try not to think of a modeling language for Haskell code. instead, think of Haskell itself as a meta-modelling language: first, you design a modelling language suitable for the problem at hand, then you make that modelling language precise and executable by prototyping it as an embedded domain-specific language in Haskell, then you model your problem in that modelling language. finally, you run your model. sometimes, you are done at this point. sometimes, you will need many more models, more efficiently implemented, so it makes sense to move from the prototypical implementation of your modelling language to an efficiency-oriented one (perhaps by turning an embedded interpreter into an embedded compiler and runtime system). sometimes, you only needed that one model, but you need it faster, and in a different language, to fit into some external constraints, so you either make your embedded compiler generate code in that language, or you re-implement by hand once you know that your model does what you want. of these, only the last alternative is not in line with model-driven development, in its code-and-model-are-linked-by-tools incarnation. if you need to model parsers, you start with a parser language, if you need to model other grammar-based problems, such as type systems or operational semantics, you generalise to monadic combinators, if you need to model financial contracts, you start with a contract language, if you need to model animation, you start with an animation language, if you need to model graphical representations of data-flow, you start by embedding Petri nets, and so on.. it is up to you to find and define the right modelling language for your problem/ domain/audience/customers/bosses/.., but Haskell provides good abstractions to build on, and -not to be underestimated- a common framework (or meta language) in which several such modelling languages can be combined. the latter not only means that abstractions common to different modelling languages can be extracted into libraries, and studied in general (such as monads and monad transformers), it also means that your model of a grammar can be integrated with your model of an execution mechanism, which in turn can be linked with your visual model of static and dynamic properties of your systems. in other words, you can model complex systems in a single framework, while still getting to choose the most appropriate language for modelling each part of your system. Hmph, how to disprove this argument? Say, you have generated ddl-code from an ER-model and now want to generate Haskell data structures that operate on this data. How would you procede? This is similar to HaXML that helped you to generate Haskell types for an xml schema. provided that the modelling language is defined precisely, you can write a compiler for it in Haskell (Haskell is good for writing compilers, remember?-). such a compiler could generate Haskell code, or tools, or data types, or.., or even Java code. rumour has it that it could even be used to reverse engineer and process Cobold, if necessary;-) (the xml example -is that xml schemata or dtds, btw?- demonstrates that precise definitions don't necessarily make for concise code, but thats what you get with standards..) claus which reminds me that so far there have been only two times i found myself agreeing with anything umlish: a paper by Harel explaining his ideas about statecharts, and a workshop of umlers i stumbled into, where it became clear to me that those pragmatic users of uml mainly use the graphics to depict their type hierarchies, while tending to ignore the advanced, complicated, and not necessarily well-defined aspects of uml. ___ 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 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 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 I know that the threads really calculate what I want, and as soon as they are finished I get the result. The problem is that I have no speed up, the time is basically the sum of the time for the two threads. I thought that ghc now would take advantage of the two cpus if I compiled with -threaded. Am I wrong, do I need some special flag, a newer version of the compiler (I have 6.6.20070129), or it is just normal? ./MyProgram +RTS -N2 where N is your CPU count. thanks, that was it. (that said, DO NOT USE THREADS IF AT ALL POSSIBLE, they are ugly and cause heisenbugs, if you want paralelism `par` from Control.Parallel is to be preferred if at all possible since it is deterministic) in theory yes, but I am quite used to programm with threads and even mpi. I have looked at Control.Parallel (and the nice article on it), but there is no easy way tell (at least that I saw) to leave the whole calculation to a sub thread. 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 3.14user 0.02system 0:01.68elapsed 187%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1041minor)pagefaults 0swaps 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. I had looked at strategies, but I need first a breath first traversal of a graph generated on the fly (to be parallel) and then a depth first traversal (to avoid space leaks), and I found no easy way to do it with strategies, so I did it by hand. 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)? Fawzi ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] multithreading speedup
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. 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! 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 I know that the threads really calculate what I want, and as soon as they are finished I get the result. The problem is that I have no speed up, the time is basically the sum of the time for the two threads. I thought that ghc now would take advantage of the two cpus if I compiled with -threaded. Am I wrong, do I need some special flag, a newer version of the compiler (I have 6.6.20070129), or it is just normal? ./MyProgram +RTS -N2 where N is your CPU count. thanks, that was it. (that said, DO NOT USE THREADS IF AT ALL POSSIBLE, they are ugly and cause heisenbugs, if you want paralelism `par` from Control.Parallel is to be preferred if at all possible since it is deterministic) in theory yes, but I am quite used to programm with threads and even mpi. I have looked at Control.Parallel (and the nice article on it), but there is no easy way tell (at least that I saw) to leave the whole calculation to a sub thread. 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 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 :) 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. I had looked at strategies, but I need first a breath first traversal of a graph generated on the fly (to be parallel) and then a depth first traversal (to avoid space leaks), and I found no easy way to do it with strategies, so I did it by hand. 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)? Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Type checking with Haskell
Stefan O'Rear wrote: On Thu, Apr 12, 2007 at 01:04:13PM +0100, Joel Reymont wrote: Folks, The ghc/compiler/typecheck directory holds a rather large body of code and quick browsing through did not produce any insight. How do you implement type checking in haskell? Assume I have an Expr type with a constructor per type and functions can take lists of expressions. Do I create a function taking an Expr, pattern-matching on appropriate constructor and returning True on a match and False otherwise? The Glasgow Haskell typechecker is big not because type checking is hard, but because GHC Haskell is a very big language. Also, GHC runs typechecking *before* desugaring, apparently thinking error messages are more important than programmer sanity :) A typechecker for a simpler language can be implemented quite easily: --- Simply typed lambda calculus data Typ = Int | Real | Bool | Fn Typ Typ data Exp = Lam Typ Exp | Var Int | App Exp Exp typeCheck' :: [Typ] - Exp - Maybe Typ typeCheck' cx (Lam ty bd) = fmap (Fn ty) (typeCheck' (ty:cx) bd) typeCheck' cx (Var i) = Just (cx !! i) typeCheck' cx (App fn vl) = do Fn at rt - typeCheck' cx fn pt - typeCheck' cx vl guard (at == pt) return rt Your problem, as I understand it, is even simpler than most since there are no higher order functions and no arguments. --- data Typ = Real | Int | Bool | String tc2 a b ta tb tr | typeCheck a == ta typeCheck b == tb = Just tr | otherwise = Nothing typeCheck :: Exp - Maybe Typ typeCheck (IAdd a b) = tc2 a b Int Int Int ... (That said, it would probably be better to fuse parsing and type checking in this case so that you do not need to track source positions.) Stefan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe Just for interest: Chapter 31 of Shriram Krishnamurthi's Programming Languages: Application and Interpretation has an interesting perspective on Haskell style polymorphism http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weaving fun
Jan-Willem Maessen wrote: On Apr 12, 2007, at 9:39 PM, Matthew Brecknell wrote: Jan-Willem Maessen: Interestingly, in this particular case what we obtain is isomorphic to constructing and reversing a list. Jan-Willem's observation also hints at some interesting performance characteristics of difference lists. It's well known that difference lists give O(1) concatenation, but I haven't seen much discussion of the cost of conversion to ordinary lists. Nice analysis, thanks to both of you. I think a lot of this folklore isn't widely understood, particularly the fact that the closures constructed by difference lists are isomorphic to trees, with nodes corresponding to append/compose and leaves corresponding to empty/singleton. So you pay the cost for append each time you flatten---the difference list trick is only a win if you flatten to an ordinary list once and/or consume the entire list each time you flatten it. I'd had an intuitive notion of how this worked, but this spells it out nicely. Of course, once you represent things like so: data DiffList a = Segment [a] | DiffList a :++ DiffList a toList :: DiffList a - [a] toList dl = toListApp dl [] toListApp :: DiffList a - [a] - [a] toListApp (Segment s) = (s++) toListApp (a:++b) = toListApp a . toListApp b You can start thinking about all sorts of other interesting questions, beyond just transforming to a list and eta-abstracting toListApp. The next thing you know, you're writing a better pretty printer or otherwise mucking about with the DiffList type itself to tailor it for your own nefarious purposes. -Jan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe And the relationship between them is de-/re-functionalization, Defunctionalization at Work (http://www.brics.dk/RS/01/23/) has some interesting applications of ideas along the line of Jan's. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe