November 2006 - Haskell-Cafe

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 09 Nov '06

09 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 09 Nov '06

09 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 09 Nov '06

09 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 09 Nov '06

09 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

Newbie Q: composeMaybe :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
by Dmitri O.Kondratiev 09 Nov '06

09 Nov '06

I am trying to solve a problem from "The Craft of Functional Programming" book: 14.38 ... define the function: data Maybe a = Nothing | Just a composeMaybe :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c) using functions: squashMaybe :: Maybe (Maybe a) -> Maybe a squashMaybe (Just (Just x)) = Just x squashMaybe _ = Nothing mapMaybe :: (a -> b) -> Maybe a -> Maybe b mapMaybe f Nothing = Nothing mapMaybe f (Just x) = Just (f x) As a first step to the solution I defined auxilary function: f1 f g x = mapMaybe f (g x) GHCi gives the following type for this function: f1 :: (a -> b) -> (t -> Maybe a) -> t -> Maybe b ^^^ Q: I don't quite understand this signature. I would expect this instead (by mapMaybe definition): f1 :: (a -> b) -> (t -> Maybe a) -> Maybe b >From where does the second 't' come from? What are the arguments and what f1 returns in this case?

2 2

StateT and modify
by Peter Steiner 09 Nov '06

09 Nov '06

hi haskellers, i have a basic question regarding StateT encapsulating IO and the modify function. my scenario is similar to the following simple code snippet: > import Control.Monad.State > > type MyState = StateT Int IO > > test = evalStateT foo 0 > > foo = do > modify $ (+) 1 > get i would like to be able to debug what's happening inside the modifier function. that's why i want to be able to use a modifier that's in the IO monad, like in the following, obviously defunct snippet: > test = evalStateT bar 0 > > bar = do > modify $ myAdd 1 > get > > myAdd :: Int -> Int -> IO Int > myAdd x y = do > putStr "in myAdd\n" > return $ x + y this fails because (myAdd :: Int -> Int -> IO Int) does not match the required modify argument type (Int -> Int -> Int) for MyState. Couldn't match expected type `Int' against inferred type `IO Int' In the second argument of `($)', namely `myAdd 1' In the expression: modify $ (myAdd 1) In a 'do' expression: modify $ (myAdd 1) is it possible to 'lift' StateT modify into the inner monad (IO in my case)? regards, peter.

5 9