October 2003 - Haskell-Cafe

Re: ANNOUNCE: HaRe, the Haskell Refactorer, version 0.1
by ketil＠ii.uib.no 02 Oct '03

02 Oct '03

(taken to -cafe) "C.Reinke" <C.Reinke(a)kent.ac.uk> writes: > Dear Haskellers, > > as part of our project on Refactoring Functional Programs > > http://www.cs.kent.ac.uk/projects/refactor-fp/ > > we are pleased to announce the availability of HaRe 0.1 (also > known as HaRe 01/10/2003 ;-), a snapshot of our Haskell Refactorer > prototype. First, let me say that I'm intrigued. This looks like really neat functionality to have available. I'm curious whether you are planning (or have developed) tools to *detect* cases for refactoring? Occasionally, I find myself wishing for a tool to help me clean up a finished program, by e.g. - removing unused items from export/import lists - identifying functions which are only used in one place (and thus candidate for inclusion in 'where' clauses) - identifying functions defined in one module, but only (mainly?) used by/depending on functions in another module, and thus candidate for cross-module migration. - perhaps similarly, identify function transformation that reduces the parameter lists (i.e. exposed function interface) and so on. (Does that make sense at all? :-) -kzm -- If I haven't seen further, it is by standing in the footprints of giants

2 1

AW: Newbie qustion about monads
by Markus.Schnell＠infineon.com 02 Oct '03

02 Oct '03

> I'm not trying to create useful monads (I'm pretty sure they > aren't :), > but understanding the concepts. So, the question remains: > when the monad > laws say that > > (return x) >>= f == f x The Monad class is just called Monad because it is intended to cover a monad. But it doesn't ensure the laws. That is your sole responsibility. > > what is intended in that "=="? Eq."==" for You can define it to your liking as long as it is commutative. HTH, Markus

3 2

RE: swap leak problem
by Simon Marlow 02 Oct '03

02 Oct '03

> This sounds like a good plan (I do have a ghc build around). > How do I go > about compiling a debugging RTS? Add the following to mk/build.mk: GhcRtsHcOpts = -optc-DDEBUG GhcRtsCcOpts = -g then go into ghc/rts and 'make clean && make'. Now rebuild your program using this GHC (or alternatively add a -L flag pointing to this ghc/rts directory). Then run it with +RTS -DS -Sstderr, observe it going very slowly and see if it throws any assertion failures. Cheers, Simon

2 1

Non-blocking keyboard peek
by Adrian May 02 Oct '03

02 Oct '03

Hi folks, I have simulator which should grind away all night but check the keyboard once per iteration to see if I'm trying to view the results, change parameters or terminate it. Therefore I need a non-blocking keyboard peek function. So far, my searching only lead to some stuff about using threads in GHC but that seems far too complicated and messy. I have no reason to open a new thread and would still have to fight over some resource lock at the very position in the program where I would normally have just peeked at the keyboard and maybe called the menu procedure. I don't think such a peek function would affect referential transparency or be considered gauche for any other reason. Does it really not exist? Can I write it for a reasonable amount of effort? Thanks in advance, AM PS. This is the second of these mails I sent 'cos the first one just didnt show up on the list. ______________________________________________________________________________ Zwei Mal Platz 1 mit dem jeweils besten Testergebnis! WEB.DE FreeMail und WEB.DE Club bei Stiftung Warentest! http://f.web.de/?mc=021183

2 1

RE: Haskell-beginners problem with memory consuption
by Simon Marlow 02 Oct '03

02 Oct '03

