April 2002 - Haskell-Cafe

RE: if (++) were left associative ?
by Konst Sushenko 07 Apr '02

07 Apr '02

Thanks, but you are assuming that foldl evaluates the intermediate result right away. If it were, then I have no problem seeing why time is quadratic. I am concerned about laziness though... My understanding of foldl is thus: foldl (++) [] [[1],[2],[3],[4]] -> foldl (++) ([] ++ [1]) [[2],[3],[4]] -> foldl (++) ([] ++ [1] ++ [2]) [[3],[4]] -> foldl (++) ([] ++ [1] ++ [2] ++ [3]) [[4]] -> foldl (++) ([] ++ [1] ++ [2] ++ [3] ++ [4]) [] -> [] ++ [1] ++ [2] ++ [3] ++ [4] Which brings me back to my original question... > -----Original Message----- > From: David Feuer [mailto:dfeuer@cs.brown.edu] > Sent: Sunday, April 07, 2002 3:21 AM > To: haskell-cafe(a)haskell.org > Subject: Re: if (++) were left associative ? > > > On Sun, Apr 07, 2002, Konst Sushenko wrote: > > Hello, > > > > this is probably embarrassing, but I just realised that I do not > > understand why list concatenation operation takes quadratic > time if it > > is associated from left to right (see e.g. 'The Haskell School of > > Expression' by Hudak, p. 335): > > > > cat1 = (++) > > cat2 = (++) > > > > ( [1,2] `cat1` [3,4] ) `cat2` [5,6] > > > > > > My understanding is that cat2 is invoked before cat1, and > as soon as the > > first element of cat1 is available, cat2 starts building > its own result. > > cat2 does not need to wait until the whole list is emitted > by cat1, does > > it? Where is quadratic time complexity? > > Suppose we define > > listseq [] x = x > listseq (a:b) x = listseq b x > > l = [1..n] > > inter = foldl (++) [] (map (:[]) foo) > > final = listseq inter inter > > > Then inter will be the result of concatenating [1],[2],[3],... from > left to right. One meaningful question is: how long will it take to > calculate "final"? This is (I believe) called the _shared cost_ of > inter (while inter does not actually do any significant work, it > produces a chain of suspensions that together do quite a > bit.... I'm not > sure if the way they are chained still allows this to be > considered the > shared cost, but I'm not sure). > > 1. How long does it take to calculate final ? > Well, let's try it for n = 4: > > inter = foldl (++) [] [[1],[2],[3],[4]] > = foldl (++) ([]++[1]) [[2],[3],[4]] = foldl (++) [1] > [[2],[3],[4]] > = foldl (++) ([1]++[2]) [[3],[4]] = foldl (++) [1,2] [[3],[4]] > = foldl (++) ([1,2]++[3]) [[4]] = foldl (++) [1,2,3] [[4]] > = foldl (++) ([1,2,3]++[4]) [] = foldl (++) [1,2,3,4] [] > = [1,2,3,4] > > Note that in successive iterations, the following are calculated: > > []++[1] > [1]++[2] > [1,2]++[3] > [1,2,3]++[4] > > Since l1++l2 takes order length(l1), each concatenation takes > more time > than the previous one (linearly), so the total time for all of them is > quadratic. >

3 2

Re: Lambda over types.
by anatoli 07 Apr '02

07 Apr '02

