- Haskell-Cafe - Haskell.org

Fudgets
by Christian Buschmann 10 Jun '03

10 Jun '03

Hi! Is there any easy way to display an IO String with Fudgets? I know how to display a String: import Fudgets main :: IO () main = fudlogue (shellF "Prog" showMe) showMe = ("Hello " `labLeftOfF` displayF) >==< mapF getString >==< (buttonF "ClickMe!") getString :: Click -> String getString Click = "World!" But if I change the getString-function to: getString :: Click -> IO String getString Click = return "World!" --or any other kind of function which returns an IO String I get an error message. Is there any way, without using unsafePerformIO, to display my IO String? thanks Christian Buschmann

3 3

Powerset
by oleg＠pobox.com 10 Jun '03

10 Jun '03

The following seems to be a faster version of powerset that delivers results strictly in the order of increasing cardinality (i.e., all sets of size 1 first, then of size 2, etc). It seems to run faster than any other ordered version of powerset posted so far. On GHCi, length $ powerset [1..22] is computed roughly 4 times faster than powerset3 given earlier. On Hugs, the powerset below also runs faster, with less memory consumption and in fewer GC cycles, up to a limit of 18 for the size of the input set. Then something happens. length $ powerset3 [1..19] runs out of memory on my (not current) version of Hugs too. The algorithm is more complex, though. Suppose we have a list xs Let powerset_n xs = filter (\p -> length p == n) $ powerset xs Let ps n i = powerset_n $ (tails xs)!!i that is, ps n 0 = powerset_n xs ps n (length(xs)-n) = [(tails xs)!!(length(xs)-n)] that is, i varies from 0 to (length(xs)-n) We observe that ps n (i-1) = ps n i ++ (map (x:) $ ps (n-1) i) where x = xs!!(i-1) Therefore, if we know ps (n-1) i for all i, we can compute ps n i from the base condition ps n (length(xs)-n) = [(tails xs)!!(length(xs)-n)] and then decrementing i. This recurrence is the instance of the right fold psn n psn1 = foldr (\ (psn1i,x) ps@(psni:_) -> (psni ++ (map(x:) psn1i)):ps) [[(tails xs)!!(length(xs)-n)]] $ zip (tail$init psn1) xs We can build ps n from n=0 onwards, given that ps 0 = map (const [[]]) (tails xs) we then observe that (tails xs)!!(length(xs)-n) === (reverse $ tails xs) !! n which, after a few simplifications, gives us import List powerset [] = [[]] powerset [x] = [[],[x]] powerset xs = [] : runit (tail rsxtails) ps0 where xstails = tails xs rsxtails = reverse xstails ps0 = map (const [[]]) $ tail xstails psn tn psn1 = foldr (\ xpsn1i ps@(psni:_) -> (xpsn1i++psni):ps) [[tn]] $ zipWith (\x psn1i -> map (x:) psn1i) xs (init $ psn1) runit [tn] _ = [xs] runit (tn:tns) psn1 = newps0 ++ (runit tns newps) where (newps0:newps) = psn tn psn1 There is still some room for improvement left. Actually, the following is a slightly faster version, showing off lazy evaluation: powerset [] = [[]] powerset [x] = [[],[x]] powerset xs = [] : runit (tail rsxtails) ps0 where xstails = tails xs rsxtails = reverse xstails ps0 = map (const [[]]) xstails psn tn psn1 = psnew where psnew = [tn]: (zipWith (++) (reverse (zipWith (\x psn1i -> map (x:) psn1i) xs (tail $ reverse$tail $ psn1))) psnew) runit [tn] _ = [xs] runit (tn:tns) psn1 = (last newps) ++ (runit tns newps) where newps = psn tn psn1

3 2

RE: Powerset
by Simon Marlow 10 Jun '03

10 Jun '03

> The following seems to be a faster version of powerset that delivers > results strictly in the order of increasing cardinality (i.e., all > sets of size 1 first, then of size 2, etc). It seems to run faster > than any other ordered version of powerset posted so far. On GHCi, > length $ powerset [1..22] is computed roughly 4 times faster than > powerset3 given earlier. On Hugs, the powerset below also runs faster, > with less memory consumption and in fewer GC cycles, up to a limit of > 18 for the size of the input set. Just a word of warning: using GHCi or Hugs for comparison benchmarking will give unreliable results. Use GHC with -O. Cheers, Simon

1 0

