- Haskell-Cafe - Haskell.org

Automatic fixity allocation for symbolic operators
by Brian Hulley 11 Nov '06

11 Nov '06

Hi - I'm wondering if it is possible to construct a methodical procedure to assign a fixity to symbolic operators so that we could get rid of the need for user defined fixites. User defined fixities are an enormous problem for an interactive editor, because it is not possible to construct a parse tree of some code if you don't know what the fixities are, and an editor must be able to do something useful with a code fragment without having to look inside other modules (because the other modules may not yet have even been written!). Also, the programmer or reader of code needs to be able to understand each code fragment independently as well. >From the Haskell98 report, the Prelude defines: infixr 9 ., !! infixr 8 ^, ^^, ** infixl 7 *, /, `quot`, `rem`, `div`, `mod` infixl 6 +, - infixr 5 :, ++ infix 4 ==, /=, <, <=, >=, > infixr 3 && infixr 2 || infixl 1 >>, >>= infixr 1 =<< infixr 0 $, $!, `seq` Suppose we ignore the varid operators and just consider the symbolic ops. What I'm trying to find is a systematic way to assign fixities to all other possible sequences of symbol characters that is consistent with what we've already got in the Prelude. As a first step, we could say that "mirrored" operators must share the same precedence ie: =<< >>= < > For associativity, we could assign each character an associativity weight: -1 left associative 0 neutral 1 right associative and say that the associativity is simply the sign of the sum of the associativity weights of the characters thus: > -1 = 0 < 1 =<< 0 + 1 + 1 ie infixr Note that I don't care about non-associative ops since the non-associativity of something should be a question for the type checker not the parser imho - ideally we should be able to create a parse tree for any possible operator expression. To form the precedence, we could assign each character a precedence value eg: 9 . ! 8 ^ 7 * / 6 + - 5 : 4 = 3 & 2 | 1 < > 0 $ A first attempt might be to say that the precedence is simply the decimal expansion of the precedence values eg >>= has precedence 1.14 and $! has precedence 0.9. However, as noted above, mirrored ops must share the same precedence so an alternative is to create some ordering of characters such that when the set of characters in an operator is sorted according to this ordering, the decimal expansion of the precedence digits will give the same relative ordering for operator precedences as the Prelude. For example, using $ | & + - * / ^ . ! : < > = as the ordering, we'd get: infixr 9 . !! 9 9.9 infixr 8 ^, ^^, ** 8 8.8 7.7 infixl 7 *, /, 7 7 infixl 6 +, - 6 6 infixr 5 : , ++ 5 6.6 infix 4 ==, /=, <, <=, >=, > 4.4 7.4 1 1.4 1.4 1 infixr 3 && 3.3 infixr 2 || 2.2 infixl 1 >>, >>= 1.1 1.14 infixr 1 =<< 1.14 infixr 0 $, $! 0 0.9 Although most existing ops get a similar precedence (eg ^ ^^ and ** are all still in the same group relative to the other ops despite the fact that within the group there is now an ordering) the main problem seems to be that < <= >= > get precedences that bind too loosely and /= is totally wrong. This problem aside, the above algorithm would give sensible precedences for such things as: :> <: 5.1 <+> <*> 6.11 6.11 where the use of <> neutralizes the associativity contribution of < or > respectively (since (-1) + 1 == 0), giving us the intuitive associativity we'd expect from the "interesting" character in the middle. (The problem of /= getting 7.4 could be solved by putting / after = in the order, to get 4.7, but unfortunately this would mean that since <> must be before =, <> would be before / so </> would get the wrong precedence compared to <*>) Another issue is that there is no assignment of associativity weights such that "*" is infixl but "**" is infixr (ditto + and ++) so perhaps we'd need to associate each character with an associativity function. Similar to precedences, we then define an associativity ordering and let the resulting associativity be the sign of the composition of the sorted functions applied to 1 eg: ^ const (-1) * \x -> x * (-1) = id & const (-1) < (+1) > (+ (-1)) Then * (\x -> x * (-1)) 1 === -1 ie left ** (\x -> x * (-1)) . (\x -> x * (-1)) $ 1 === +1 ie right >>= > > = (+ (-1)) . (+ (-1)) . id $ 1 === -1 <*> -- remember ordering * < > (\x -> x * (-1)) . (+1) . (+ (-1)) $ 1 === ((1 - 1) + 1) * (-1) === -1 ie left as required!!! :-) Anyway this is as far as I've got so far trying to rationally reconstruct the original Prelude precedences to achieve the golden aim of eliminating the infinite problem of fixity declarations from source code... :-) (Regarding `div` `seq` etc - I'd just assign them all the same precedence because use of multiple varid ops in the same expression with different precedences, or trying to combine them with symbolic ops, is just a highway to confusion city imho. Note also that (seq x $ exp) is not only clearer but is also one character shorter than (x `seq` exp)) The main open problem is finding an algorithm which assigns a good precedence to >>= as well as to >= and /= and </> and <*>.... ;-) Any ideas? Thanks, Brian. -- www.metamilk.com