(Redirected from haskell to haskell-cafe.) Well, I tried to fix the problems you mention. Results attached. I have managed to do without de Brujin notation. The evaluator is (modulo bugs!) normal order. One can easily do an applicative order evaluator as well. Evaluating to WHNF is probably easy too (this is what the previous version supposed to do). I'll try to come up with a regression test suite for this stuff as my (copious :) free time permits, but on the surface it looks ok. --- oleg(a)pobox.com wrote: > > > anatoli <anatoli at yahoo> wrote: > > > This is all, of course, of purely academical interest. The notation > > is extremely inconvenient to do any real work. I'd rather prefer > > a real, language-supported lambda over types. > > > Or... wait a minute! You did find all those problems; does it mean > > you tried to *use* this stuff for something? Just curious. > > I must start with a profuse apology, because what follows is perhaps > of little relevance to the list. I also propose to re-direct the > follow-ups to the Haskell Cafe. > > I have examined your code and then tried a few examples, some of which > from my code's regression tests. > > I have implemented a compile-time lambda-calculator, in a different > language. I should say, in a meta-language. The output of the > evaluator is a term that can then be compiled and evaluated. The > lambda-calculator acts as a partial evaluator. The calculator > normalizes a term in a pure untyped lambda calculus. The result is > compiled and evaluated in a call-by-value lambda-calculus with > constants. > > Haskell typechecker (augmented with multi-parameter classes with > functional dependencies and let on loose) may do something similar. > > BTW, the meta-language lambda-evaluator code (with the regression tests) > can be found at > http://pobox.com/~oleg/ftp/Computation/rewriting-rule-lambda.txt > The calculator is implemented in CPS, in some sort of extended lambda > calculus. Therefore, the code has three kinds of lambdas: of the source > language, of the transformer meta-language, and of the target > language. The first and the third lambdas are spelled the same and > are the same. > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell __________________________________________________ Do You Yahoo!? Yahoo! Tax Center - online filing with TurboTax http://taxes.yahoo.com/

2 2

if (++) were left associative ?
by Konst Sushenko 07 Apr '02

07 Apr '02

Hello, this is probably embarrassing, but I just realised that I do not understand why list concatenation operation takes quadratic time if it is associated from left to right (see e.g. 'The Haskell School of Expression' by Hudak, p. 335): cat1 = (++) cat2 = (++) ( [1,2] `cat1` [3,4] ) `cat2` [5,6] My understanding is that cat2 is invoked before cat1, and as soon as the first element of cat1 is available, cat2 starts building its own result. cat2 does not need to wait until the whole list is emitted by cat1, does it? Where is quadratic time complexity? konst

2 1

please help me
by Eric 07 Apr '02

07 Apr '02