RE: Compiling hws with ghc 6
by Simon Marlow 10 Jun '03

10 Jun '03

> I'm trying to compile the haskell web server (from the > haskell-libs project > at sf.net) with ghc6 and I'm stuck on the last function in Util.hs: > > statMaybe filename = do > maybe_stat <- tryJust ioErrors (getFileStatus filename) > case maybe_stat of > Left e -> do > errno <- getErrorCode > if errno == eNOENT > then return Nothing > else ioError e > Right stat -> > return (Just stat) > > > What are the equivalents for getFileStatus and getErrorCode > these days? > > I suppose Foreign.C.Error.getErrno might substitute for > getErrorCode, but I'm stumped on getFileStatus. You're right about getErrno. getFileStatus is available from System.Posix. Cheers, Simon

1 0

Bom dia haskell-cafe
by kandrak 10 Jun '03

10 Jun '03

Message to haskell-cafe(a)haskell.org Ola!!!! haskell-cafe GANHAMOS O PRÊMIO DE MELHOR SITE DO RAMO ======Estamos operando em Novo Formato====== Confira em: escuta21.kit.net ou http://www.escuta21.kit.net ei.... haskell-cafe Cuidado com o que fala ao Celular... ele tb tem ouvidos... para remover o haskell-cafe(a)haskell.org de nossa lista responda este e-mail e coloque remover nos perdoe o transtorno...ok? kandrak

1 0

Re: on termination
by cwitty＠newtonlabs.com 09 Jun '03

09 Jun '03

"Cagdas Ozgenc" <co19(a)cornell.edu> writes: > This may be a little off topic, but I could not get much response from = > comp.theory, so here it goes: > > Is it possible to have a programming language that can be used to = > produce only the programs that terminate, but at the same time decide = > all recursive languages? Or does such limitation automatically reduce = > the class of languages that such a programming language decide to = > primitive-recursive? If you have any programming language (say Haskell), and if you have some formal system which is capable of proving termination properties of programs in your programming language (and in which proofs are machine-checkable), then you can create a new language "Terminating Haskell" simply by pairing each program with a proof of termination. Of course, if you start with a Turing-complete language, then your formal system is necessarily incomplete; this means there will be programs that do terminate but that you cannot prove terminate. So your programming language will include programs that decide all languages that you can prove recursive (in your formal system), but not all recursive languages. However, if your formal system is strong enough, it may be possible to prove termination of all the programs you really care about. Some theorem-proving systems (including ACL2 and PVS) are like this -- within the logic, you can write programs in a Turing-complete language, as long as you can prove termination. (More precisely, the language would be Turing-complete were it not for the termination requirement. In both cases, the "program" portion is fairly distinct from the "proof of termination" portion, so that it does make sense to talk about what the language would be like without the termination requirement.) It has long been a goal of mine to create a Haskell-like programming language where you could mark portions as being guaranteed to terminate. The compiler would prove termination whenever it could, but in cases where the termination proof was too complicated for automatic proofs, the programmer would be required to add an explicit proof of termination. Carl Witty

1 0

Compiling hws with ghc 6
by Alistair Bayley 09 Jun '03

09 Jun '03

I'm trying to compile the haskell web server (from the haskell-libs project at sf.net) with ghc6 and I'm stuck on the last function in Util.hs: statMaybe filename = do maybe_stat <- tryJust ioErrors (getFileStatus filename) case maybe_stat of Left e -> do errno <- getErrorCode if errno == eNOENT then return Nothing else ioError e Right stat -> return (Just stat) What are the equivalents for getFileStatus and getErrorCode these days? I suppose Foreign.C.Error.getErrno might substitute for getErrorCode, but I'm stumped on getFileStatus.

1 0

Please Help!
by David Savimbi 09 Jun '03

09 Jun '03

