Re: [Haskell-cafe] Is there good place to post Haskell alorithms/data structures that follow Steven Skiena's book on algorithm design and also Haskell code snippets that follow some of Knuth's books?
Hi Casey, Do you have these snippets already? If so, I can't wait to see them :) On Tue, Jun 22, 2010 at 4:42 AM, Twan van Laarhoven twa...@gmail.comwrote: Casey Hawthorne wrote: Is there good place to post Haskell alorithms/data structures that follow Steven Skiena's book on algorithm design and also Haskell code snippets that follow some of Knuth's books? These code snippets don't seem to fit with Hackage. You could make some pages for them on the Haskell wiki. If it is structured as a tutorial (which your suggestion of hatorial suggests), then you should add it to http://haskell.org/haskellwiki/Category:Tutorials Twan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Installing Haskell on OSX
Hi again, El mar, 22-06-2010 a las 13:36 +1200, Hamish Mackenzie escribió: On 22 Jun 2010, at 08:01, Giuseppe Luigi Punzi Ruiz wrote: uhmm.. Now, with all gtk2 rebuilded with +no_x11 and +quartz I get Linking dist/build/leksah/leksah ... ld: library not found for -lgtk-x11-2.0 collect2: ld returned 1 exit status cabal: Error: some packages failed to install: leksah-0.8.0.6 failed during the building phase. The exception was: ExitFailure 1 I searched, and it suppose libgtk-x11-2.0 is part of GTK2, but I only can found it in darwinports inside xulrunner package, but fails me a lot building. Some idea? I think something must still have been built against gtk x11. Did you rebuild all of Gtk2Hs after rebuilding Gtk? cabal install --reinstall glib cabal install --reinstall gio cabal install --reinstall cairo cabal install --reinstall pango cabal install --reinstall gtk cabal install --reinstall gtksourceview Oops..not. I will try at home.. If that does not fix it, you could try this to find the package at fault. grep gtk-x11 ~/.ghc/i386-darwin-6.12.1/package.conf.d/* I am interested to see how you get on with MacPorts. I have not tried it myself in a while. I built the current Leksah OS X binary with jhbuild... http://sourceforge.net/apps/trac/gtk-osx/wiki/Build I am sorry that the current binary is not compatible with OS X 10.5. I will try to use OS X 10.5 to build the next release to make sure it is compatible. Once you have Leksah working you will probably need to update the keymap file (~/.cabal/share/leksah-0.8.0.6/data/keymap.lkshk) if you want Command-C, V and X to work. Just uncomment the three lines already in there... ctrlx - EditCut ctrlc - EditCopy ctrlv - EditPaste You will probably find it beeps each time you use them. I have a nice fix for that but I think it requires a newer version of ige-mac-integration than the one in MacPorts. I will check all of this, thanks a lot. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] design question: decision tree from Programming Collective Intelligence
Hello Maybe permutation trees are a viable starting point? See the paper Parsing Permutation Phrases which appears to be on CiteSeer. Some slides are also here - the data type definitions and Functor instance for permutation trees are on page 18 (pdf index page 19): http://www.comlab.ox.ac.uk/jeremy.gibbons/wg21/meeting56/loeh-slides.pdf An alternative implementation for applicative functors is here: http://hackage.haskell.org/package/action-permutations Note the use of existentials here is pretty cunning, I didn't get very far the time I attempted to use the technique for my own purposes. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Different choice operations in a continuation monad
On Jun 19, 2010, at 1:48 PM, Heinrich Apfelmus wrote:
In my code, mzero is indeed an identity for orElse [...]
The observation is any action can be brought into one of the forms
mzero
return a `mplus` return b `mplus` ...
which corresponds to the list type [a] .
Ok that makes sense because the list types supports both a cancelling
`orElse` and a distributive `mplus` with identity `mzero`.
[...] you can implement your type as
newtype CMaybe a = CMaybe { forall b . (a - [b]) - [b] }
Yes. For me it was interesting to see how far we get by wrapping
`Maybe` in `Codensity`: we get more than `Maybe` but not as much as
`[]`.
Sebastian
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haddock Problem
malcolm.wallace malcolm.wallace at me.com writes: I haven't been following closely, but how did you install haddock? From a binary dist? Is it possible that one of the Windows binary dists has a baked-in location for something on the E: drive, which existed on the packager's machine but not on the final installed machine? We are on the Haskell Platform 2010.1.0.0 and haddock comes as a .exe with it. Does anyone have any suggestions or do I have to start building haddock myself? Thanks, Dominic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Continuations and coroutines
Paul Johnson wrote: Yves Parès wrote: It helps me understand better, but would you have some simple code that would do that ? http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps You can also understand coroutines and continuations in terms of operational semantics. Here is a reimplementation of Koen Claessen's poor man's concurrency monad based on this approach: PoorMansConcurrency.hs http://projects.haskell.org/operational/examples.html Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Different choice operations in a continuation monad
Sebastian Fischer wrote:
Heinrich Apfelmus wrote:
[...] you can implement your type as
newtype CMaybe a = CMaybe { forall b . (a - [b]) - [b] }
Yes. For me it was interesting to see how far we get by wrapping `Maybe`
in `Codensity`: we get more than `Maybe` but not as much as `[]`.
Well, you can implement it with Maybe as well, at the price of
duplicated computations. The idea is that for the implementation of
orElse , we're not interested in the full list of results, only in
whether this list is empty or not. This leads to
eval :: ProgramView Language a - Maybe a
eval (Return a := k) = Just a
eval (MZero := k) = Nothing
eval (MPlus n m := k) = (eval . view) (n = k)
`mplus` (eval . view) (m = k)
eval (OrElse n m := k) = case (eval . view) n of
Nothing - (eval . view) (m = k)
Just _ - (eval . view) (n = k)
Thanks to lazy evaluation, this is not too inefficient, even.
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Tiger compiler: variable escaping analysis phase
Hello. I have been teaching an introductory course on compiler construction to our undergraduates students using Appel's Modern Compiler Implementation in Java. There are also versions of the book in ML and C. The books explain how to write a compiler for the Tiger programming language. Now I want to implement a Tiger compiler in Haskell. The lexer and parser (built with the help of alex and happy) and the type checker are already working. Next step is implementing a variable escape analysis phase, needed for the intermediate code generator. The objective of this phase is to find out if each variable escapes or not. In general an escaping variable should be allocated in the stack frame (in memory). Non escaping variables may be allocated in the stack frame or in a register. Generally, a variable escapes if it is passed by reference, its address is taken (using C's operator, for instance), or it is accessed from a nested function. Only the last is possible with Tiger. The approach adopted by Appel in his books is easy: a muttable field in the abstract syntax of variable declarations, of for expressions, and of function formal parameters, which introduce new variables, is used to collect the escaping information of the variable. In the ML version of the book this is a reference to boolean (bool ref). Initially, in a conservative approach, the reference is initialized to true. In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. I am look for good ways to implement the variable escaping analysis phase in Haskell, which is a pure language. I see two alternatives: 1) adopt the same approach as Appel used in his ML version of the compiler: use a mutable reference in the IO monad (Data.IORef) to hold the variable escaping information, and write everything inside the IO monad 2) build a new abstract syntax tree with updated information regarding variable escaping The second option is more elegant in my point of view, but would be much less efficient than the first one. So I want to know what advices Haskell programmers has to me about implementing this phase of the Tiger compiler in Haskell. Regards, Romildo -- Computer Science Department Universidade Federal de Ouro Preto, Brazil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
2010/6/22 José Romildo Malaquias j.romi...@gmail.com: Hello. I have been teaching an introductory course on compiler construction to our undergraduates students using Appel's Modern Compiler Implementation in Java. There are also versions of the book in ML and C. The books explain how to write a compiler for the Tiger programming language. Now I want to implement a Tiger compiler in Haskell. The lexer and parser (built with the help of alex and happy) and the type checker are already working. Next step is implementing a variable escape analysis phase, needed for the intermediate code generator. The objective of this phase is to find out if each variable escapes or not. In general an escaping variable should be allocated in the stack frame (in memory). Non escaping variables may be allocated in the stack frame or in a register. Generally, a variable escapes if it is passed by reference, its address is taken (using C's operator, for instance), or it is accessed from a nested function. Only the last is possible with Tiger. The approach adopted by Appel in his books is easy: a muttable field in the abstract syntax of variable declarations, of for expressions, and of function formal parameters, which introduce new variables, is used to collect the escaping information of the variable. In the ML version of the book this is a reference to boolean (bool ref). Initially, in a conservative approach, the reference is initialized to true. In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. I am look for good ways to implement the variable escaping analysis phase in Haskell, which is a pure language. I see two alternatives: 1) adopt the same approach as Appel used in his ML version of the compiler: use a mutable reference in the IO monad (Data.IORef) to hold the variable escaping information, and write everything inside the IO monad 2) build a new abstract syntax tree with updated information regarding variable escaping The second option is more elegant in my point of view, but would be much less efficient than the first one. So I want to know what advices Haskell programmers has to me about implementing this phase of the Tiger compiler in Haskell. Hi, I think there is a third way to do what you describe (if I understood everything). You can use a Writer monad (basically a state monad where the state is never read, only written to). Essentially you walk the tree and record the information you want (a mapping from variable name to a boolean 'does-escape'). That information is threaded through the tree-walking functions. The information you record is the underlying monoid of the Writer monad. Anyway, the second option sounds better than the first one as you don't have to rely on IO (for which IMO there is no real reason in the problem you provide). Cheers, Thu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
On Tue, Jun 22, 2010 at 09:33:22AM -0300, José Romildo Malaquias wrote: In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. Idea of pure algorithm: 1) Update the symbol table itself, that is: instead of using (a) Map Symbol (IORef Bool) use (b) Map Symbol Bool. This doesn't change the complexity of the algorithm as searching and updating have the same complexity for many data structures (maps and hashtables, for example). In reality, you don't need to use a Map at all. Just use (c) Set Symbol and symbols not in the set do not escape. Using (a) gives you O(n log k) for this step, where n is the size of the AST and k is the number of symbols. On the other hand, (c) gives you O(n log e), where e is the number of escaping symbols. 2) After doing the whole analysis, use a function 'addEscapeInfo' to process the whole pure AST again adding information about escaped symbols. This is O(n log e) as well. The second option is more elegant in my point of view, but would be much less efficient than the first one. While O(n log e) is better than O(n log k), probably the constants in the pure algorithm are higher than their impure counterparts. I guess you could also try to write: 1) Take an 'AST e' into 'AST (STRef s Bool, e)' in O(n). 2) Use the impure algorithm inside ST monad in O(n log k). 3) Take 'AST (STRef s Bool, e)' into 'AST (Bool, e)' in O(n). 4) 'runST' on the above steps to get a pure function from 'AST e' into 'AST (Bool, e)'. The ST monad has the same runtime overhead as IO. Steps 1) and 3) are used to hide the ST monad from the rest of the compiler. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
Hello Doaitse Swierstra has a Tiger compiler written in Haskell + UUAG as a demonstration for UUAG attribute grammar system. The package on Hackage only contains the derived source - i.e not the original attribute grammar code, but the generated Haskell source after running UUAG on the *.ag files. http://hackage.haskell.org/package/tiger You could try contacting Doaitse Swierstra for the original UUAG source. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
On Tue, Jun 22, 2010 at 02:30:04PM +0100, Stephen Tetley wrote: Hello Doaitse Swierstra has a Tiger compiler written in Haskell + UUAG as a demonstration for UUAG attribute grammar system. The package on Hackage only contains the derived source - i.e not the original attribute grammar code, but the generated Haskell source after running UUAG on the *.ag files. http://hackage.haskell.org/package/tiger You could try contacting Doaitse Swierstra for the original UUAG source. I have found the sources at http://www.cs.uu.nl/wiki/HUT/WebHome. What is provided is an implementation of a compiler front-end and type checker for Andrew Appel's Tiger language. The variable escaping phase (needed only to decide where variables would be allocated in the back-end) is not implemented. At least I could not find it in a quick view. Romildo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
On Tue, Jun 22, 2010 at 02:54:08PM +0200, Vo Minh Thu wrote: 2010/6/22 José Romildo Malaquias j.romi...@gmail.com: Hello. I have been teaching an introductory course on compiler construction to our undergraduates students using Appel's Modern Compiler Implementation in Java. There are also versions of the book in ML and C. The books explain how to write a compiler for the Tiger programming language. Now I want to implement a Tiger compiler in Haskell. The lexer and parser (built with the help of alex and happy) and the type checker are already working. Next step is implementing a variable escape analysis phase, needed for the intermediate code generator. The objective of this phase is to find out if each variable escapes or not. In general an escaping variable should be allocated in the stack frame (in memory). Non escaping variables may be allocated in the stack frame or in a register. Generally, a variable escapes if it is passed by reference, its address is taken (using C's operator, for instance), or it is accessed from a nested function. Only the last is possible with Tiger. The approach adopted by Appel in his books is easy: a muttable field in the abstract syntax of variable declarations, of for expressions, and of function formal parameters, which introduce new variables, is used to collect the escaping information of the variable. In the ML version of the book this is a reference to boolean (bool ref). Initially, in a conservative approach, the reference is initialized to true. In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. I am look for good ways to implement the variable escaping analysis phase in Haskell, which is a pure language. I see two alternatives: 1) adopt the same approach as Appel used in his ML version of the compiler: use a mutable reference in the IO monad (Data.IORef) to hold the variable escaping information, and write everything inside the IO monad 2) build a new abstract syntax tree with updated information regarding variable escaping The second option is more elegant in my point of view, but would be much less efficient than the first one. So I want to know what advices Haskell programmers has to me about implementing this phase of the Tiger compiler in Haskell. Hi, I think there is a third way to do what you describe (if I understood everything). You can use a Writer monad (basically a state monad where the state is never read, only written to). Essentially you walk the tree and record the information you want (a mapping from variable name to a boolean 'does-escape'). That information is threaded through the tree-walking functions. The information you record is the underlying monoid of the Writer monad. The 'does-escape' information should be available for each variable at the point the variable is introduced (a variable declaration or a formal parameter in a function declaration, for instance). If this information is collected in another data structure that is not the abstract syntax tree, it may be difficult to access the 'does-escape' information when needed. In this line I thought about using a mapping from a pair consisting of the variable name and its position in the source code, to the 'does-escape' boolean. The findEscape function would construct this mapping while traversing the abstract syntax tree. The function that generates the intermediate representation of the program would be given the abstract syntax tree and the escaping mapping as arguments. When traversing the abstract syntax tree to generate code, it would consult the escaping mapping to determine if a varable escapes or not, when allocating a variable. The variable name and its position are available from the abstract syntax tree. Are you suggesting that the Writer monad would be used to construct a data structure like the escaping mapping I mentioned above? Anyway, the second option sounds better than the first one as you don't have to rely
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
2010/6/22 José Romildo Malaquias j.romi...@gmail.com: On Tue, Jun 22, 2010 at 02:54:08PM +0200, Vo Minh Thu wrote: 2010/6/22 José Romildo Malaquias j.romi...@gmail.com: Hello. I have been teaching an introductory course on compiler construction to our undergraduates students using Appel's Modern Compiler Implementation in Java. There are also versions of the book in ML and C. The books explain how to write a compiler for the Tiger programming language. Now I want to implement a Tiger compiler in Haskell. The lexer and parser (built with the help of alex and happy) and the type checker are already working. Next step is implementing a variable escape analysis phase, needed for the intermediate code generator. The objective of this phase is to find out if each variable escapes or not. In general an escaping variable should be allocated in the stack frame (in memory). Non escaping variables may be allocated in the stack frame or in a register. Generally, a variable escapes if it is passed by reference, its address is taken (using C's operator, for instance), or it is accessed from a nested function. Only the last is possible with Tiger. The approach adopted by Appel in his books is easy: a muttable field in the abstract syntax of variable declarations, of for expressions, and of function formal parameters, which introduce new variables, is used to collect the escaping information of the variable. In the ML version of the book this is a reference to boolean (bool ref). Initially, in a conservative approach, the reference is initialized to true. In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. I am look for good ways to implement the variable escaping analysis phase in Haskell, which is a pure language. I see two alternatives: 1) adopt the same approach as Appel used in his ML version of the compiler: use a mutable reference in the IO monad (Data.IORef) to hold the variable escaping information, and write everything inside the IO monad 2) build a new abstract syntax tree with updated information regarding variable escaping The second option is more elegant in my point of view, but would be much less efficient than the first one. So I want to know what advices Haskell programmers has to me about implementing this phase of the Tiger compiler in Haskell. Hi, I think there is a third way to do what you describe (if I understood everything). You can use a Writer monad (basically a state monad where the state is never read, only written to). Essentially you walk the tree and record the information you want (a mapping from variable name to a boolean 'does-escape'). That information is threaded through the tree-walking functions. The information you record is the underlying monoid of the Writer monad. The 'does-escape' information should be available for each variable at the point the variable is introduced (a variable declaration or a formal parameter in a function declaration, for instance). If this information is collected in another data structure that is not the abstract syntax tree, it may be difficult to access the 'does-escape' information when needed. I was thinking 'accessing when needed' was just a lookup into that other datastructure (i.e. a map). As someone said, and related to your second solution, this analysis and the resulting mapping can be put pack into the tree. I.e. instead of data Tree = ... you have data Tree a = ... and the 'a' can be whatever you want, including the 'does-escape' boolean value. In this line I thought about using a mapping from a pair consisting of the variable name and its position in the source code, to the 'does-escape' boolean. The findEscape function would construct this mapping while traversing the abstract syntax tree. Yes, that was what I had in mind. But don't use (variable name, position) to index the map. Instead have a renaming pass that ensure that every name is unique. The function that
Re: [Haskell-cafe] Tiger compiler: variable escaping analysis phase
On Tue, Jun 22, 2010 at 10:01:37AM -0300, Felipe Lessa wrote: On Tue, Jun 22, 2010 at 09:33:22AM -0300, José Romildo Malaquias wrote: In the variable escaping analysis phase of the compiler, a function findEscape looks for escaping variables and record this information in the escape fields of the abstract syntax. To do this the entire abstract syntax tree is traversed looking for escaping uses of every variable, and, when found, the field is set to true. findEscape uses a symbol table to accomplish its work, binding variable names to a reference to boolean (the same reference used in the abstract syntax tree). When processing a variable declaraction, for instance, it inserts the variable name into the symbol table, binding it to its escaping field. When processing an expression which is a simple variable, if the variable occurs in a nested function, its binding in the symbol table is set to true. This reflects directly in the abstract syntax tree of the variable declaration, as the escape field in the variable declaration and the binding in the symbol table are the same reference to bool. Idea of pure algorithm: 1) Update the symbol table itself, that is: instead of using (a) Map Symbol (IORef Bool) use (b) Map Symbol Bool. This doesn't change the complexity of the algorithm as searching and updating have the same complexity for many data structures (maps and hashtables, for example). In reality, you don't need to use a Map at all. Just use (c) Set Symbol and symbols not in the set do not escape. Using (a) gives you O(n log k) for this step, where n is the size of the AST and k is the number of symbols. On the other hand, (c) gives you O(n log e), where e is the number of escaping symbols. These solutions would not work because they do not deal with scopes of variables. In a Tiger program (as in most programming languges) a variable name can be reused many times to refer to different variables, and each variable can escape. Maybe a set of pairs containing the variable name and its position in the source code (available from the abstract syntax tree) would be a good idea. Then the code generator would traverse the abstract syntax tree and, when needed, use this set to find out whether a variable escapes. 2) After doing the whole analysis, use a function 'addEscapeInfo' to process the whole pure AST again adding information about escaped symbols. This is O(n log e) as well. If the variable escaping analysis is done and its result is made available in another data structure, there would be no need to add the escaping information back to the abstract syntax tree. The second option is more elegant in my point of view, but would be much less efficient than the first one. While O(n log e) is better than O(n log k), probably the constants in the pure algorithm are higher than their impure counterparts. I guess you could also try to write: 1) Take an 'AST e' into 'AST (STRef s Bool, e)' in O(n). 2) Use the impure algorithm inside ST monad in O(n log k). 3) Take 'AST (STRef s Bool, e)' into 'AST (Bool, e)' in O(n). 4) 'runST' on the above steps to get a pure function from 'AST e' into 'AST (Bool, e)'. The ST monad has the same runtime overhead as IO. Steps 1) and 3) are used to hide the ST monad from the rest of the compiler. Romildo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Inferring the most general type
Esteemed fellow haskellers, I recently ran into a very simple real life case where Haskell's rules for inferring the types for mutually recursive definitions resulted in a type that was less general than it could be. It took me a while to realize that the type error I was getting wasn't actually a problem with my code. I understand why Haskell does this (it infers the strongly connected mutually recursive definitions monomorphically), but I think it _could_ infer the more general type even with recursive definitions like this. Here is a simplified example that illustrates the problem: import Data.Maybe -- The fixed point datatype data Y f = Y (f (Y f)) -- silly dummy function maybeToInt :: Maybe a - Int maybeToInt = length . maybeToList -- f :: Y Maybe - Int f (Y x) = g maybeToInt x g h x = h $ fmap f x This is the type it wants to infer for g g :: (Maybe Int - Int) - Maybe (Y Maybe) - Int This is the type I think it should have, note you can't force the type with a typesig without -XRelaxedPolyRec g :: (Functor f) = (f Int - b) - f (Y Maybe) - b If I use -XRelaxedPolyRec I can manually specify the more general type, but then I have to convince myself that there isn't a more general type that I'm missing. Are there other known algorithms that yield a more general type? and if so, what was the rational for Haskell keeping the current method? I worked out an alternative algorithm that would give a more general type (perhaps the most general type) but it has factorial complexity and probably wouldn't be good for strongly connected groups with 7 or more members. Even so, I would much rather have the inferred types always be the most general ones and be required to add type signatures for mutually recursive groups with 7 or more members (which probably need to be redesigned anyway) than be always required to manually figure out the more general signatures. What do you think? - Job ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] TH instance code.
Hi all, I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: GWindowId) $ fromVariant x -- duplicate code end -- Any TH expert help? Thanks, -- Andy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TH instance code.
What you're looking for is something like: deriveVariable _t = [d| instance Variable $t where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: $t) $ fromVariant x|] deriveVariable (conT ''PageType) deriveVariable (conT ''Int) deriveVariable (conT ''Maybe `appT` conT ''Char) ... On Tue, Jun 22, 2010 at 11:24 AM, Andy Stewart lazycat.mana...@gmail.comwrote: Hi all, I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: GWindowId) $ fromVariant x -- duplicate code end -- Any TH expert help? Thanks, -- Andy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TH instance code.
v-- I had accidentally elided the _'s before the t's in the quasiquotation before. What you're looking for is something like: deriveVariable _t = [d| instance Variable $_t where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: $_t) $ fromVariant x|] deriveVariable (conT ''PageType) deriveVariable (conT ''Int) deriveVariable (conT ''Maybe `appT` conT ''Char) ... On Tue, Jun 22, 2010 at 11:24 AM, Andy Stewart lazycat.mana...@gmail.comwrote: Hi all, I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: GWindowId) $ fromVariant x -- duplicate code end -- Any TH expert help? Thanks, -- Andy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TH instance code.
On Tue, Jun 22, 2010 at 6:24 PM, Andy Stewart lazycat.mana...@gmail.comwrote: Hi all, I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: GWindowId) $ fromVariant x -- duplicate code end -- Any TH expert help? Thanks, -- Andy mkInstance :: Name - Q Dec mkInstance n = do tv - [|toVariant . show|] fv - [|fmap read . fromVariant|] return $ InstanceD [] (ConT ''Variable `AppT` ConT n) [ FunD (mkName toVariant) [Clause [] [NormalB tv] []] , FunD (mkName fromVariant) [Clause [] [NormalB fv] []] ] mkInstances = mapM mkInstance mkInstances [''PageType, ''Int, ..] Haven't tried it, but it should be pretty close. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TH instance code.
I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x If this isn't an exercise to learn TH, you might also want to try scoped type variables (7.8.7) to connect the 'read v' annotation to the instance head: http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/other-type-extensions.html#scoped-type-variables Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: bitspeak 0.0.1
John Meacham wrote: In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too. Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: srec-0.0.0
A little library for reading s-record files: http://hackage.haskell.org/package/srec -Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Minix
L.S., I just read about Minix and found a discussion [1] about Andrew Tanenbaum (the creator of Minix) wanting to try drivers written in Haskell on Minix. It has been four years since, is there currently a way to (cross)compile Haskell programs for Minix? Haskell well suited to write reliable software and Minix is all about reliability; they seem to match perfectly. It would increase visibility of Haskell if it can be used on Minix systems. Regards, Henk-Jan van Tuyl [1] http://groups.google.com/group/fa.haskell/browse_thread/thread/43f22847305b00ba?tvc=2 -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: ANN: bitspeak 0.0.1
On Mon, 21 Jun 2010, Maurício CA wrote: bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). There is a parallel between data compression algorithms and this sort of task, expressing a sentence in the minimal number of bits via compression also minimized the number of yes/no questions that need to be asked. In particular, a Huffman coding: Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen. http://www.inference.phy.cam.ac.uk/dasher/ Tony. -- f.anthony.n.finch d...@dotat.at http://dotat.at/ SOUTH BISCAY: EASTERLY OR NORTHEASTERLY 4 OR 5, OCCASIONALLY 6 IN SOUTHWEST. SLIGHT OR MODERATE. FAIR. GOOD.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Huffman Codes in Haskell
On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote: John Meacham wrote: In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too. Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing... Hmmm Do I hear a challenge? :) Actually, I can't find my huffman code at the moment, I would be curious what others take on the problem was. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
john: On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote: John Meacham wrote: In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too. Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing... Hmmm Do I hear a challenge? :) Actually, I can't find my huffman code at the moment, I would be curious what others take on the problem was. http://hackage.haskell.org/package/huffman A simple and pure Haskell implementation of the Huffman encoding algorithm. Google turns up a lot of results. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting a famous library and using the same name: pros and cons
On Tue, Jun 08, 2010 at 11:21:54AM -0700, Gregory Crosswhite wrote: Or you just put an upper bound on the versions of the fgl library that your program will build against, as you should be doing anyway, and then nothing breaks. Until some package you rely on decides to upgrade and start using fgl-6 internally without modifying its external API. Suddenly you are incompatible without a version number bump anywhere due to a completely non-local change. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
Don Stewart wrote: http://hackage.haskell.org/package/huffman A simple and pure Haskell implementation of the Huffman encoding algorithm. What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting a famous library and using the same name: pros and cons
The problem is that nothing breaks immediately. Then someone else comes along and transitively depends on your package and on another package, which depends on the newer version. Your users wind up with strange conflicts like that if they are using Parsec 3 they can't use HTTP. Or if they use fc-labels they can't use any library that internally uses mtl, because fc-labels uses transformers. Or worse they want to use a library that used fc-labels internally with another library that used mtl internally. It fragments the library base that you are able to use. Version caps are not the answer. -Edward Kmett On Tue, Jun 8, 2010 at 2:21 PM, Gregory Crosswhite gcr...@phys.washington.edu wrote: Or you just put an upper bound on the versions of the fgl library that your program will build against, as you should be doing anyway, and then nothing breaks. Cheers, Greg On Jun 8, 2010, at 11:08 AM, Gene A wrote: On Tue, Jun 8, 2010 at 8:08 AM, Don Stewart d...@galois.com wrote: (... There have been a few cases of major API / rewrites to famous old packages causing problems, including: * QuickCheck 1 vs 2 * parsec 2 vs 3 * OpenGL ...) (... * No additional breakages are introduced. ...) Oh lord yes... just call it fgl3 and leave the fgl package alone. This is a source based community here... so you take a package that has a dependency on another library and you go out and get that to cover the dependency and the API is not the same!!! AND especially if that might be the only thing you will ever use that lib for ... and you have to stop and rewrite the original.. and as someone else said with maybe documentation of that API that is not maybe finished or... NO ... At that point the person will probably just DISCARD the compile on the lib or program that had the dependency.. rather then put the effort in to learn an entire API that doesn't match up.. BAD IDEA!! cheers, gene ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Minix
On Tue, Jun 22, 2010 at 08:54:26PM +0200, Henk-Jan van Tuyl wrote: I just read about Minix and found a discussion [1] about Andrew Tanenbaum (the creator of Minix) wanting to try drivers written in Haskell on Minix. It has been four years since, is there currently a way to (cross)compile Haskell programs for Minix? I guess you should look at JHC, it shouldn't be a huge effort to port it to the Minix 3 OS. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Rewriting a famous library and using the same name: pros and cons
There is no reason that your program couldn't link to multiple versions of the same package so that each library can access the version that it needs. In fact, GHC already does this, doesn't it? For example, I use a mixture of libraries in my programs that link to QuickCheck 1 and QuickCheck 2, and this works just fine. The only problem I've had is with cabal, which when resolving dependencies seems to only be able to pick out one version of a package; in some cases instead of running cabal install A B where A and B depended on different versions of the same package (QuickCheck) I had to instead separately run cabal install A and cabal install B. This isn't a big deal, but I could imagine cases where it could fail to automatically install a package entirely due to conflicting version requirements. This, however, is not because there is an intrinsic problem with installing multiple versions of a library, but simply because cabal sometimes seems to get confused about what it needs to do. So in short, I see no problem with there being multiple versions of a package floating around, and to the extent that an implementation of something can't handle this it seems like this is arguably a bug in that implementation rather than a bug in the package system for allowing the possibility. Cheers, Greg On 6/22/10 4:06 PM, Edward Kmett wrote: The problem is that nothing breaks immediately. Then someone else comes along and transitively depends on your package and on another package, which depends on the newer version. Your users wind up with strange conflicts like that if they are using Parsec 3 they can't use HTTP. Or if they use fc-labels they can't use any library that internally uses mtl, because fc-labels uses transformers. Or worse they want to use a library that used fc-labels internally with another library that used mtl internally. It fragments the library base that you are able to use. Version caps are not the answer. -Edward Kmett On Tue, Jun 8, 2010 at 2:21 PM, Gregory Crosswhite gcr...@phys.washington.edu mailto:gcr...@phys.washington.edu wrote: Or you just put an upper bound on the versions of the fgl library that your program will build against, as you should be doing anyway, and then nothing breaks. Cheers, Greg On Jun 8, 2010, at 11:08 AM, Gene A wrote: On Tue, Jun 8, 2010 at 8:08 AM, Don Stewart d...@galois.com mailto:d...@galois.com wrote: (... There have been a few cases of major API / rewrites to famous old packages causing problems, including: * QuickCheck 1 vs 2 * parsec 2 vs 3 * OpenGL ...) (... * No additional breakages are introduced. ...) Oh lord yes... just call it fgl3 and leave the fgl package alone. This is a source based community here... so you take a package that has a dependency on another library and you go out and get that to cover the dependency and the API is not the same!!! AND especially if that might be the only thing you will ever use that lib for ... and you have to stop and rewrite the original.. and as someone else said with maybe documentation of that API that is not maybe finished or... NO ... At that point the person will probably just DISCARD the compile on the lib or program that had the dependency.. rather then put the effort in to learn an entire API that doesn't match up.. BAD IDEA!! cheers, gene ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TH instance code.
Hi Edward, Thank you very much, your code works perfect! -- Andy Edward Kmett ekm...@gmail.com writes: v-- I had accidentally elided the _'s before the t's in the quasiquotation before. What you're looking for is something like: deriveVariable _t = [d| instance Variable $_t where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: $_t) $ fromVariant x|] deriveVariable (conT ''PageType) deriveVariable (conT ''Int) deriveVariable (conT ''Maybe `appT` conT ''Char) ... On Tue, Jun 22, 2010 at 11:24 AM, Andy Stewart lazycat.mana...@gmail.com wrote: Hi all, I have below duplicate code, but i don't know how to use TH instance code. -- duplicate code start -- instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v - read v :: GWindowId) $ fromVariant x -- duplicate code end -- Any TH expert help? Thanks, -- Andy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
On Tue, Jun 22, 2010 at 4:18 PM, Andrew Coppin andrewcop...@btinternet.comwrote: What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had. I would argue that quicksort is considerably simpler, as it doesn't have to maintain an explicit tree, lookup and merge values, deal with bits, etc. For something, perhaps closer in spirit to quicksort, and still compression-oriented, I have an implementation of LZ78 for decompressing streams directly into a monoid, rather than reconstituting the result, which also winds up remarkably terse and a great deal more general than its imperative counter-parts. ;) http://hackage.haskell.org/packages/archive/monoids/0.1.36/doc/html/src/Data-Generator-Compressive-LZ78.html -Edward Kmett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
On Tue, Jun 22, 2010 at 10:18 PM, Andrew Coppin andrewcop...@btinternet.com wrote: Don Stewart wrote: http://hackage.haskell.org/package/huffman A simple and pure Haskell implementation of the Huffman encoding algorithm. What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Quicksort is naturally expressed using filter and (++), etc. Huffman coding is naturally expressed in terms of priority queues, etc. Why is using the right vocabulary OK in one case and not in the other? This seems like an example of list-chauvinism -- what Chris Okasaki calls a communal blind spot of the FP community in Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design -- http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Installing Haskell on OSX
I uninstalled all ports and macports, to try with gtk-osx Once I did all of this, leksah builds, but leksah-server don't, with problems with version of libgthread2. I'm at jhbuild build meta-gtk-osx-bootstrap step of GTK-OSX. Once the next step (jhbuild build meta-gtk-osx-core) is finished, and all is fine (and really I hope it), there are some consideration, before directly reinstall cabal gtk packages, and reinstall leksah? I ask because it sais thath jhbuild is needed to build gtk apps. Cheers. Note: Somebody wants a Macbook? I sell mine :P El 22/06/2010, a las 3:36, Hamish Mackenzie escribió: On 22 Jun 2010, at 08:01, Giuseppe Luigi Punzi Ruiz wrote: uhmm.. Now, with all gtk2 rebuilded with +no_x11 and +quartz I get Linking dist/build/leksah/leksah ... ld: library not found for -lgtk-x11-2.0 collect2: ld returned 1 exit status cabal: Error: some packages failed to install: leksah-0.8.0.6 failed during the building phase. The exception was: ExitFailure 1 I searched, and it suppose libgtk-x11-2.0 is part of GTK2, but I only can found it in darwinports inside xulrunner package, but fails me a lot building. Some idea? I think something must still have been built against gtk x11. Did you rebuild all of Gtk2Hs after rebuilding Gtk? cabal install --reinstall glib cabal install --reinstall gio cabal install --reinstall cairo cabal install --reinstall pango cabal install --reinstall gtk cabal install --reinstall gtksourceview If that does not fix it, you could try this to find the package at fault. grep gtk-x11 ~/.ghc/i386-darwin-6.12.1/package.conf.d/* I am interested to see how you get on with MacPorts. I have not tried it myself in a while. I built the current Leksah OS X binary with jhbuild... http://sourceforge.net/apps/trac/gtk-osx/wiki/Build I am sorry that the current binary is not compatible with OS X 10.5. I will try to use OS X 10.5 to build the next release to make sure it is compatible. Once you have Leksah working you will probably need to update the keymap file (~/.cabal/share/leksah-0.8.0.6/data/keymap.lkshk) if you want Command-C, V and X to work. Just uncomment the three lines already in there... ctrlx - EditCut ctrlc - EditCopy ctrlv - EditPaste You will probably find it beeps each time you use them. I have a nice fix for that but I think it requires a newer version of ige-mac- integration than the one in MacPorts. Good Luck, Hamish Giuseppe Luigi Punzi Ruiz Blog: http://www.lordzealon.com Twitter Skype GoogleTalk accounts: glpunzi ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] TypeFamillies and UndecidableInstances - why?
When I tried to do something like:
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
class Test a where
type TestMonad a :: * - *
from :: a b - TestMonad a b
to :: TestMonad a b - a b
data Testable a b = Testable (a b)
instance (Test a, Functor (TestMonad a)) = Functor (Testable a) where
f `fmap` Testable v = Testable $! (to . fmap f . from) v
It asks for adding UndecidableInstances as:
test.hs:11:0:
Constraint is no smaller than the instance head
in the constraint: Functor (TestMonad a)
(Use -XUndecidableInstances to permit this)
In the instance declaration for `Functor (Testable a)'
What is undecidable? a is bound so TestMonad a should be bound so
Functor (TestMonad a) should be valid.
Is it a bug/missing feature in ghc or do I fail to see something?
Regards
signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TypeFamillies and UndecidableInstances - why?
On Jun 22, 2010, at 21:41 , Maciej Piechotka wrote: test.hs:11:0: Constraint is no smaller than the instance head in the constraint: Functor (TestMonad a) (Use -XUndecidableInstances to permit this) In the instance declaration for `Functor (Testable a)' What is undecidable? a is bound so TestMonad a should be bound so Functor (TestMonad a) should be valid. I *think* the point of the error message is that Functor (TestMonad a) is a tautology, so including it doesn't actually constrain the instance (which in GHC-ese is Constraint is no smaller than the instance head). In short, GHC thinks you're being tricky in a way it can't understand, because otherwise there's no point in including the constraint, so it's telling you that being tricky requires UndecidableInstances. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: TypeFamillies and UndecidableInstances - why?
On Tue, 2010-06-22 at 21:51 -0400, Brandon S. Allbery KF8NH wrote: On Jun 22, 2010, at 21:41 , Maciej Piechotka wrote: test.hs:11:0: Constraint is no smaller than the instance head in the constraint: Functor (TestMonad a) (Use -XUndecidableInstances to permit this) In the instance declaration for `Functor (Testable a)' What is undecidable? a is bound so TestMonad a should be bound so Functor (TestMonad a) should be valid. I *think* the point of the error message is that Functor (TestMonad a) is a tautology, so including it doesn't actually constrain the instance (which in GHC-ese is Constraint is no smaller than the instance head). In short, GHC thinks you're being tricky in a way it can't understand, because otherwise there's no point in including the constraint, so it's telling you that being tricky requires UndecidableInstances. I'm sorry but how Functor (TestMonad a) is a tautology? It cannot be derived from other constraints (in and outside this class). Unless you mean that GHC thinks it is tautology. Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: srec-0.0.0
For those others like me who have no idea what s-record files are: http://en.wikipedia.org/wiki/S-record On 23 June 2010 03:36, Tom Hawkins tomahawk...@gmail.com wrote: A little library for reading s-record files: http://hackage.haskell.org/package/srec -Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TypeFamillies and UndecidableInstances - why?
On Wednesday 23 June 2010 03:41:47, Maciej Piechotka wrote:
When I tried to do something like:
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
class Test a where
type TestMonad a :: * - *
from :: a b - TestMonad a b
to :: TestMonad a b - a b
data Testable a b = Testable (a b)
instance (Test a, Functor (TestMonad a)) = Functor (Testable a) where
f `fmap` Testable v = Testable $! (to . fmap f . from) v
It asks for adding UndecidableInstances as:
test.hs:11:0:
Constraint is no smaller than the instance head
in the constraint: Functor (TestMonad a)
(Use -XUndecidableInstances to permit this)
In the instance declaration for `Functor (Testable a)'
What is undecidable? a is bound so TestMonad a should be bound so
Functor (TestMonad a) should be valid.
Is it a bug/missing feature in ghc or do I fail to see something?
Regards
The constraint contains one type variable, as does the instance head, so
the compiler can't be sure that type checking will terminate.
Here, UndeciableInstances means, type checking will terminate, go ahead.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Huffman Codes in Haskell
G'day all.
Quoting Andrew Coppin andrewcop...@btinternet.com:
What the...?
Oh, I see. It uses another package to handle the tricky sorting and
searching stuff. Well, yeah, that would make the code a bit shorter...
;-)
Even so, it's not nearly as elegant to behold as, say, the quicksort
algorithm, despite being of roughly similar complexity. Still, it's
shorter than what I had.
Ah, but the famous Haskell quicksort algorithm is optimised for brevity.
It's an executable specification of quicksort, not a practical sort
algorithm.
But honestly, it's just not that hard to do in linear time, assuming
the symbols are sorted by frequency:
data HuffmanTree a = Empty
| Node (HuffmanTree a) (HuffmanTree a)
| Leaf a
deriving Show
huffmanTree :: (Ord w, Num w) = [(w,a)] - HuffmanTree a
huffmanTree
= build . map (id Leaf) . sortBy (comparing fst)
where
build [] = Empty
build [(_,t)] = t
build ((w1,t1):(w2,t2):wts)
= build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts
Now if you want a real challenge, implement length-limited Huffman
codes. Here's a suggested interface:
-- There really should be a better traits typeclass for bit hackery,
-- but there isn't.
class (Integral w, Bits w) = WordType w where { wordBits :: w - Int }
instance WordType Word8 where { wordBits = 8 }
instance WordType Word16 where { wordBits = 16 }
instance WordType Word32 where { wordBits = 32 }
instance WordType Word64 where { wordBits = 64 }
minimalRedundancyCode :: (Ord w, Num w, WordType word) =
[(w,a)] - [(a,Int,word)]
-- minimalRedundancyCode returns an optimal prefix-free minimal-redundancy
-- code such that every code fits in a word of size w. An entry (a,b,w)
-- in the result means that the code for a is stored in the b least
-- significant bits of w.
Andrew Bromage
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: srec-0.0.0
On Tue, Jun 22, 2010 at 9:08 PM, Ivan Miljenovic ivan.miljeno...@gmail.com wrote: For those others like me who have no idea what s-record files are: http://en.wikipedia.org/wiki/S-record Sorry, I should have been more clear. In embedded systems development, s-records are typically used to hold the ROM image of a processor. It is the last file produced by the compiler tool chain and the file that is loaded (aka. flashed) into the processor. My interest, and hence the motivation for the library, is to conduct software verification on machine code. This library may soon be tied in with my powerpc instruction set simulator [1]. -Tom [1] http://hackage.haskell.org/package/powerpc ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Control.Alternative --- some and many?
Hey everyone, Could someone explain to me (or point me to a reference explaining) the purpose of the some and many methods of the Alternative class? Also, there is a link posted in the documentation for Control.Applicative to a paper which describes the motivation behind the Applicative class; is there similarly a paper explaining the motivation behind the Alternative class? (The problem with Googling for Alternative is that this word is used a whole lot of the time, and very rarely does it refer to the Alernative class. :-) ) Cheers, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Relating generated asm to Core
Hi, Can anyone tell me a way to identify the generated assembly (as found in the intermediate files produced by GHC) corresponding to a particular fragment of Core code. Thanks, Rami The information in this e-mail may be confidential and subject to legal professional privilege and/or copyright. National ICT Australia Limited accepts no liability for any damage caused by this email or its attachments. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Relating generated asm to Core
Rami.Mukhtar: Hi, Can anyone tell me a way to identify the generated assembly (as found in the intermediate files produced by GHC) corresponding to a particular fragment of Core code. Hey Rami, I use the ghc-core tool: http://hackage.haskell.org/package/ghc-core Which displays both the core and assembly in a pager, with syntax highlighting. In general, if you see foo in the Core, you're looking for foo_entry or similar in the assembly. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] checking types with type families
I have a parameterized data type: data Val result = VNum Double | VThunk (SomeMonad result) type Environ result = Map Symbol (Val result) I have a class to make it easier to typecheck Vals: class Typecheck a where from_val :: Val result - Maybe a instance Typecheck Double where from_val (VNum d) = Just d from_val _ = Nothing Now I can write lookup_environ :: (Typecheck a) = Symbol - Environ result - Maybe a Now of course there's a question of how to write Typecheck for VThunk. I would like to be able to call 'lookup_environ' expecting a 'SomeMonad result' and get Nothing or Just depending on if it's present. instance Typecheck (SomeMonad result) where from_val (VThunk f) = Just f But I need something to say that the 'result' from the instance head is the same as the 'result' from the class declaration, because otherwise I get Couldn't match expected type `result' against inferred type `result1' So maybe a type family? class Typecheck ... type ResultOf a :: * from_val :: Val (ResultOf a) - Maybe a instance Typecheck (SomeMonad result) where type ResultOf (SomeMonad result) = result ... Now the question is, what's the ResultOf a Double? Well, since the output doesn't depend on 'result' at all, I would like to be able to write 'type ResultOf Double = anything', and then I can look up a VNum in an 'Environ anything'. Unfortunately, that type declaration isn't legal because it wants 'anything' to be bound somewhere. I tried explicitly introducing 'anything' with a forall, but no dice. So there are a number of possible solutions to this problem. One is, is there another way to get from the expression language type VNum, VThunk, etc. to a haskell type that doesn't use typeclasses in this way? Or, is there a way to assert in the instance of 'Typecheck (SomeMonad result)' that its 'result' is equal to the 'result' in the class declaration without using type families in this way? Or, is there a way to use type families in the way I'm using them to leave 'result' polymorphic in the cases where it can be left free in the result (e.g. VNum 42 :: Val anything)? I know lots of people have used haskell to write little interpreters, so maybe someone has solved this problem before. Basically, I have a Val that is semi-polymorphic, but even if I go the totally monomorphic / dynamic type route by making a Result type with all the different types, I still have trouble converting from haskell types and back when I need to write the Result - result function. I suppose I could play the same Typecheck game there, but I like the idea of an Environ X that doesn't admit the wrong kind of VThunk. It seems like I should be able to express that in the type system and be safer as well as save some packing and unpacking. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] checking types with type families
On 23 June 2010 13:46, Evan Laforge qdun...@gmail.com wrote: I have a parameterized data type: data Val result = VNum Double | VThunk (SomeMonad result) type Environ result = Map Symbol (Val result) I have a class to make it easier to typecheck Vals: class Typecheck a where from_val :: Val result - Maybe a I think your problem here is that there's no mention of `a' on the left-hand size of from_val's type signature; you either need to use MPTC+fundep to associate what result is compared to a, or else use a phantom type parameter of Val to make it data Val result a = ... and then from_val :: Val result a - Maybe a. SPJ's paper on type families has this situation arising in the section on defining a graph class. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] checking types with type families
On Wednesday 23 June 2010 05:46:46, Evan Laforge wrote: I have a parameterized data type: data Val result = VNum Double | VThunk (SomeMonad result) type Environ result = Map Symbol (Val result) I have a class to make it easier to typecheck Vals: class Typecheck a where from_val :: Val result - Maybe a Would it work if you made Typecheck a two-parameter type class? class Typecheck result a where from_val :: Val result - Maybe a instance Typecheck result Double where ... instance Typecheck result (SomeMonad result) where instance Typecheck Double where from_val (VNum d) = Just d from_val _ = Nothing Now I can write lookup_environ :: (Typecheck a) = Symbol - Environ result - Maybe a Now of course there's a question of how to write Typecheck for VThunk. I would like to be able to call 'lookup_environ' expecting a 'SomeMonad result' and get Nothing or Just depending on if it's present. instance Typecheck (SomeMonad result) where from_val (VThunk f) = Just f But I need something to say that the 'result' from the instance head is the same as the 'result' from the class declaration, because otherwise I get Couldn't match expected type `result' against inferred type `result1' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] TypeFamillies and UndecidableInstances - why?
On Wed, 23 Jun 2010, Maciej Piechotka wrote:
When I tried to do something like:
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
class Test a where
type TestMonad a :: * - *
from :: a b - TestMonad a b
to :: TestMonad a b - a b
data Testable a b = Testable (a b)
instance (Test a, Functor (TestMonad a)) = Functor (Testable a) where
f `fmap` Testable v = Testable $! (to . fmap f . from) v
It asks for adding UndecidableInstances as:
test.hs:11:0:
Constraint is no smaller than the instance head
in the constraint: Functor (TestMonad a)
(Use -XUndecidableInstances to permit this)
In the instance declaration for `Functor (Testable a)'
Basically, the compiler starts with Is `Testable a` a Functor? and
ends with Is `a` a Test and (figure out what `TestMonad a`) a Functor?
The second question is more work to do than it started with.
The `Test a` constraint is fine, because you're at least narrowing
down the type in question. But `TestMonad a` is a type function
that could be literally anything, including `Testable a` itself,
which would leave us at:
instance (Functor (Testable a)) = Functor (Testable a)
Which is obviously problematic.
Friendly,
--Christopher Lane Hinson
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Huffman Codes in Haskell
G'day all. But honestly, it's just not that hard to do in linear time, assuming the symbols are sorted by frequency: Or maybe not so easy. Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Control.Alternative --- some and many?
I'm not sure how Alternative differs from MonadPlus, other than being defined for Applicative rather than Monad. They have the same laws (identity and associativity). Some and many are probably motivated by their usefulness in parsers. Hence optional, etc. I'm sure there are plenty of other uses for it. On 23 June 2010 05:22, Gregory Crosswhite gcr...@phys.washington.edu wrote: Hey everyone, Could someone explain to me (or point me to a reference explaining) the purpose of the some and many methods of the Alternative class? Also, there is a link posted in the documentation for Control.Applicative to a paper which describes the motivation behind the Applicative class; is there similarly a paper explaining the motivation behind the Alternative class? (The problem with Googling for Alternative is that this word is used a whole lot of the time, and very rarely does it refer to the Alernative class. :-) ) Cheers, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