Hi there, I am a beginner a haskell,and I have some difficulty in dealing with an assignment that is to translate a string representation of a list of appointments into a list of appointments. For example: strToApps "! 10-11 lecture 12-13 lunch at the refec :(" Would yield: [((10,11),"lecture",True), ((12,13),"lunch at the refec :(",False)] "!" is used to determine that appointment is important or not I have done some work,those are: > type Date = (Day,Month,Year) -- e.g. (1,1,2000) = 1/1/2000 > type Year = Int > type Month= Int > type Day = Int > type Hour = Int > type Minute = Int > type Time = Hour -- only times on the hour for now > type Appointment = (Duration, Note, Important) > type Duration = (Time,Time) -- e.g. (13,14) = 1-2pm, forall (s,f) in Duration: s < f > type Note = String > type Important = Bool > strToApps :: String -> [Appointment] > strToApps s = How can I finish the requirement make use of library functions such as words, unwords, lines and break. I am eager to receive your help, thank you very much. Best Wishes Leo =================================================================== ÐÂÀËÃâ·Ñµç×ÓÓÊÏä (http://mail.sina.com.cn) ÐÂÀË·ÖÀàÐÅÏ¢£º¶þÊÖÊÐ³¡×ßÒ»×ß£¬žÃ³öÊÖÊ±ŸÍ³öÊÖ£¡ (http://classad.sina.com.cn/2shou/)

3 3

Ex 9.9 in Paul Hudak's book
by Ludovic Kuty 04 Apr '02

04 Apr '02

The exercise is short. First, he defines a "fix" function: fix f = f (fix f) Which has the type (a -> a) -> a Then the function "remainder": remainder :: Integer -> Integer -> Integer remainder a b = if a < b then a else remainder (a - b) b The function fix, has far as i understand the matter, has no base case. So if someone wants to evaluate it, it will indefinitely apply the function f to itself, leading the hugs interpreter to its end. That's ok. But next he asks the reader to rewrite the function remainder using fix and i cannot find out how. I tried something like: remainder2 a b = fix (\x -> x - b) but there is no base case too. As soon as the lambda expression wants to evaluate its argument, the interpreter crashes. Can someone help me to solve the problem ? TIA Ludovic Kuty

5 8

newbie:: getting random Ints
by Peter Rooney 04 Apr '02

04 Apr '02

hello all, total newbie to haskell, armed with "the craft of functional programming". i can't seem to generate random numbers. i have read this: http://www.haskell.org/onlinelibrary/random.html and searched the web and archives, and read thru Random.hs (mostly over my head), but have been unable to get any combination of getStdRandom randomR, etc. to work. even the example in the 98 report, import Random rollDice :: IO Int rollDice = getStdRandom (randomR (1,6)) gets me: Main> rollDice Main> after loading the file, which makes me think i'm missing something! TCFP has an example of how to do it yourself, but i can see that my needs are more than met by Random.hs. my various attempts all look a lot like this: Main> getStdGen (random 5) ERROR - Type error in application *** Expression : getStdGen (random 5) *** Term : getStdGen *** Type : IO StdGen *** Does not match : a -> b could someone post an example of how to generate random integers within a range? tia, peter

5 5

Re: hashmap withdrawal and poor haskell style
by Long Goodbye 04 Apr '02

04 Apr '02

module Main where main = do content <- getContents let starstat = oneline content alphabet = ['a'..'z'] count ch = length . filter (==ch) oneline str ch = [ch] ++ " " ++ stars (count ch str) stars x = take x ['*','*'..] sequence $ map (putStrLn . starstat) alphabet Just another example ... I thought you might like an example close to your original code _________________________________________________________________ Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.

1 0

hashmap withdrawal and poor haskell style
by Michal Wallace 04 Apr '02

04 Apr '02

Hello everyone, I just wrote my first haskell program. I started with a simple python program and tried to see if I could port it to haskell. The program reads text from stdin and prints out a histogram of all the letters: """ alphabet = 'abcdefghjiklmnopqrstuvwxyz' def letter_count(lines): res = {} for line in lines: for char in line.lower(): if char not in alphabet: continue if res.has_key(char): res[char] += 1 else: res[char] = 1 return res if __name__=="__main__": import sys hist = letter_count(sys.stdin) for letter in alphabet: print letter, "*" * hist.get(letter, 0) """ Kid stuff, but it took me about 10 hours to port it... :) Here's what I came up with: """ module Main where alphabet = "abcdefghijklmnopqrstuvwxyz" count ch str = length [c | c <- str , c == ch] hist str = [count letter str | letter <- alphabet] oneline ch str = [ch] ++ " " ++ stars (count ch str) stars x = if x == 0 then "" else "*" ++ stars ( x - 1 ) report str ch = do putStrLn ( oneline ch str ) loop f (h:t) = if t == [] then f h else do f h loop f t main = do content <- getContents let rpt letter = report content letter loop rpt alphabet """ Other than ignoring upper case letters, and being really really slow, it seems to work fine in hugs.... One thing I really missed was a hash / dictionary. I tried for about an hour to use Assoc following the examples from PLEAC: http://pleac.sourceforge.net/pleac_haskell/hashes.html ... But I never got it working: :> module Main where :> import Assoc (empty) :> main :: IO() :> main = do line <- getContents :> let w = length line :> count:: AssocDefault String Int :> count = w.foldl (\a s -> a.update s (+1)) empty :> print x -> ERROR "alphahist.hs":6 - Undefined type constructor "AssocDefault" (I couldn't get Assoc to work either, even with "Import Assoc (Assoc)" though I looked in the Assoc.hs file and could see it in there.. This was the most frustrating part of the experiment) Can anyone point me in the right direction here? Also, I'd really like to here anyone's thoughts on the code I have above, especially concercing what I could have done better. :) Thanks! Cheers, - Michal http://www.sabren.net/ sabren(a)manifestation.com ------------------------------------------------------------ Give your ideas the perfect home: http://www.cornerhost.com/ cvs - weblogs - php - linux shell - perl/python/cgi - java ------------------------------------------------------------