From: David Jonas Savimbi Johannesburg, South Africa Email: djsavimbi(a)phantomemail.com June 9th, 2003. Dear Sir, It is my humble pleasure to write you this letter irrespective of the fact that you do not know me. However, I got your name through your country business directory here in my search for a reliable and trustworthy person that can assist me confidently. My name is Mr.John Jonas Savimbi. I am the son of Late Dr. Jonas Savimbi from Angola. I am 29 years old and I have got two younger sisters of same blood. Our mother died almost a year ago. We are all fighting for political asylum in South Africa. We cannot find a home in Angola anymore because of the war that our late father fought with the government of Angola until he died in that war. The government of Angola is now mad at us because our late father also wanted to be president and caused the people to fight the war for him because he was the president of UNITA political movement of Angola. So now we are in South Africa and we are suffering too much because we don't have money and the government of South Africa will not give jobs to asylum seekers. I am much concerned about my younger sisters who are finding it very difficult to manage in the situation. But I know that we should not suffer this way. I know that I must not let my younger sisters get into trouble because of money. So after consideration I am hereby begging for your assistance to help me to recover the sum of USD $29 Million which is my inheritance from my late mother. My late mother had taken this money with her to Spain in a diplomatic metal box marked (Precious Stones). Subsequently she lodged the metal box (As precious Stones) with a Securities and Valuables Protection company in Spain. I am supposed to be the beneficiary in the event of her death. However, all effort I made to go Spain to claim was refused by the Spainish embassy. And this was while it was still possible for me to travel. Now I cannot travel anywhere anymore. So in the situation that we are facing now, I must find somebody who can go to the Spain on my behalf. I understand that I will have to transfer my beneficiary rights unto you. I am willing to do so in the hope that you are a God fearing person who will not abandon us after you have the money. So from the bottom of my heart I am giving you 20% of the all the money. Once we have enough to sustain us sufficiently, you may be come our fund manager and invest the rest wisely for us. If you will be kind to assist us, please inform me urgently. Kind regards to you and your family. Sincerely, David Jonas savimbi

1 0

RE: Naive question on lists of duplicates
by Stecher, Jack 08 Jun '03

08 Jun '03

Thanks so much for the reply. On Thu, Jun 06, 2003 at 08:06 PM, Dylan Thurston wrote: > Was there actually a problem with the efficiency of your first code? No -- it was untested, and as I developed more of the code in Haskell, I found that there were slight differences between what I thought we needed to do and what my co-worker had in mind. So, even if my co-worker goes back to writing things in SAS, this has already been helpful for clarifying requirements. In particular, it turns out that he needs to know when promotions overlap for the same SKU, as this is an indication that the data we've received are invalid. I tested the mergeSort to make sure I didn't have any errors, though I used the fairly standard one. It was much faster than a sort in SAS, at least with a PROC SQL, though I ran into size limitations because I had to compile on the Windows side. (We don't have gcc installed on our UNIX side, so ghci will work but ghc won't compile my code.) Since I'm analyzing roughly 600MB of data, I will probably add a step or two in order to chunk the data. In any case, I'm not noticing any obvious inefficiencies, but my Haskell programming is self-taught, and this is my first attempt at solving a real problem at work using Haskell, so I figured I'd get feedback from the list. > (Unless this is really a one-shot deal, I suspect using Ints for dates > is a bad decision...) When I first read this message, I thought, "Well, this really is only a one-shot deal." However, as I thought more about this, I decided that I should write this so that we can use it in case another client comes along with similar data for us to analyze on another project. So I will change this and define a date type, or else I'll read the ghc documentation and learn how to use what's in the time library. > import List(sortBy, insertBy) > > data PromotionRec = PR {sku :: String, store :: String, startDate :: Int, endDate :: Int, amount::Float} As it turns out, the same promotions are always on across all stores. Thus, each SKU/startDate/endDate will seem to have a duplicate promotion. Also, I don't need the amount information, so I wrote the import function so that it would ignore the amount information. One further change: the SKU and store are identified by their number, not their descriptions. The new data type is like this: data PromoRec = PR {startDate, endDate, skuID, storeID :: Int} deriving Show though I will likely implement a better show function and will, as noted above, change the dates to a date type. The file is a fixed-width file, so I just do this: loadData :: Handle -> IO [String] loadData handle = do s <- hGetContents handle return (lines s) toPromoRecs :: [String] -> [PromoRec] toPromoRecs [] = [] toPromoRecs (x:xs) = (PR (read (take 8 x)) (read (take 8 (drop 8 x))) (read (take 20 (drop 16 x))) (read (take 20 (drop 36 x)))) : toPromoRecs xs There's probably a much more clever way to do this, but it seems fairly fast. The file allowed 20 spaces for the SKU and store numbers, but they're at most 7 digits long. Again, I'll need to change the first and second reads to some function that converts a string in the form yyyymmdd into a date type (or I'll need to write one). > compareStart, compareEnd :: PromotionRec -> PromotionRec -> Ordering > compareStart x y = compare (startDate x) (startDate y) > compareEnd x y = compare (endDate x) (endDate y) This is helpful; I'll also need to add a function like this: compareSku :: PromoRec -> PromoRec -> Ordering compareSku x y = compare (skuID x) (skuID y) > overlap :: [PromoRec] -> [[PromoRec]] > overlap l = filter (lambda l. length l > 1) > (overlap' [] (sortBy compareStart l)) > > overlap' _ [] = [] > overlap' active (x:xs) = > let {active' = dropWhile (lambda y. endDate y < startDate x) active} in > (x:active') : overlap' (insertBy compareEnd x active') xs Okay; I see what additional modifications I should make. I need to add a step sort by store and delete duplicate stores where the SKU, start date, and end date are the same. But I should be able to get there from here. > The key is that, by keeping a list of the currently active promotions > in order sorted by the ending date, we only need to discared an > initial portion of the list. Good insight. Many thanks. > You could get a moderately more efficient implementation by keeping > the active list as a heap rather than a list. I had thought about that, and took the BinomialHeap.hs file from Okasaki, but I must have a typo somewhere, because I was having typing clashes that I couldn't easily clarify. At least, when I loaded the BinomialHeap.hs into Hugs, it didn't complain, but when I tried to create an empty heap using the heapEmpty function, Hugs screamed at me. I got scared and fled the scene, retreating into the safety of lists. Thanks again, Jack