21 57

Announcement: new maintainers forr wxHaskell
by Jeremy O'Donoghue 11 Nov '06

11 Nov '06

Hi all, I'd like to announce that we have a new team of maintainers in place for wxHaskell, so we're hoping that this list will see a significant increase in activtiy in the future. We have several near-term objectives, which will likely occur in roughly the order below: * Pull together all of the patches for various wxHaskell functionalities which are 'out there' into the core distribution. * Enhance support for Unicode. * Ensure that we support GHC 6.4.2 and GHC 6.6. * Add support for wxWidgets 2.6.3 and maintain support for wxWidgets 2.4.2. There are very good reasons why many wxHaskell users will want to continue to use 2.4.2. * 'Cabalize' the wxHaskell build system. * Add new examples and increase the coverage of different wxWidgets functionalities. * Create binary releases / installable packages for popular platforms (Windows, Mac, Debian are current favourites) The maintainers will work mainly on a public Darcs repository at http://darcs.haskell.org/wxhaskell, which will always contain the latest patches, but which may not always be stable. I will, from time to time, release reasonably stable updates of files to Sourceforge CVS, and we will aim for binary releases whenever this makes sense. I'd ask the community to send patches via this list. They will get added to the public Darcs repository once at least one of the maintainers has successfully integrated and built them. We will create a separate developers list if the volume of patches ever threatens to overwhelm the wxhaskell-users list :-) To go with the above, I hereby provide first patch to to the archive at http://darcs.haskell.org/wxhaskell as an attachment. This patch brings together patches from a number of sources (mainly Shelarcy and Eric) to provide some support for Unicode variants of wxWidgets, a couple of extra widgets, preliminary support for wxWidgets 2.6.3 and a patch to enable build with GHC 6.6. None of this would have been possible without a great bunch of volunteers who have come forward and shown great patience with the slow pace at which I have pulled this together. Eric Kow, Shelarcy, Mads Lindstrøm, Time Docker and Frank Berthold have all offered their assistance, and should take a virtual bow. Finally, none of this would have been possible without the assistance of Daan Leijen, the original author of most of wxHaskell, who has been gracious enough to offer advice, and to pass on everything we need to move forward.

4 3

aggressiveness of functional dependencies
by Nicolas Frisby 11 Nov '06

11 Nov '06

I have a question about functional dependencies, instance contexts, and type inference. A specific example and question is in the attached code. In brief the question is: to what degree does type inference use the functional dependencies of an instance's class and context? I believe I am wishing it were more aggressive than it is. Please note that I have not enabled overlapping instances. Any suggestions regarding how to get the inferred type of |rite_t1| to be the one I anticipated would be much appreciated. Of course, I would also appreciate explanations of why I shouldn't anticipate it! The rest of this message is a copy of the attached code. Thanks, Nick I'm using GHC 6.6, but I see the same inferred types with 6.4.1. > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} -- for the coverage condition > > module FunDepEx where A plain ole' isomorphism class. > class Iso a b | a -> b, b -> a where > rite :: a -> b > left :: b -> a Isomorphism lifts through the sum bifunctor. > bifmap_either f g = either (Left . f) (Right . g) > > instance ( Iso f f', Iso g g' > ) => Iso (Either f g) (Either f' g') where > rite = bifmap_either rite rite > left = bifmap_either left left Some types to play around with. > newtype MyChar = MyChar Char deriving (Show, Eq) > > instance Iso MyChar Char where > rite (MyChar c) = c > left c = MyChar c > instance Iso Char MyChar where > rite c = MyChar c > left (MyChar c) = c My type inference confusion follows; the unit arguments are just to suppress the monomorphism restriction. > t1 :: Either Char a > t1 = Left 'c' > > rite_t1 () = rite t1 The inferred type for rite_t1 is rite_t1 :: (Iso (Either Char a) (Either f' g')) => () -> Either f' g' Why isn't the inferred type of rite_t1 the same as the ascribed type of rite_t1'? > rite_t1' :: Iso b b' => () -> Either MyChar b' > rite_t1' () = rite t1