8 10

Re: hashmap withdrawal and poor haskell style
by Yoann Padioleau 03 Apr '02

03 Apr '02

Remi Turk <remi(a)abcweb.nl> writes: > > -------------------- > module Main where > > import Char > import FiniteMap > > printCount :: (Char, Integer) -> IO () > printCount (letter, count) > =3D putStrLn $ letter : replicate count '*' > > countLetters :: String -> [(Char, Integer)] > countLetters letters > =3D fmToList $ addListToFM_C (+) emptyFM $ zip letters (repeat 1) > > main =3D getContents >>=3D mapM_ printCount . countLetters . filter isAl= > pha this is not exactly the same semantic than the python version, for example if 'z' is not in the contents, then you will not display 'z' (without star) and you will not respect also the order of the letter (i think) > -------------------- > > Happy Hacking > > Remi > > --=20 > See the light and feel my warm desire, > Run through your veins like the evening sun > It will live but no eyes will see it, > I'll bless your name before I die. > > Key fingerprint =3D CC90 A1BA CF6D 891C 5B88 C543 6C5F C469 8F20 70F4 > > --wRRV7LY7NUeQGEoC > Content-Type: application/pgp-signature > Content-Disposition: inline > > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.0.6 (GNU/Linux) > Comment: For info see http://www.gnupg.org > > iD8DBQE8qzpFbF/EaY8gcPQRAm8DAJ44i0avXmnavtDu+OOy1mdrBL88HwCfWsx+ > GFJUUd1zm1wV8CwfqU2TN0k= > =X3DP > -----END PGP SIGNATURE----- > > --wRRV7LY7NUeQGEoC-- > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**

1 0

��һ��ϲ!!��88Ԫ.��!
by ��һ��ϲ!! 03 Apr '02

03 Apr '02

尊敬的用户：　　您好！　　这是来自优联网络有限公司的问侯。感谢您收看这封邮件。厦门优联网络是国内大型域名注册商及主机提供/服务商，免费为代理客户提供域名在线实时注册系统及主机在线申请服务。公司自成立以来，坚持以“优质的服务，合理的价格”赢得了广大客户的赞誉！在同等服务下，我们承诺让您拥有全国最低的代理价格，使您在市场中更具竞争力！详情请浏览:http://www.b68.com email:web@b68.com 谢谢！　　公司自1999年起全力进军国际互联网服务领域，整合推出了以下产品，全面满足您的需求。这将会是您超值的选择。　　1.30M空间＋50M企业邮箱＋1个国际域名，功能全面，仅售200元/年。　　2.50M空间＋50M企业邮箱＋1个国际域名，功能全面，仅售250元/年。　　3.100M空间＋100M企业邮箱＋1个国际域名，功能全面，仅售318元/年。　　4.100M空间+100M邮箱＋1个国际域名+各种风格模板网站+大型网站免费宣传企业信息仅售1000元详细请浏览网站:http://www.wto-china.com 　　尽管我们尽力为您提供最好的服务。，但不排除出现失误。如果是这样，我们宁愿接受退款，也不会因为哪怕一点点的不满意而让您不开心。所以我们承诺：主机不满意按实际余额退款。　　祝：开心！顺利！　　　　　　　　　　　　　　　　　　　　　　　　　 http://www.b68.com 厦门优联网络有限公司　　　　　　　　　使用极星邮件群发，无须通过邮件服务器，直达对方邮箱，速度绝对一流！下载网址：http://www.lovexin.com，更多免费的超酷软件等你来下…… ---------------------------------------------------- INFORMATION This message has been sent using a trial-run version of the TSmtpRelayServer Delphi Component. ----------------------------------------------------

1 0