March 2007 - Haskell-Cafe

Re: [Haskell-cafe] Lazy IO and closing of file handles
by Bertram Felgenhauer 21 Mar '07

21 Mar '07

Ketil Malde wrote: > Bertram Felgenhauer wrote: > >>> type Subject = String > >>> data Email = Email {from :: From, subject :: Subject} deriving Show > >data Email = Email {from :: !From, subject :: !Subject} deriving Show > ...except that From and Subject are Strings, and thus the strictness > annotation only forces WHNF. I.e., you also need to modify parseEmail > to force these. > > -k You're right. Actually, the program will be strict enough if the From header always precedes the Subject header (which was the case in my tests), but that's not immediately obvious. Modifying getHeader to force its result is the clean solution, say: getHeader = forceString . fromMaybe "N/A" . flip lookup headers forceString s = length s `seq` s Having to rely on GC to close the fds quickly enough is another problem; can this be solved on the library side, maybe by performing GCs when running out of FDs? Bertram

3 3

Is ([] -> []) an arrow?
by Chad Scherrer 21 Mar '07

21 Mar '07

In John Hughes's "Programming With Arrows" (http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf) he discusses a "stream function" type newtype SF a b = SF {runSF :: [a] -> [b]} and gives instance Arrow SF where .... He gives some examples using this, and everything seems to go just fine. But in Ross Patterson's "Arrows and Computation" (http://www.soi.city.ac.uk/~ross/papers/fop.html) he says that newtype ListMap i o = LM ([i] -> [o]) is ALMOST an arrow. Now, I've heard (but never verified) that IO fails to satisfy some monad laws, yet here we are, using it as a monad. Is a similar kind of thing going on here? Has anyone hit any snags in using this instance? Thanks, Chad

2 1

Partial Evaluation
by jim burton 21 Mar '07

21 Mar '07

I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too. This is in the context of optimising performance: "We have used existing partial evaluation techniques to do this...Unfortunately, there does not currently exist a suitable, easy-to-use partial evaluator for Haskell. Our approach was to convert the Haskell program to Scheme, partially evaluate the Scheme program, and then translate back into Haskell." What does P.E, mean here? Thanks, [1] Available http://wiki.ittc.ku.edu/lambda/Image:Hudak-Modular_Domain_Specific_Language…

4 3

There can be only one fix? Pondering Bekic's lemma
by Nicolas Frisby 21 Mar '07

21 Mar '07

Bekic's lemma [1], allows us to transform nested fixed points into a single fixed point, such as: fix (\x -> fix (\y -> f (x, y))) = fix f where f :: (a, a) -> a This depends on having "true products," though I'm not exactly sure what that means. Mutual recursion can also be described with recursion and products f = \a -> ... g a ... g = \b -> ... f b ... can be defined as (f, g) = fix (\knot -> \a -> ... (snd knot) a ..., \b -> ... (fst knot) b ...) My question is: Given products and a fixed point combinator, can any pure expression be transformed into a corresponding expression that has just a single use of fix? If yes, has there been any usage of such a transformation, or is it just crazy? If no, could you provide a counter-example? Thanks for playing along, Nick [1] - Bekic has an entire book, but the most available reference for this I found is Levent Erkök's thesis regarding MonadFix/mfix (pgs 16 and 141). [Also, I cannot figure out how to get the proper symbol above that c in Bekic... sorry about that. I'd appreciate if someone told me how; does Unicode even have it?]

5 6

Design and state...
by Magnus Therning 21 Mar '07

21 Mar '07

Recently I've been hacking together a small Haskell module on top of ptrace(2). It's comming along nicely, but it's very low level. The signals arrive in a list: wait :: Int -> IO [Signal] and processing of the signals can be done using e.g. mapM_: wait childPid >>= mapM_ processSignal In a few cases this low level requires quite a bit of extra code. Code needs to be repeated in every program using the module. Dealing with breakpoints is a good example: - Setting a breakpoint requires storing the old instruction at the address - When hitting a breakpoint the old instruction should be put back, EIP backed up, perform one single-step, and last put the breakpoint back again. I believe adding another layer on top of what I have now seems like a good idea. AFAICS that means having a state (I must keep track of the original instruction). That can easily be done by wrapping IO in a StateT: forEachSignal:: Int -> (Signal -> IO ()) -> StateT DbgEnv IO () forEachSignal childPid procSignal = ... (Or would it be better using IORefs and "OO" in the way described in "IO Inside"[1]?) What I am struggling with is how to allow the user of the module to have state as well. I can see how "OO"[1] can be used to solve it, but is there a more elegant, maybe more idiomatic (Haskellic??), way? Or am I missing a more elegant way of dealing with this? /M [1]: http://haskell.org/haskellwiki/IO_inside#Example:_emulating_OOP_with_record… -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus

2 2

Lazy IO and closing of file handles
by Pete Kazmier 21 Mar '07

21 Mar '07

When using readFile to process a large number of files, I am exceeding the resource limits for the maximum number of open file descriptors on my system. How can I enhance my program to deal with this situation without making significant changes? My program takes one or more directories that contain email messages, stored one per file, and prints a list of all the email threads. Here is a snippet of output: New addition to the Kazmier family Casey Kazmier Memoization in Erlang? Thomas Johnsson Ulf Wiger $AL/EAB$ As a newcomer to Haskell, I am intrigued by lazy evaluation and how it can influence one's designs. With that said, I wrote the program as a sequence of list manipulations which seemed quite natural to do in Haskell starting with reading the contents of the each file. Here is the algorithm at the high level: 1. Read contents of all files returning a list of Strings 2. Map over the list and parse each String as an Email 3. Sort the list of Emails 4. Group the list of Emails by Subject 5. Map over the grouped list to create a list of Threads 6. Finally, print the list of Threads It is my understanding that, as a result of lazy IO, the entire file does not need to be read into memory because parseEmail only inspects the topmost portion of the email (its headers), which is a key part of my design as some of the files can be quite large. Unfortunately, as soon as I run this program on a directory with more than 1024 files, GHC craps out on me due to resource limits. It seems that the handles opened by readFile remain open. Would this be common across all Haskell implementations? How do I go about fixing this without making a significant number of changes to my program? Did I make a mistake in steps 1 and 2 above? Should I have read and parsed a single file at a time, and then move on to the next? I'd appreciate any other comments on the program as well. I feel this is the best example of Haskell code that I have written. Compared to the first version of this program I wrote a few months ago, this is a hundred times better. Here is the program: > module Main where > > import Control.Monad (filterM, liftM) > import Data.List > import Data.Maybe > import System.Directory > import System.Environment > > type From = String > type Subject = String > data Email = Email {from :: From, subject :: Subject} deriving Show > data Thread = Thread [Email] > > instance Show Thread where > show (Thread emails@(e:es)) = title ++ senders > where > title = newline . bolder . subject $ e > sender = newline . indent . from > senders = concatMap sender emails > newline = (++ "\n") > indent = (" " ++) > bolder = ("\27[0;32;40m" ++) . (++ "\27[0m") > > main = > getArgs >>= > mapM fileContentsOfDirectory >>= > mapM_ print . threadEmails . map parseEmail . concat > > fileContentsOfDirectory :: FilePath -> IO [String] > fileContentsOfDirectory dir = > setCurrentDirectory dir >> > getDirectoryContents dir >>= > filterM doesFileExist >>= -- ignore directories > mapM readFile > > parseEmail :: String -> Email > parseEmail text = > Email (getHeader "From") (getHeader "Subject") > where > getHeader = fromMaybe "N/A" . flip lookup headers > headers = concatMap mkassoc . takeWhile (/="") $ lines text > mkassoc s = case findIndex (==':') s of > Just n -> [(take n s, drop (n+2) s)] > Nothing -> [] > > threadEmails :: [Email] -> [Thread] > threadEmails = > map Thread . groupBy (fuzzy (==)) . sortBy (fuzzy compare) > where > fuzzy fn e e' = stripReFwd (subject e) `fn` stripReFwd (subject e') > stripReFwd = stripSpaces . reverse . stripToColon . reverse > stripSpaces = dropWhile (==' ') > stripToColon = takeWhile (/=':')

22 44

toClockTime
by Jeff Polakow 20 Mar '07

20 Mar '07

