- Beginners - Haskell.org

Rewriting traversal over trees
by Darryn Reid 30 Mar '10

30 Mar '10

Hi, I hope that this is an appropriate place to post this question; I'm an experienced computer scientist and mathematician but am new to Haskell (I love it, I might add, but have much to learn). I've coded a (fairly) general rewriting traversal - I suspect the approach might be generalisable to all tree-like types, but this doesn't concern me much right now. My purpose is for building theorem provers for a number of logics, separating the overall control mechanism from the specific rules for each logic. The beauty of Haskell here is in being able to abstract the traversal away from the specific reduction rules and languages of the different logics. I have paired down the code here to numbers rather than modal formulas for the sake of clarity and simplicity. My question is two-fold: 1. Does my representation of the traversal seem good or would it be better expressed differently? If so, I'd appreciate the thoughts of more experienced Haskell users. 2. I cannot really see how to easily extend this to a queue-based breadth-first traversal. I'm sure others must have a good idea of how to do what I'm doing here except in breadth-first order; I'd appreciate it very much if someone could show me how to make a second breadth-first version. Thanks in advance for any help! Darryn. start of code. ------------------------------------------------------------------------- import Control.Monad import Control.Monad.Identity -- Tableau is a tree containing formulas of type a, in -- Fork (disjunctive) nodes and Single (conjunctive) nodes. -- Paths from root to Nil each represent an interpretation. data Tableau a = Nil -- End of a path | Single a (Tableau a) -- Conjunction | Fork (Tableau a) (Tableau a) -- Disjunction deriving (Eq, Show) -- 'Cut' directs the traversal to move back up the tree rather than into -- the current subtree, while 'Next' directs the traversal to proceed -- into the subtree. data Action = Cut | Next deriving (Eq, Show) -- The type of the rewrite function to perform at each node in -- the traversal of the tree. The Rewriter returns the new -- subtree to replace the existing subtree rooted at the -- traversal node, and a direction controlling the traversal -- to the next node. type Rewriter m a = Tableau a -> m (Tableau a, Action) -- The traversal function, depth-first order. rewrite :: (Monad m) => Rewriter m a -> Tableau a -> m (Tableau a) rewrite rf t = do (t', d) <- rf t rewrite' rf d t' -- Worker function for traversal, really its main body. rewrite' :: (Monad m) => Rewriter m a -> Action -> Tableau a -> m (Tableau a) rewrite' rf Cut t = return t rewrite' rf Next Nil = return Nil rewrite' rf Next (Single x t1) = do t1' <- rewrite rf t1 return (Single x t1') rewrite' rf Next (Fork t1 t2) = do t1' <- rewrite rf t1 t2' <- rewrite rf t2 return (Fork t1' t2') -- Some examples to test the code with: -- ghci> let t0 = (Single 2 (Single 3 Nil)) -- ghci> let t1 = (Single 1 (Fork t0 (Fork (Single 4 Nil) (Single 5 Nil)))) -- ghci> let t2 = (Fork (Single 10 Nil) (Single 11 Nil)) -- ghci> let t3 = (Fork (Single 3 Nil) (Single 3 Nil)) -- Running "test4 t1 t2" produces the expected result; running -- "test4 t1 t3" does not terminate, because this endlessly -- generates new patterns that match the substitution condition: test4 :: (Num t) => Tableau t -> Tableau t -> Tableau t test4 tab tab' = runIdentity (rewrite rf tab) where rf (Single 3 Nil) = return (tab', Next) rf t = return (t, Next) -- Running "test5 t1 t3", however, does terminate because the "Cut" -- prevents the traversal from entering the newly spliced subtrees -- that match the pattern. test5 :: (Num t) => Tableau t -> Tableau t -> Tableau t test5 tab tab' = runIdentity (rewrite rf tab) where rf (Single 3 Nil) = return (tab', Cut) rf t = return (t, Next) ------------------------------------------------------------------------- end of code.

2 1

overflow safe Word types
by Ashish Agarwal 30 Mar '10

30 Mar '10

Is there an alternative implementation of the types Word8, Word16, etc. that disallow overflow? For example, currently: Prelude Word> (fromInteger 256) :: Word8 0 I'd like a type whose constructors disallow this.

3 3

[OT] To the Google Group 'fa.haskell' admin.
by aditya siram 29 Mar '10

29 Mar '10

I noticed that my posts to the 'fa.haskell' Google group don't make it to the Haskell-Cafe archives and I suspect they are invisible to the Haskell-Cafe readers. They seem to be visible to only those who are subscribe to the Google Group. Conversely some of the other people's posts to Haskell-Cafe don't appear in the Google group. For instance I posted to this thread: http://www.haskell.org/pipermail/haskell-cafe/2010-March/075250.html and it is not in the Haskell-Cafe archives. And this response by Jeff Wheeler: http://www.haskell.org/pipermail/haskell-cafe/2010-March/075251.html is not visible in the Google Group. As of now I'll stop using the Google group, but I wanted to let someone know. Thanks ... -deech

2 1

Mixing monads?
by Ron Leisti 28 Mar '10

28 Mar '10

I've run into a situation where I need to 'weave' two monads together, but I can't figure out how it's done. The first monad is "Parser a" from Attoparsec, and the second is one that I've created called "CBC a", with the following relevant functions: -- Decrypts a word in cipher-block-chaining mode decryptCBC :: Word128 -> CBC Word128 -- Performs a cipher-block-chaining mode operation with the given -- key and initialization vector. cbc :: Key -> IV -> CBC a -> a I've also defined a special parser for Attoparsec, for extracting the next 128 bit word from the stream: word128 :: Parser Word128 My problem is that I would like to write a function which reads a word, decrypts it, and then uses the result to make a decision about whether to read further words or return a result. So far, I think my function would have a result type of: func :: Parser (CBC foo) but within the function, if I do something like: func = do x <- word128 let r = do y <- decryptCBC x if (predicate y) then return bar else -- somehow read more from the parser? return r But within this function I run into the situation where my types turn into something like Parser (CBC (Parser a)). I have a feeling that I'm just going about this in a wrong way. I realize that I probably don't need to use Parser here, since I'm just reading a stream of words, but I'd still like to learn how to do this in the general case. Is there anyone that could point me in a better direction? Thanks, Ron

3 3

Earth Hour 2010: Will you join me?
by Ivan Vovnenko 26 Mar '10

26 Mar '10

beginners(a)haskell.org, I just signed up to support the Earth Hour 2010 campaign and I'd like to invite you to join me. Just visit https://www.myearthhour.org/home?invite=KozdEiQpor. Earth Hour was conceived by the World Wildlife Fund, and represents the global call to action on climate change. The more people that pledge to turn off their lights for Earth Hour, the more influence we will have. Nearly one billion people around the world turned off their lights for Earth Hour 2009 and we can help make the next one even bigger. Through the flick of a light switch on March 27 at 8:30 pm local time, we'll be casting our vote for action on one of the most pressing issues facing our planet, sending a message to our local, national, and global leaders that the time to act is now. Follow this link to learn more and sign-up yourself. https://www.myearthhour.org/home?invite=KozdEiQpor ---------------- -Ivan Vovnenko ----------------

1 0

Fwd: [Haskell-beginners] SMTPClient + hsemail-1.6 = errors
by Sergey Mironov 26 Mar '10

26 Mar '10

Thanks, Robert. But my real goal was to compile happstack. SMTPClient is just a dependency. I solved the problem with ghc-pkg unregister: ierton@vault ~ % ghc-pkg unregister hsemail-1.6 ierton@vault ~ % cabal install hsemail-1.3 ierton@vault ~ % caball install SMTPClient 2010/3/26 Robert Wills <wrwills(a)gmail.com>: > HaskellNet contains an smtp client as well. > > http://hackage.haskell.org/package/HaskellNet > > It worked last time I checked. > > main = do > con <- connectSMTP smtpServer > let msg = ([("From", "HaskellNet <" ++ sendFrom ++ > ">"),("Subject","Test")], BS.pack "\r\nhello from haskellnet") > sendMail sendFrom sendTo (BS.pack $ show $ showMessage "utf-8" msg) con > closeSMTP con > > Regards, > Rob > > On Thu, Mar 25, 2010 at 11:34 PM, Sergey Mironov <ierton(a)gmail.com> wrote: >> Hi. >> I was trying to install SMTPClient-1.0.1 >> >> Compiler reported me: >> >> ierton@vault SMTPClient-1.0.1 % cabal build >> Preprocessing library SMTPClient-1.0.1... >> Building SMTPClient-1.0.1... >> [1 of 2] Compiling Network.SMTP.ClientSession ( >> Network/SMTP/ClientSession.hs, dist/build/Network/SMTP/ClientSession.o >> ) >> >> Network/SMTP/ClientSession.hs:242:16: >> Not in scope: data constructor `Message' >> >> Network/SMTP/ClientSession.hs:406:15: >> Not in scope: data constructor `Message' >> >> I've made some digging: Seems that newest version of 'hsemail' (1.6) >> breaks backward compatibility (SMTPClient depends on it) >> >> My questions: >> 1) Where should i send bugreport to? >> There are no emails on http://hackage.haskell.org/package/SMTPClient >> so i don't know how to contact maintainers. >> >> 2) How to fallback hsemail? >> i tried: >> >> ierton@vault ~ % cabal install hsemail-1.3 # good, i suppose >> ierton@vault ~ % ghc-pkg hide hsemail-1.6 # Bad one >> ierton@vault ~ % caball install -v SMTPClient >> ... >> ... bla-bla ... >> ... >> selecting hsemail-1.6 (installed or hackage) and discarding hsemail-1.0, 1.1, >> 1.2, 1.3, 1.4 and 1.5 >> ... >> >> Looks like hiding a package is not a case for me. >> >> ps >> >> I am using ghc-6.12 >> >> -- >> Thanks, >> Sergey >> _______________________________________________ >> Beginners mailing list >> Beginners(a)haskell.org >> http://www.haskell.org/mailman/listinfo/beginners >> > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners > -- С Уважением, Сергей. -- С Уважением, Сергей.

3 4

Cygwin error: D:\Haskell\bin/windres: can't open temporary file `\/cca02652.irc': No such file or directory
by remy willems 26 Mar '10

26 Mar '10

I am using cygwin. While in cygwin, when I try to make EHC, the essential haskell compiler, I get the following error: D:\Haskell\bin/windres: can't open temporary file `\/cca02652.irc': No such file or directory strip: 'build/libutil/setup.exe': No such file There are no strange permission in the folder I'm running the make. I'm the administrator and am running cygwin in "run as adminstrator" mode. Could someone help me? I'm really stuck with this. Much appreciated, Remy.

2 2

SMTPClient + hsemail-1.6 = errors
by Sergey Mironov 25 Mar '10

25 Mar '10

Hi. I was trying to install SMTPClient-1.0.1 Compiler reported me: ierton@vault SMTPClient-1.0.1 % cabal build Preprocessing library SMTPClient-1.0.1... Building SMTPClient-1.0.1... [1 of 2] Compiling Network.SMTP.ClientSession ( Network/SMTP/ClientSession.hs, dist/build/Network/SMTP/ClientSession.o ) Network/SMTP/ClientSession.hs:242:16: Not in scope: data constructor `Message' Network/SMTP/ClientSession.hs:406:15: Not in scope: data constructor `Message' I've made some digging: Seems that newest version of 'hsemail' (1.6) breaks backward compatibility (SMTPClient depends on it) My questions: 1) Where should i send bugreport to? There are no emails on http://hackage.haskell.org/package/SMTPClient so i don't know how to contact maintainers. 2) How to fallback hsemail? i tried: ierton@vault ~ % cabal install hsemail-1.3 # good, i suppose ierton@vault ~ % ghc-pkg hide hsemail-1.6 # Bad one ierton@vault ~ % caball install -v SMTPClient ... ... bla-bla ... ... selecting hsemail-1.6 (installed or hackage) and discarding hsemail-1.0, 1.1, 1.2, 1.3, 1.4 and 1.5 ... Looks like hiding a package is not a case for me. ps I am using ghc-6.12 -- Thanks, Sergey

2 1

Memory usage problem
by Sami Liedes 25 Mar '10

25 Mar '10

Hi! I wrote a simple program to parse Debian package list files (a simple text record format), sort the list of packages and output the list. I first wrote the program in C (which I speak fluently), but wanting to learn Haskell, have been trying to reimplement it in Haskell. The problem is that my 60-line Haskell program, which doesn't yet do everything the C program does, uses huge amounts of memory, 1.5 gigabytes when parsing a single file. The C implementation can parse and sort more than twice that data in less than 10 megabytes. I can't figure out where the memory goes or how to fix it, but my guess would be it's some lazy computation thunk. (See below after the code for description of the input and output formats.) With a package file of 28000 records (packages), the memory usage is roughly 1.5 gigabytes when compiled with ghc - under hugs it just bails out quickly after stack overflow - and I'd appreciate help in figuring out 1) Where the memory is actually spent? 2) How would one usually go about figuring this out? and 3) How to fix it? [4) I'd also love style hints and other ideas to make my code more idiomatic] I've tried to randomly add some $! operators to the code (that doesn't feel right :-), but so far to no avail. Here's the code: ------------------------------------------------------------ module Main where import List (sort) import Maybe (fromJust, mapMaybe) -- Parse one line of the format "Field: value". -- Ignore those that start with a space. readField :: String -> Maybe (String,String) readField line = if line == "" || head line == ' ' then Nothing else let (name,':':' ':val) = break (== ':') line in Just (name,val) data Package = Package { name, version :: !String } deriving (Show, Eq, Ord) -- Use sprintPackage for formatted output, show for unformatted sprintPackage :: Package -> String sprintPackage (Package name ver) = name ++ replicate (50 - length name) ' ' ++ ver -- Read one record worth of lines (separated by blank lines) getOneRecordLines [] = ([],[]) getOneRecordLines lines = (hd, if tl == [] then [] else tail tl) where (hd,tl) = break (== "") lines -- Read one record worth of lines and parse, returning (Field, value) -- tuples and the rest of the lines (less the just read record) readRecordFields :: [String] -> ([(String,String)], [String]) readRecordFields lines = (mapMaybe readField rl, rest) where (rl,rest) = getOneRecordLines lines -- Convert a list of (Field,value) tuples to a Package recordFieldsToPackage :: [(String,String)] -> Package recordFieldsToPackage fields = let names = [y | (x,y) <- fields, x=="Package"] vers = [y | (x,y) <- fields, x=="Version"] in case (names,vers) of ([], _) -> error "Package has no name." (a:b:rest, _) -> error ("Package has two names ("++a++","++b++").") ([n], []) -> error ("Package "++n++" has no version.") ([n], a:b:rest) -> error ("Package "++n++" has multiple versions.") ([n], [v]) -> Package n v -- Read one record, returning Just Package if it contained a valid -- package and version, Nothing otherwise. readRecord :: [String] -> (Maybe Package,[String]) readRecord lines = if fields == [] then (Nothing, rest) else (Just (recordFieldsToPackage fields), rest) where (fields,rest) = readRecordFields lines -- Converts the list (stream) of lines to a list of packages readRecords :: [String] -> [Package] readRecords [] = [] readRecords lines = let (rec,rest) = readRecord lines in case rec of Just pkg -> pkg : readRecords rest Nothing -> readRecords rest processFile = unlines . (map sprintPackage) . sort . readRecords . lines main :: IO () main = interact processFile ------------------------------------------------------------ The input (stdin) for the program is of the format: ------------------------------------------------------------ Package: somepackagename Version: someversionstring Other-Fields: ... Whatever: ... ... (lines that begin with space are just ignored) Package: pkg2 Version: otherversion ... ------------------------------------------------------------ That is, the file has records separated by blank lines. Only lines that begin with "Package: " or "Version: " are considered in a record, the others are just ignored. When finished, it outputs a formatted list of packages to stdout: ------------------------------------------------------------ a2ps 1:4.14-1 a2ps-perl-ja 1.45-5 a56 1.3-5 a7xpg 0.11.dfsg1-4 a7xpg-data 0.11.dfsg1-4 aa3d 1.0-8 aajm 0.4-3 aap 1.091-1 aap-doc 1.091-1 ... ------------------------------------------------------------ GHC profiling hints that the memory is spent in processFile and main, but no amount of adding $! to those functions seems to help: ------------------------------------------------------------ Thu Mar 18 22:37 2010 Time and Allocation Profiling Report (Final) aptlistsh +RTS -p -RTS total time = 3.18 secs (159 ticks @ 20 ms) total alloc = 1,873,922,000 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc processFile Main 44.0 61.9 main Main 32.1 20.7 readField Main 11.9 9.0 recordFieldsToPackage Main 4.4 2.0 newPkg Main 3.1 0.8 sprintPackage Main 1.3 2.1 readRecordFields Main 1.3 1.3 CAF Main 1.3 0.4 getOneRecordLines Main 0.6 1.4 ------------------------------------------------------------ Sami

4 7

Call for papers (Deadline Extended): MULTICONF-10, USA, July 2010
by John Edward 24 Mar '10

24 Mar '10

It would be highly appreciated if you could share this announcement with your colleagues, students and individuals whose research is in computer science, computer engineering, information science and related areas. Call for papers (Deadline Extended): MULTICONF-10, USA, July 2010 The 2010 multi-conference (MULTICONF-10) (website: http://www.PromoteResearch.org ) will be held during July 12-14, 2010 in Orlando, Florida, USA. The primary goal of MULTICONF is to promote research and developmental activities in computer science, information technology, control engineering, and related fields. Another goal is to promote the dissemination of research to a multidisciplinary audience and to facilitate communication among researchers, developers, practitioners in different fields. The following conferences are planned to be organized as part of MULTICONF-10. • International Conference on Artificial Intelligence and Pattern Recognition (AIPR-10) • International Conference on Automation, Robotics and Control Systems (ARCS-10) • International Conference on Bioinformatics, Computational Biology, Genomics and Chemoinformatics (BCBGC-10) • International Conference on Computer Communications and Networks (CCN-10) • International Conference on Enterprise Information Systems and Web Technologies (EISWT-10) • International Conference on High Performance Computing Systems (HPCS-10) • International Conference on Information Security and Privacy (ISP-10) • International Conference on Image and Video Processing and Computer Vision (IVPCV-10) • International Conference on Software Engineering Theory and Practice (SETP-10) • International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-10) MULTICONF-10 will be held at Imperial Swan Hotel and Suites. It is a full-service resort that puts you in the middle of the fun! Located 1/2 block south of the famed International Drive, the hotel is just minutes from great entertainment like Walt Disney World® Resort, Universal Studios and Sea World Orlando. Guests can enjoy free scheduled transportation to these theme parks, as well as spacious accommodations, outdoor pools and on-site dining — all situated on 10 tropically landscaped acres. Here, guests can experience a full-service resort with discount hotel pricing in Orlando. Please see the website http://www.PromoteResearch.org for more details. Sincerely John Edward

1 0