March 2008 - Haskell-Cafe

Re: [Haskell-cafe] Gtk2hs
by Andrew Coppin 14 Mar '08

14 Mar '08

Don Stewart wrote: > andrewcoppin: > >> Just a short one... gtk2hs won't build on my [Linux] laptop. What's the >> best channel for seeking help with this? >> > > Discuss it on the gtk2hs list, with a full error log. > Thanks. I'll go look at that. (Who knows, maybe somebody already solved this one...)

1 0

Ackermann Function Memoization, GHC Weird Output or Bug?
by Donnie Jones 14 Mar '08

14 Mar '08

Hello, I'm learning Haskell, so I was attempting memoization based upon the Fibonacci examples but for the Ackermann function. In my tests, I found what seems to be truncated output. See my comments at the end of the code for the test cases and output. ### Begin Code ### module Main where import Data.Array main = do let m = 3 n = 1 a = ackermann_mem m n putStrLn("Ackermann-mem " ++ show m ++ " " ++ show n ++ " = " ++ show a) -- Functions. -- Based upon examples from: -- http://reddit.com/r/programming/info/16ofr/comments) <http://reddit.com/r/programming/info/16ofr/comments%29> tabulate bounds f = array bounds [(i, f i) | i <- range bounds] dp bounds f = (memo!) where memo = tabulate bounds (f (memo!)) -- Trying to apply memoization function to Ackermann. ackermann_mem m n = dp ((0,0), (30, 1000)) ack (m, n) where ack rec (0, n) = n + 1 ack rec (m, 0) = rec (m - 1, 1) ack rec (m, n) = rec (m - 1, rec (m, n - 1)) {- Test cases: ackermann_mem 4 1 = 533 -- when using (30, 1000) as upper bound. ackermann_mem 4 1 = 5533 -- when using (30, 10000) as upper bound. ackermann_mem 4 1 = 65533 -- when using (30, 100000) as upper bound. <--- correct answer! -} ### End Code ### It seems if I don't choose an upper bound pair for (m,n) that is large enough I get truncated output for the answer, instead of GHC giving me an array index exception... This behavior seems very odd to me, can someone explain? Or is this a bug? Thank you. __ Donnie Jones

4 4

File I/O question
by Andrew Coppin 14 Mar '08

14 Mar '08

Hi Cafe. There's good news and there's bad news. The bad news is... I'm back. [Did I miss anything good?] The good news is... I have an actual question to ask as well. When I write to a file using System.IO, the file is locked for exclusive access. I gather this is as specified in the Haskell Report. Which is nice, but... I'd actually prefer the file to *not* be locked. Anybody know how to do that?

6 12

Space leak - help needed
by Krzysztof Kościuszkiewicz 14 Mar '08

14 Mar '08

Dear Haskellers, Another story from an (almost) happy Haskell user that finds himself overwhelmed by laziness/space leaks. I'm trying to parse a large file (>600MB) with a single S-expression like structure. With the help of ByteStrings I'm down to 4min processing time in constant space. However, when I try to wrap the parse results in a data structure, the heap blows up - even though I never actually inspect the structure being built! This bugs me, so I come here looking for answers. Parser follows: > module Main where > > import qualified Data.ByteString.Lazy.Char8 as B > import Text.ParserCombinators.Parsec > import Text.ParserCombinators.Parsec.Pos > import System.Environment > import System.Exit > import qualified Data.Map as M > import Lexer > > type XdlParser a = GenParser Token XdlState a > > -- Parser state > type XdlState = Counts > > type Counts = M.Map Count Integer > > data Count = ListCount | SymbolCount > deriving (Eq, Ord, Show) > > emptyXdlState = M.empty > > incCount :: Count -> (Counts -> Counts) > incCount c = M.insertWith' (+) c 1 > > -- handling tokens > myToken :: (Token -> Maybe a) -> XdlParser a > myToken test = token showTok posTok testTok > where > showTok = show > posTok = const (initialPos "") > testTok = test > > -- Syntax of expressions > data Exp = Sym !B.ByteString | List ![Exp] > deriving (Eq, Show) > > expr = list <|> symbol > > rparen = myToken $ \t -> case t of > RParen -> Just () > other -> Nothing > > lparen = myToken $ \t -> case t of > LParen -> Just () > other -> Nothing > > name = myToken $ \t -> case t of > Name n -> Just n > other -> Nothing > > list = do > updateState $ incCount ListCount > lparen > xs <- many1 expr > rparen > return () > -- return $! (List xs) > > symbol = do > updateState $ incCount SymbolCount > name >> return () > -- Sym `fmap` name > > -- Top level parser > top :: XdlParser XdlState > top = do > l <- many1 list > eof > getState > > main = do > args <- getArgs > case args of > [fname] -> do > text <- B.readFile fname > let result = runParser top emptyXdlState fname (tokenize text) > putStrLn $ either show show result > _ -> putStrLn "usage: parse filename" >> exitFailure And the Lexer: > module Lexer (Token(..), tokenize) where > > import qualified Data.ByteString.Lazy.Char8 as B > import Control.Monad > import Data.Char > import Data.List > import System.Environment > import System.Exit > > data Token = LParen > | RParen > | Name B.ByteString > deriving (Ord, Eq, Show) > > type Input = B.ByteString > > -- Processor returns Nothing if it can't process the Input > type Processor = Input -> Maybe ([Token], Input) > > -- Tokenize ends the list when all processors return Nothing > tokenize :: Input -> [Token] > tokenize = concat . unfoldr processAll > where > processors = [doSpaces, doComment, doParens, doName] > processAll :: Processor > processAll bs = if B.null bs > then Nothing > else foldr mminus Nothing $ map ($ bs) processors > mminus a@(Just _) _ = a > mminus Nothing b = b > > doSpaces :: Processor > doSpaces bs = > if B.null sp > then Nothing > else Just ([], nsp) > where > (sp, nsp) = B.span isSpace bs > > doComment :: Processor > doComment bs = > if B.pack "# " `B.isPrefixOf` bs > then Just ([], B.dropWhile (/= '\n') bs) > else Nothing > > doParens :: Processor > doParens bs = case B.head bs of > '(' -> Just ([LParen], B.tail bs) > ')' -> Just ([RParen], B.tail bs) > _ -> Nothing > > doName :: Processor > doName bs = > if B.null nsp > then Nothing > else Just ([Name nsp], sp) > where > (nsp, sp) = B.span (not . isRest) bs > isRest c = isSpace c || c == ')' || c == '(' Regards, -- Krzysztof Kościuszkiewicz Skype: dr.vee, Gadu: 111851, Jabber: kokr(a)jabberpl.org "Simplicity is the ultimate sophistication" -- Leonardo da Vinci