2 5

Great language shootout: reloaded
by Isaac Gouy 11 Nov '06

11 Nov '06

> On 11/10/06, Henk-Jan van Tuyl <hjgtuyl at chello.nl> wrote: >> >> Haskell suddenly dropped several places in the overall socre, when the >> size measurement changed from line-count to number-of-bytes after >> gzipping. Maybe it's worth it, to study why this is; Haskell programs >> are >> often much more compact then programs in other languages, but after >> gzipping, other languages do much better. One reason I can think of, is >> that for very short programs, the import statements weigh heavily. Before this gets out-of-hand, my memory is certainly fallible but as I recall Haskell /did not/ drop several places because size measurement changed from line-count to gzip byte-count. 1) Check the webpage that Don Stewart cached and note the values for the memory use and code-lines multipliers, and note the values for the benchmark weights http://www.cse.unsw.edu.au/~dons/data/haskell_1.html Now go to the computer language shootout website and note the multipliers and benchmark weights. 2) Some Haskell programs were pushed into 'interesting alternative implementations' because they'd strayed so far from the spirit of the benchmark. (It takes a while for people to notice and complain, but eventually they do.) ____________________________________________________________________________________ Do you Yahoo!? Everyone is raving about the all-new Yahoo! Mail beta. http://new.mail.yahoo.com

3 2

Template Haskell.
by szefirov＠ot.ru 10 Nov '06

10 Nov '06

Why doesn't reify return function body? reify (mkName "somefunction") for a function defined in the same module returns constructor VarI (of data type Info) that does not contain function declaration in (Maybe Dec) part. What actions should I perform to get a function body with patterns, expressions and all that?

2 1

Haskell Quiz Solution - Haskell Newbie Requesting Review
by Justin Bailey 10 Nov '06

10 Nov '06