Hello, On my system, GHC 6.6 running on windows xp, System.Time.toClockTime fails on calendar times later than (by days, I didn't check hours, minutes, etc.) January 18, 2038. Is this a bug? thanks, Jeff --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

4 3

what I learnt from my first serious haskell programm
by Fawzi Mohamed 20 Mar '07

20 Mar '07

Hi everybody, I came to haskell recently (one month) and I have now written my first serious program. I am still busy improving it, but here is a small report of what I learned and and my impressions of the language. I found no show stoppers, but a couple of things that I didn't like much. * namespaces * First off something that disturbed me but does not seem to be discussed much are namespaces, or rather the lack of them. Yes I know that haskell does have namespaces, but with object oriented languages you basically get a namespace for each class, in haskell you need modules, and I often like to have groups of related types in the same module. This might seem like a small issue, but the fact when a program or library grows it gets worse, and for me having a consistent way of calling functions is very important, it lets me spend less time thinking about naming. This is something makes the difference between a set of libraries and well thought out framework. Records then also put everything in the module namespace, and it seems that this misfeature has already been discussed. Anyway the namespaces would not be a problem if one would use always the most specialized function (and throw an error is no such function exist) as for example is done by Aldor ( http://www.aldor.org ) a language with a very nice type system, that unfortunately has been kind of dying for a long time because of its closed source. So I am wondering how people cope with them, share your opinion, for me the best thing seem to be to try to use one module per "big" type, and then "import qualified x as y", what are good coding practices? * space leaks * Sure enough in my program I had a space leak, actually an exponential space leak. The short story: it did bite me, and I think that many people that have problems with the performance in haskell, is because of them. The whole story is that I wanted to find the optimal node at depth n of an infinite tree. I even wrote down the list of the optimal nodes at each depth from which I would take some, but even before compiling it I realized that this would never be efficient. So I passed the maximum depth as argument to the function that generates and immediately reduces the tree. It had a huge space leak, and I knew what was happening, the function wad doing a breath first search of the tree instead of a depth first search, so I put a seq to make it go deeper first. It helped, but a space leak was still there. So I used the profiler, and basically the default profiler is useless for space leaks (it just says the total amount allocated which was constant). After some thinking I finally found out (a posteriori obvious) that I had to fully evaluate the actual node the the depth, and finally return the list. In the meantime I had introduced a couple of seq too much, and also switched to a strict data structure (which helped a little but was not the biggest issue. I really looked into memory profiling after having fixed the problem (but having seen how much work it could be even when you know where the problem is). I tried to use it and I think that it would have been useful, I will see how much with the next bug. With respect to this bibliographical heap profile (+RTS -hb) is broken on my AMD 64 Linux machine with GHC 6.6.20070129, I submitted a bug. * vector & matrices * A thing that bothered me a little was the absence of good standardized vectors and matrices, for now I rolled my own 3x3, I have seen numerical prelude, maybe in the future thre will be a standard interface for matrixes... Rolling my own mattrixes/vectors I have hit against some limitations of classes, nothing terrible, but not so nice, and something that I gather is known for example the fact that you cannot overload + or (in haskell 98) you cannot have overlapping instances. Again (see namespaces problem) changing names for the operations is the way out but it is not so nice. * parallel * For the future I want to make my algorithm parallel using threads (should be easy) . Then I was thinking about being parallel between computers, so to have really make this exercice a test if I really can switch to haskell for my programming, I was thinking about MPI, suggestions? thanks for having read till here :) Fawzi

12 24

Re: [Haskell] Call-by-name: moved to haskell-cafe
by Dan Weston 20 Mar '07

20 Mar '07

Dan Weston wrote: > Douglas Philips wrote: >> On 2007 Mar 20, at 3:30 PM, Dan Weston indited: >> >>> I looked up John Backus on wikipedia and followed a link to ALGOL: >>> http://en.wikipedia.org/wiki/ALGOL_60 >>> where the following "undesirable" property of call-by-name is mentioned. >>> >>> "ALGOL 60 allowed for two evaluation strategies for parameter >>> passing: the common call-by-value, and call-by-name. Call-by-name had >>> certain limitations in contrast to call-by-reference, making it an >>> undesirable feature in language design. For example, it is impossible >>> in ALGOL 60 to develop a procedure that will swap the values of two >>> parameters if the actual parameters that are passed in are an integer >>> variable and an array that is indexed by that same integer variable. >>> However, call-by-name is still beloved of ALGOL implementors for the >>> interesting thunks that are used to implement it." >>> >>> I suppose that call-by-name is still beloved of Haskell implementors >>> as well? >> >> Notice that the "problem" with call-by-name is when side-effects are >> involved. In a pure-functional-environment those "problems" don't >> arise... >> >> --Doug > > It was the phrase "making it an undesirable feature in language design" > that jumped out at me. Here "language" is an implicitly universally > quantified variable, and the phrase beta-reduces to "call-by-name is an > undesirable feature in Haskell design". >

2 1

parsec error message
by david karapetyan 20 Mar '07

20 Mar '07

i get the following error message new.o:fake:(.text+0x85): undefined reference to `parseczm2zi0_TextziParserCombin atorsziParsecziChar_oneOf_closure' new.o:fake:(.rodata+0x4): undefined reference to `parseczm2zi0_TextziParserCombi natorsziParsecziChar_oneOf_closure' collect2: ld returned 1 exit status when compiling the following code module Main where import System.Environment import Text.ParserCombinators.Parsec hiding (spaces) symbol = oneOf "!$%&|*+-/:<=>?@^_~" main = do return 1 any help is greatly appreciated. i am running ghc-6.6 on a windows xp machine.

2 1