5 8

FFI newbie question
by Verma Anurag-VNF673 14 Mar '08

14 Mar '08

I am trying to figure out how to pass array of String (char **) from C to Haskell? I have read the FFI examples, but most of them are centered on calling C from Haskell. I have read in the mailing list, it is rare to call Haskell from C, but my requirement is such that I am going to write Haskell library that needs to be called from C. Also, I read that the linking in FFI needs to be done through ghc. However, I have an existing Make system that uses gcc to do the linking, so what extra steps I need to do make gcc do the linking instead? Anurag

2 1

A question about "monad laws"
by Deokjae Lee 14 Mar '08

14 Mar '08

Tutorials about monad mention the "monad axioms" or "monad laws". The tutorial "All About Monads" says that "It is up to the programmer to ensure that any Monad instance he creates satisfies the monad laws". The following is one of the laws. (x >>= f) >>= g == x >>= (\v -> f v >>= g) However, this seems to me a kind of mathematical identity. If it is mathematical identity, a programmer need not care about this law to implement a monad. Can anyone give me an example implementation of monad that violate this law ?

28 58

Problem making a program in ghc
by Maverick 14 Mar '08

14 Mar '08

Hi, I have a problem when I am trying to use a binary file generated by ghc make in Windows. Ihave writed an application that parses xml files and returns a result(using HaXml), this is published as a service, I implemented a server(withSocketsDo), the server listen the port 5760 in a forever fashion,when a message arrives, then the program creates a new thread (forkIO)for attend the request. This works fine when I run it from ghci, when I make the program and run the binary (in Windows), the requests arrive to the program but I think that the response can´t be sentbecause the front end can´t receive the response (I am calling theservice from a .Net web application), I have a log that confirms that the response arrives correctly. I use make like this: ghc --make -package HaXml Main.hs HermesService.hs ..... What could be the problem? I am using HaXml 1.13.2 with Ghc 6.6.1, thanks in advance. Alvaro Sejas UMSS Cochabamba - Bolivia ______________________________________________ Enviado desde Correo Yahoo! El buzón de correo sin límite de almacenamiento. http://es.docs.yahoo.com/mail/overview/index.html

4 3

Naming as infection
by Greg Meredith 14 Mar '08

14 Mar '08

All, Here <http://biosimilarity.blogspot.com/2008/03/naming-as-dialectic.html> is a deliberately provocative posting (with running code and a shameless plug for BNFC) on the process of introducing naming and name management into the design of data structures. Comments greatly appreciated. Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)
by Conor McBride 13 Mar '08

13 Mar '08