As part of the Ruby Quiz in Haskell solutions appearing on the wiki recently, I just a solution to Ruby Quiz #100 - create a bytecode interpreter for a simple expression language. Like I said, the code below parses simple integer arithmetic expressions and generates byte codes for a hypothetical stack-based intepreter that would evaluate the expressions. To run it, save it as a literate haskell file and run "interpret_tests". That just shows correctness, though. Other output can be obtained by running "compile_tests" (shows bytes for all tests), "generate_tests" (symbolic bytecodes for all tests), and "eval_tests" (evaluate ASTs for all tests). To see the AST generated for a example expression, try something like 'parse "2-2-2"'. I'm just learning Haskell (about a month in) and if anyone has time and desire to critique the code below, I'd love to hear it. I come from an OOP (primarily C# & Ruby) background, so I'm really interested in getting a handle on the functional/Haskell "way" of coding. Thanks for any feedback! Justin p.s. This code is also available on the wiki: http://www.haskell.org/haskellwiki/Haskell_Quiz/Bytecode_Compiler/Solution_… p.p.s. The original ruby quiz is available at: http://www.rubyquiz.com/quiz100.html \begin{code} import Text.ParserCombinators.Parsec hiding (parse) import qualified Text.ParserCombinators.Parsec as P (parse) import Text.ParserCombinators.Parsec.Expr import Data.Bits import Data.Int -- Represents various operations that can be applied -- to expressions. data Op = Plus | Minus | Mult | Div | Pow | Mod | Neg deriving (Show, Eq) -- Represents expression we can build - either numbers or expressions -- connected by operators. This structure is the basis of the AST built -- when parsing data Expression = Statement Op Expression Expression | Val Integer | Empty deriving (Show) -- Define the byte codes that can be generated. data Bytecode = NOOP | CONST Integer | LCONST Integer | ADD | SUB | MUL | POW | DIV | MOD | SWAP deriving (Show) -- Using imported Parsec.Expr library, build a parser for expressions. expr :: Parser Expression expr = buildExpressionParser table factor <?> "expression" where -- Recognizes a factor in an expression factor = do{ char '(' ; x <- expr ; char ')' ; return x } <|> number <?> "simple expression" -- Recognizes a number number :: Parser Expression number = do{ ds <- many1 digit ; return (Val (read ds)) } <?> "number" -- Specifies operator, associativity, precendence, and constructor to execute -- and built AST with. table = [[prefix "-" (Statement Mult (Val (-1)))], [binary "^" (Statement Pow) AssocRight], [binary "*" (Statement Mult) AssocLeft, binary "/" (Statement Div) AssocLeft, binary "%" (Statement Mod) AssocLeft], [binary "+" (Statement Plus) AssocLeft, binary "-" (Statement Minus) AssocLeft] ] where binary s f assoc = Infix (do{ string s; return f}) assoc prefix s f = Prefix (do{ string s; return f}) -- Parses a string into an AST, using the parser defined above parse s = case P.parse expr "" s of Right ast -> ast Left e -> error $ show e -- Take AST and evaluate (mostly for testing) eval (Val n) = n eval (Statement op left right) | op == Mult = eval left * eval right | op == Minus = eval left - eval right | op == Plus = eval left + eval right | op == Div = eval left `div` eval right | op == Pow = eval left ^ eval right | op == Mod = eval left `mod` eval right -- Takes an AST and turns it into a byte code list generate stmt = generate' stmt [] where generate' (Statement op left right) instr = let li = generate' left instr ri = generate' right instr lri = li ++ ri in case op of Plus -> lri ++ [ADD] Minus -> lri ++ [SUB] Mult -> lri ++ [MUL] Div -> lri ++ [DIV] Mod -> lri ++ [MOD] Pow -> lri ++ [POW] generate' (Val n) instr = if abs(n) > 32768 then LCONST n : instr else CONST n : instr -- Takes a statement and converts it into a list of actual bytes to -- be interpreted compile s = toBytes (generate $ parse s) -- Convert a list of byte codes to a list of integer codes. If LCONST or CONST -- instruction are seen, correct byte representantion is produced toBytes ((NOOP):xs) = 0 : toBytes xs toBytes ((CONST n):xs) = 1 : (toConstBytes (fromInteger n)) ++ toBytes xs toBytes ((LCONST n):xs) = 2 : (toLConstBytes (fromInteger n)) ++ toBytes xs toBytes ((ADD):xs) = 0x0a : toBytes xs toBytes ((SUB):xs) = 0x0b : toBytes xs toBytes ((MUL):xs) = 0x0c : toBytes xs toBytes ((POW):xs) = 0x0d : toBytes xs toBytes ((DIV):xs) = 0x0e : toBytes xs toBytes ((MOD):xs) = 0x0f : toBytes xs toBytes ((SWAP):xs) = 0x0a : toBytes xs toBytes [] = [] -- Convert number to CONST representation (2 element list) toConstBytes n = toByteList 2 n toLConstBytes n = toByteList 4 n -- Convert a number into a list of 8-bit bytes (big-endian/network byte order). -- Make sure final list is size elements long toByteList :: Bits Int => Int -> Int -> [Int] toByteList size n = reverse $ take size (toByteList' n) where toByteList' a = (a .&. 255) : toByteList' (a `shiftR` 8) -- All tests defined by the quiz, with the associated values they should evaluate to. test1 = [(2+2, "2+2"), (2-2, "2-2"), (2*2, "2*2"), (2^2, "2^2"), (2 `div` 2, "2/2"), (2 `mod` 2, "2%2"), (3 `mod` 2, "3%2")] test2 = [(2+2+2, "2+2+2"), (2-2-2, "2-2-2"), (2*2*2, "2*2*2"), (2^2^2, "2^2^2"), (4 `div` 2 `div` 2, "4/2/2"), (7`mod`2`mod`1, "7%2%1")] test3 = [(2+2-2, "2+2-2"), (2-2+2, "2-2+2"), (2*2+2, "2*2+2"), (2^2+2, "2^2+2"), (4 `div` 2+2, "4/2+2"), (7`mod`2+1, "7%2+1")] test4 = [(2+(2-2), "2+(2-2)"), (2-(2+2), "2-(2+2)"), (2+(2*2), "2+(2*2)"), (2*(2+2), "2*(2+2)"), (2^(2+2), "2^(2+2)"), (4 `div` (2+2), "4/(2+2)"), (7`mod`(2+1), "7%(2+1)")] test5 = [(-2+(2-2), "-2+(2-2)"), (2-(-2+2), "2-(-2+2)"), (2+(2 * -2), "2+(2*-2)")] test6 = [((3 `div` 3)+(8-2), "(3/3)+(8-2)"), ((1+3) `div` (2 `div` 2)*(10-8), "(1+3)/(2/2)*(10-8)"), ((1*3)*4*(5*6), "(1*3)*4*(5*6)"), ((10`mod`3)*(2+2), "(10%3)*(2+2)"), (2^(2+(3 `div` 2)^2), "2^(2+(3/2)^2)"), ((10 `div` (2+3)*4), "(10/(2+3)*4)"), (5+((5*4)`mod`(2+1)), "5+((5*4)%(2+1))")] -- Evaluates the tests and makes sure the expressions match the expected values eval_tests = concat $ map eval_tests [test1, test2, test3, test4, test5, test6] where eval_tests ((val, stmt):ts) = let eval_val = eval $ parse stmt in if val == eval_val then ("Passed: " ++ stmt) : eval_tests ts else ("Failed: " ++ stmt ++ "(" ++ show eval_val ++ ")") : eval_tests ts eval_tests [] = [] -- Takes all the tests and displays symbolic bytes codes for each generate_tests = concat $ map generate_all [test1,test2,test3,test4,test5,test6] where generate_all ((val, stmt):ts) = (stmt, generate (parse stmt)) : generate_all ts generate_all [] = [] -- Takes all tests and generates a list of bytes representing them compile_tests = concat $ map compile_all [test1,test2,test3,test4,test5,test6] where compile_all ((val, stmt):ts) = (stmt, compile stmt) : compile_all ts compile_all [] = [] interpret_tests = concat $ map f' [test1, test2, test3, test4, test5, test6] where f' tests = map f'' tests f'' (expected, stmt) = let value = fromIntegral $ interpret [] $ compile stmt in if value == expected then "Passed: " ++ stmt else "Failed: " ++ stmt ++ "(" ++ (show value) ++ ")" fromBytes n xs = let int16 = (fromIntegral ((fromIntegral int32) :: Int16)) :: Int int32 = byte xs byte xs = foldl (\accum byte -> (accum `shiftL` 8) .|. (byte)) (head xs) (take (n - 1) (tail xs)) in if n == 2 then int16 else int32 interpret [] [] = error "no result produced" interpret (s1:s) [] = s1 interpret s (o:xs) | o < 10 = interpret ((fromBytes (o*2) xs):s) (drop (o*2) xs) interpret (s1:s2:s) (o:xs) | o == 16 = interpret (s2:s1:s) xs | otherwise = interpret (((case o of 10 -> (+); 11 -> (-); 12 -> (*); 13 -> (^); 14 -> div; 15 -> mod) s2 s1):s) xs \end{code}