> Keep in mind that Strings are lists of characters. I think (somebody > correct me if I'm wrong) GHC will store a character inside a cons > cell, but that still leaves 8 bytes per character. Worst case it will > store the 8-byte cons cell pointing to a 32-bit char value, 12 bytes > per character. (Strings as lists-of-char is very useful, but not > terribly efficient). Worst case: 16 bytes per character, usual case (all characters <= '\xff'): 8 bytes per character, because we have static copies of characters 0-255 in the RTS. Using Data.PackedString or UArray Char: 4 bytes per character. Cheers, Simon

1 0

RE: Lazy IO is useful! [Was: "interact" behaves oddly...]
by Simon Marlow 02 Oct '03

02 Oct '03

> main = > do let mylist = [1..10000] > writeFile "myfile.txt" (unlines (map show mylist)) This part does run in O(1) space and isn't problematic. > -- ... > mylist' <- (map read . lines) `fmap` readFile "myfile.txt" > let result = sum mylist' > print result Indeed, this works by interleaving the I/O and the computation of the result. It is a convenient way to program, because you can use ordinary list operations on the I/O stream. We know it is not "safe": a programmer can observe the fact that implicit I/O is going on. It is also not a good way to program: you have no way to catch errors and take appropriate action if the implicit I/O should fail in some way. Should we really be encouraging the writing of programs that have no error checking? > With lazy IO, this program too should run in constant space, and the > functions that consume the large intermediate structure can remain > unchanged! > > So, I think a lazy programming language should support not only lazy > evaluation, but also lazy IO! When it is appropriate to abstract away > from the details of when IO happens, lazy IO is useful. It can > facilitate separation of concerns and modularity, just like lazy > evaluation. Appropriate lazy IO should not compromise the > purity of the language or be an obstacle to optimistic evaluation. I look forward to seeing a form of lazy I/O that doesn't suffer from these problems! (although I suspect I still won't use it :-p) Cheers, Simon

1 0

SV: SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Thanks for the tip - I will give it a try. PE -----Opprinnelig melding----- Fra: Ketil Malde [mailto:ketil+haskell@ii.uib.no] Sendt: 2. oktober 2003 09:02 Til: Petter Egesund Kopi: 'haskell-cafe(a)haskell.org' Emne: Re: SV: Haskell-beginners problem with memory consuption Petter Egesund <petter.egesund(a)kunnskapsforlaget.no> writes: > fun :: String -> String > look for pat1 in string - if found subst with sub1 > look for pat2 in string - if found subst with sub2 > look for pat3 in string - if found subst with sub3 > recurse until no pattern is found I would structure this as replace :: String -> [String] -> String replace input patterns = ... At each position of input, check for the presence of patterns (use isPrefixOf) and conditionally replace it, else output first char of input and recurse on input's tail. This should make the function "online", so that it can be streamed over a large but lazy list (say a file read with "readFile" -- hurry up before Simon takes it away! :-) without explicitly constructing the whole input or output String. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi & thanks for answering; I should have been more precise, my function works like this: fun :: String -> String look for pat1 in string - if found subst with sub1 look for pat2 in string - if found subst with sub2 look for pat3 in string - if found subst with sub3 recurse until no pattern is found Cheers PE -----Opprinnelig melding----- Fra: Wolfgang Jeltsch [mailto:wolfgang@jeltsch.net] Sendt: 1. oktober 2003 15:36 Til: The Haskell Cafe Emne: Re: Haskell-beginners problem with memory consuption Am Mittwoch, 1. Oktober 2003, 15:18 schrieb Petter Egesund: > [...] > The problem is of course that the string is copied each time I do a > substitute, and I wonder if a more experienced haskeller has a better > solution to my problem. It doesn't have to be a problem that the string is copied each time. If you have, e.g., functions f1, f2, ..., fn :: String -> String and do something like f1 (f2 (... (fn string)...)) then string and the intermediate data can be removed by the garbage collector as soon as they are not needed. Unfortunately, from your message it's not very clear to me what exactly you mean, and, unfortunately again, I'm not an expert in Haskell memory management. > I have myself considered these solutions, but they all seems non-elegant; > [...] Indeed, they all look very non-elegant, and I think, there is a better solution. > Cheers, > > Petter Egesund Wolfgang _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi, I have just started using Haskell, and it has been really fun so far. But I have problems with memory usage when handling large files. What I do is the following; I load my file in one chunk, and does a lot of substitutes on the string - this is quick eating all my memory and the computers start to get really slow. The problem is of course that the string is copied each time I do a substitute, and I wonder if a more experienced haskeller has a better solution to my problem. I have myself considered these solutions, but they all seems non-elegant; 1. Use some IO extensions to fake a mutable variable - but solving a problem like this with a solution which is meant for IO does not seem right? 2. Split the file in smaller parts could be a solution, but then I would have to do a lot of preparsing to make sure I not spilt my file in the middle of a pattern. Sounds to me like developing a lex-like system for such a easy task is overkill? 3. I could maybe use some form of mutable arrays, but doing string regexps on an array...? 4. ? Any clues or opinions? Cheers, Petter Egesund

3 2

Another beginner's memory consumption problem...
by Bayley, Alistair 01 Oct '03

01 Oct '03

I'm trying the add-a-gram challenge from here: http://www.itasoftware.com/careers/programmers-archive.php ... and I'm also experiencing runaway memory consumption. If I load the supplied list of words (a 1.6M file) and search for shorter strings, things are OK. Memory consumption increases dramatically as I search for longer and longer trails. The function searchWord starts with a particular map and searches the maps below it (i.e. those containing shorter words), so when I search for longer trails, a larger number of maps must be examined. When I search for short trails, only a few (2-3 say) of the maps are examined. I think this implies some kind of lazy evaluation problem, but I'm not sure where to go from here. Was it a bad idea to use a Map of Maps as a data structure? Initially I had a list of Maps, but this wouldn't even load the full file (so I suppose lazy evaluation has allowed me to get a bit further...). Maps seemed like the right data structures to use for this problem. Is there some way I could force evaluation of the maps as the file is loaded? (Or is blaming the maps a red herring?) Program below: > module Main where > import Data.FiniteMap > import Data.List > import System.IO Data structure is a Map of Maps. The top-level Map holds Maps indexed by Int (for words of size n). Each of these Maps holds words of that size, where a key is the sorted list of chars for a word, and the value is the list of words whose sorted characters are that key i.e. all words constructed from the same set of characters. > type WordMaps = FiniteMap Int WordMap > type WordMap = FiniteMap String [String] > type MyWord = String ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11) mar + c = cram + h = march + s = charms + o = chromas + n = monarchs + i = harmonics + a = maraschino + n = ANACHRONISM (length 11) ----------------------------------------------------------- > addWordToMap :: String -> WordMap -> WordMap > addWordToMap word m = > case lookupFM m key of > Just wlist -> addToFM m key (word:wlist) > Nothing -> addToFM m key [word] > where key = sort word > addWord :: String -> WordMaps -> WordMaps > addWord word maps = addToFM maps key newmap > where key = length word > newmap = addWordToMap word oldmap > oldmap = case (lookupFM maps key) of > Just m -> m > Nothing -> emptyFM > populateMaps :: WordMaps -> IO WordMaps > populateMaps maps = do > eof <- isEOF > if eof then return maps else do > word <- getLine > if (length word) > 0 -- test for blank lines > then populateMaps (addWord word maps) > else populateMaps maps ----------------------------------------------------------- > getMap :: WordMaps -> Int -> WordMap > getMap maps key = case (lookupFM maps key) of > Nothing -> emptyFM > Just m -> m > showWordList :: [String] -> String > showWordList = concat . intersperse ", " > printTrail :: WordMaps -> [String] -> String > printTrail _ [] = "" > printTrail maps (w:ws) = (showWordList elts) ++ "\n" ++ (printTrail maps ws) > where m = getMap maps (length w) > elts = lookupWithDefaultFM m [""] w > removeEachChar :: String -> [String] > removeEachChar word = removeEachChar' word (length word) [] > removeEachChar' :: String -> Int -> [String] -> [String] > removeEachChar' [] _ list = list > removeEachChar' _ 0 list = list > removeEachChar' word n list = removeEachChar' word (n-1) (newword:list) > where newword = (take (n-1) word) ++ (drop n word) > unfussyHead :: [[String]] -> [String] > unfussyHead [] = [] > unfussyHead l = head l Given a word (and a trail so far) this will return either an empty trail, or a trail to the first 3-char word that completes the search. A trail is just the list of keys, shortest first. > searchWord :: WordMaps -> [String] -> String -> [String] > searchWord maps trail word > | length word <= 3 = word:trail > | otherwise = > case lookupFM m word of > Nothing -> [] > Just _ -> unfussyHead $ filter ([] /=) $ map cont (removeEachChar word) > where cont = searchWord maps (word:trail) > m = getMap maps (length word) For each word (key) in a level, call searchWord. The first to return a non-empty list is the winner. If the list for this level is empty, then recurse with the next level down. > searchLevel :: WordMaps -> Int -> [String] > searchLevel _ 3 = [] > searchLevel maps level = > case (lookupFM maps level) of > Nothing -> [] > Just m -> let result = filter ([] /= ) $ map (searchWord maps []) (keysFM m) in > if result == [] > then searchLevel maps (level-1) > else head result Kick off search at top-level. > start :: WordMaps -> [String] > start maps = searchLevel maps (last (keysFM maps)) Look for a specific trail. For testing/debugging. > findw :: WordMaps -> [String] > findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "nails") findw maps = searchWord maps [] (sort "salient") findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "clarinets") > readWords :: IO String > readWords = do > wordMaps <- populateMaps emptyFM > return (printTrail wordMaps (findw wordMaps)) > -- This is how we'd normally start: > --return (printTrail wordMaps (start wordMaps)) > main :: IO () > main = do > s <- readWords > putStrLn s > return () ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

1 0