2 1

Naive question on lists of duplicates
by Stecher, Jack 07 Jun '03

07 Jun '03

Hi, all. I have an exceedingly simple problem to address, and am wondering if there are relatively straightforward ways to improve the efficiency of my solution. The task is simply to look at a lengthy list of stock keeping units (SKUs -- what retailers call individual items), stores, dates that a promotion started, dates the promotion ended, and something like sales amount; we want to pull out the records where promotions overlap. I will have dates in yyyymmdd format, so there's probably no harm in treating them as Ints. My suggestion went something like this (I'm not at my desk so I don't have exactly what I typed): > data PromotionRec = PR {sku :: String, store :: String, startDate :: Int, endDate :: Int, amount::Float} > > match :: PromotionRec -> [PromotionRec] -> [PromotionRec] > match _ [] = [] > match x (x:xs) = filter (meet x) xs > > nomatch :: PromoRec -> [PromotionRec] -> [PromotionRec] > nomatch _ [] = [] > nomatch x (x:xs) = filter (nomeet x) xs > > meet :: PromoRec -> PromoRec -> Bool > meet x y = and [startDate x <= endDate y, startDate y <= startDate x] > > nomeet :: PromoRec -> PromoRec -> Bool > nomeet x y = not (meet x y) > > overlaps :: [PromoRec] -> [[PromoRec]] > overlaps [] = [] > overlaps (x:xs) = (x : match x xs) : (overlaps (nomatch x xs)) > > overlap :: [PromoRec] -> [[PromoRec]] > overlap [] = [] > overlap (x:xs) = filter g1 (overlaps (x:xs)) where > g1 ys = (length ys) > 1 What I sent might have been slightly different, and I might have some typos in the above (as I'm composing from memory at the keyboard), but that's the rough idea: treat this like a quicksort, pulling out the records that overlap the first record, consing the first record onto the list, and then consing the resulting list onto the same function applied to the records that didn't overlap. As a last step, delete the records that were not on promotion while anything else was on promotion. I'm pretty confident that this will be more efficient than my colleague's SAS code, as he was comparing each record to every other record (giving n (n-1) comparisons). It seems like this, in the worst case where everything is on promotion at distinct times, will compare the first record to (n-1) records, the second to (n-2) records, etc., giving n (n-1)/2 comparisons. Thus, while this is worst-case O(n^2), it seems like it should have at most half as much work to do as the earlier approach in SAS. On the other hand, in the best case, when everything is on promotion at the same time, there should be something like n-1 comparisons made and then that should be it. So it seems like, depending on how frequently promotions co-occur for this retailer, the above should be somewhere between O(n) and O(n^2) time complexity. Since these people are always having some sale or other, I suspect this won't be much worse than O(n log n). Is there anything that is an obvious improvement in efficiency -- some clever tricks with the fold functions, some way of loading the data into some sort of convenient structure first, etc -- that I could easily implement? Please share your thoughts. Many thanks, Jack Stecher jack.stecher(a)retek.com

4 3