Hi On 13 Mar 2008, at 23:42, kahl(a)cas.mcmaster.ca wrote: > Conor McBride <conor(a)strictlypositive.org> responded to my comment: > >>> (mapMonotonic should of course be removed, too, >>> or specified to fail (preferably in some MonadZero) >>> if the precondition is violated, >>> which should still be implementable in linear time.) >> >> What's wrong with mapMonotonic that isn't wrong >> with, say, sortBy?, or Eq instances for parametrized >> types? > > Prelude> :m + Data.Set > Prelude Data.Set> toAscList $ mapMonotonic (10 -) (fromList [1 .. 5]) > [9,8,7,6,5] > Prelude Data.Set> 5 `member` mapMonotonic (10 -) (fromList [1 .. 5]) > False > > > Something's certainly wrong there! But nothing out of the ordinary: garbage in, garbage out. Happens all the time, even in Haskell. Why pick on mapMonotonic? Prelude Data.List> sortBy (\_ _ -> GT) [1,3,2,5,4] [4,5,2,3,1] Prelude Data.List> sortBy (\_ _ -> GT) [4,5,3,2,1] [1,2,3,5,4] I guess there's a question of what we might call "toxic waste"---junk values other than undefined. I think undefined is bad enough already. So the type system can't express the spec. I don't think we should be casual about that: we should be precise in documentation about the obligations which fall on the programmer. Some dirt is pragmatically necessary: we shouldn't pretend that it ain't so; we shouldn't pretend that dirt is clean. > > >> >> Before we can talk about what == should return, >> can we settle what we mean by = ? > > ``='' is not in the Haskell interface! ;-) No, but "is" is in the human interface! > > Therefore, I talked only about (==). Ah, but you talked about things. Which things? Is one of the things you talked about the same as (==)? the same as (flip (==))? > > The best way to include ``='' seems to be the semantic equality of > P-logic > [Harrison-Kieburtz-2005], which is quite a heavy calibre, > and at least in that paper, classes are not yet included. I expect it's hard work. It's hard work in much better behaved systems. My point is that it's worth it, in order to facilitate more meaningful discussions. All the best Conor

1 0

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)
by Conor McBride 13 Mar '08

13 Mar '08

Hi folks I'm late into this thread, so apologies if I'm being dim. On 13 Mar 2008, at 16:17, kahl(a)cas.mcmaster.ca wrote: > Adrian Hey <ahey(a)iee.org> wrote: > >> I would ask for any correct Eq instance something like the law: >> (x==y) = True implies x=y (and vice-versa) I wish I knew what = meant here. Did somebody say? I don't think it's totally obvious what equational propositions should mean. Nor do I think it's desirable to consider only those propositions expressible in QuickCheck. If = is reflexive and distinguishes undefined from True, then x = y implies (x == y) = True will be tricky to satisfy for quite a lot of types. What about undefined == undefined or repeat 'x' == repeat 'x' ? For some suitable (slightly subtle) definition of "finite", you might manage x finite and x = y implies (x == y) = True One rather intensional definition of x = y might be "x and y have a common n-step reduct" with respect to some suitable operational semantics. I don't think this is what Adrian had in mind, but it certainly falls foul of Wolfram's objection. > > The easiest counterexample are sets (or finite maps) > provided as an abstract data type (i.e., exported without access to > the > implementation, in particular constructors). > Different kinds of balanced trees typically do not produce the same > representation for the same set constructed by different construction > expressions. This suggests that we should seek to define x = y on a type by type basis, to mean "x and y support the same observations", for some suitable notion of observation, which might depend crucially on what operations are exported from the (notional or actual) module which defines the type. If so, it's clearly crucial to allow some observations which rely on waiting for ever, in order to avoid _|_-induced collapse. Something of the sort should allow this... > > Therefore, (==) on sets will be expected to produce equality of sets, > which will only be an equivalence on set representations. ...but this... > >> which implies (f x == f y) = True (for expression types which are >> instances of Eq). > > This specifies that (==) is a congurence for f, and is in my opinion > the right specification: (==) should be a congurence > on all datatypes with respect to all purely defineable functions. ...is more troublesome. Take f = repeat. Define f = f. I'd hope x == y = True would give us x = y, and that x == y would be defined if at least one of x and y is finite. That implies f x = f y, which should guarantee that f x == f y is not False. > But at least nowadays people occasionally do export functions > that allow access to representation details, [..] > I consider this as an argument to remove showTree from the > interface of > Data.Set, and to either specify toList to produce an ordered list > (replacing toAscList), or to remove it from the interface as well. Perhaps that's a little extreme but I agree with the sentiment. How about designating such abstraction- breaking functions "nosy", in the same way that functions which might break purity are "unsafe". > (mapMonotonic should of course be removed, too, > or specified to fail (preferably in some MonadZero) > if the precondition is violated, > which should still be implementable in linear time.) What's wrong with mapMonotonic that isn't wrong with, say, sortBy?, or Eq instances for parametrized types? > >> but if so would like to appeal to movers and shakers in the >> language definition to please decide exactly what the proper >> interpretation of standard Eq and Ord "class laws" are and in the >> next version of the report give an explanation of these > > Strongly seconded, inserting ``precise'' before ``explanation'' ;-) > > (And I'd expect equivalences and congruences to be accessible > on the basis of standard first-year math...) Before we can talk about what == should return, can we settle what we mean by = ? I think we need to pragmatic about breaking the rules, given suitable documentation and maybe warnings. We should at least aspire to some principles, which means we should try to know what we're talking about and to know what we're doing, even if we don't always do what we're talking about. I'll shut up now. Potatoes to peel Conor

1 0