3 5

Re: [Haskell-cafe] don't: a 'do' for comonads?
by dons＠cse.unsw.edu.au 10 Nov '06

10 Nov '06

hjgtuyl: > > don't :: whatever -> > > (whatever goes in, nothing comes out) So its: don't :: a -> Void ? -- Don

1 0

don't: a 'do' for comonads?
by dons＠cse.unsw.edu.au 10 Nov '06

10 Nov '06

As seen on #haskell, from an idea by Malcolm, 14:42 ?let top'n'tail = ("<pre>"++) . (++"</pre>") 14:42 lambdabot> Defined. 14:43 dons> > L.top'n'tail "foo me now" 14:43 lambdabot> "<pre>foo me now</pre>" 14:43 mauke> that reminds me, haskell needs don't 14:43 dons> yes! 14:44 pkhuong-> mm. the opposite of do, eh? do for comonads? :) So now a prize to the person who comes up with the best use for the identifier: don't :: ? -- Don

3 3

string to date?
by Magnus Therning 10 Nov '06

10 Nov '06

I've been staring my eyes out trying to find a function that converts a string into a ClockTime or CalendarTime. Basically something like C's strptime(3). I can't seem to find anything like it in System.Time, there are function that convert _to_ a string, but nothing that converts _from_ a string it seems. Where should I look? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. Finagle's Sixth Law: Don't believe in miracles -- rely on them.

5 5

Sistema de Ecuaciones NO lineales
by Sebastian Gaviria 10 Nov '06

10 Nov '06

hola como estan!!!! Quiero preguntar quien puede resolver el sistemas de ecuaciones NO lineales de Newton y el codigo de Jacobi en Haskell me ayudarian mucho al poder implementar ese codigo por Favor es con urgencia tener estos codigos!! muchas gracias !!! -- "La sociedad debe juzgarse por su capacidad para hacer que la gente sea feliz."" SEBASTIAN GAVIRIA J. INGENIERIA SISTEMAS UNIVERSIDAD EAFIT

4 3