- Haskell-Cafe - Haskell.org

subscribe
by Leif Eriksen 09 Apr '02

09 Apr '02

Leif Eriksen Software Engineer AusRegistry Pty Ltd Level 12, 10 Queens Rd. Melbourne, Victoria. Australia 3004. Ph: +61 3 9866 1990 Fax: +61 3 9866 1970 Email: leif(a)ausregistry.com.au Web: www.ausregistry.com.au Registrars: www.ausregistry.net.au

1 0

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

08 Apr '02

> > I don't think so. I think it only takes linear time to get the head. > But once you've gotten the head, it takes linear time again to get the > head of the tail, .... You get (I think...) a progression like > n+(n-1)+(n-2)+...+1, which is in O(n^2). > What does 'n' denote? The get the head, it takes time proportional to the number of (++) invocations. Is that what you mean? konst

2 1

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

08 Apr '02

This one helped. Thanks. 'reduction' was the key word that made it clear for me. It is not that left associated (++) reconstructs the list once and again (although one can say that) it is just that to return the head from the recursive invocations takes quadratic number of reductions. Right? konst > -----Original Message----- > From: Jay Cox [mailto:sqrtofone@yahoo.com] > Sent: Sunday, April 07, 2002 11:09 AM > To: Konst Sushenko > Cc: haskell-cafe(a)haskell.org; Jon Fairbairn > Subject: Re: if (++) were left associative ? > > > On Sun, 7 Apr 2002, Jon Fairbairn wrote: > > > The answer is that you have to evaluate ((([] ++ [1]) ++ > > [2]) ++ [3]) before you can find it, and to get that, you > > have to evaluate (([] ++ [1]) ++ [2]) and so on. > > > > > > In the other case, you can get the head of (a:...)++ (b ++ > > c) by evaluating only the first steps of the first (++). > > > > > > Does that help? > > > > Jón > > > > > Just to add a bit. "evaluate" is such a fuzzy word, > especially in a lazy > language. You must know the context of the expression in > order to know > how much of it is actually evaluated*. > > (* Eventually, the context of all expressions in haskell will be the > evaluation of something in the IO monad, but generally you don't > have to go that far in your reasoning about contexts and stuff.) > > > Ok. I shall now attempt to explain a bit more deeply the differences > between the evaluation expressions which use a left associative append > versis expressions uing a right associative append. > > > > > > In the following,"tail" means any arbitrary tail of a list. > Also, for the > sake of argument, assume : binds closer than ++ and function > application > so we dont have to mess with so many damn parentheses. (in > reality I don't > think anything binds closer than function application in Haskell.) > > the definition of ++ is like > > [] ++ b = b > (l:ls) ++ b = l:(ls++b) > > > applist = ((w:tail ++ x:tail) ++ y:tail) ++ z:tail > > This can be rewritten as the following, so we can litterally see > the leftmost-outermost-reduction. > > applist = (++) ((++) ((++) w:tail x:tail) y:tail) z:tail > > ick! lets say f=(++) (or that f is the same function as the append > operator (++)) > > applist = f (f (f w:tail x:tail) y:tail) z:tail > > > > Alright. Now say we want the head of this applist. So lets use > the head function. > > head patern matches against that thing, causing > a reduction of the outmost f. Since f > pattern matches against its first arguement, > it must cause a reduction in the second f > in that expression, and likewise the third f. > The third f will succeed in its pattern match, > namely (w:tail). > > Now, f, which was (++), will get unfolded. > using the original definition of (++) > (l:ls) ++ b = l:(ls++b) > > this becomes > (w:tail) ++ (x:tail) = w:(tail ++ x:tail) > > (which in our notation is w:(f tail x:tail)) > > substuting our unfolding back into applist and continuing with > reductions: > > f (f (f w:tail x:tail) y:tail) z:tail > -> f (f w:(f tail x:tail) y:tail) z:tail > -> f w:(f (f tail x:tail) y:tail) z:tail > -> w:(f(f(f tail x:tail) y:tail) z:tail) > > so its not like it will take length (w:tail) + length (x:tail) + > length(y:tail) reductions or whatever, but it does take > 3 reductions to get to the head, AND WILL BY NECESSITY take 3 > reductions to get each element of the rest of the tail of w:tail. > > I >think< in the end, if you need all of applist, you will need > something like > > 3*length (w:tail) + 2*length(x:tail) + length(y:tail) > > reductions of f. > > That is definitely NOT linear with > (length x:tail) + (length y:tail) + (length z:tail) > > > > > Now. Lets try go get the head of > > w:tail ++ (x:tail ++ (y:tail ++ z:tail)) > > doing like before with (++), that is > > f w:tail (f x:tail (f y:tail z:tail)) > > and now f pattern matches, etc. > > > ->w:(f tail (f x:tail (f y:tail z:tail))) > > > and thats the ONLY reduction necessary. > > getting all of applist should only require something close to > > (length x:tail) + (length y:tail) + (length z:tail) > > reductions of f. > > > > I'm sure I'm not %100 accurate here, (and It's not worth the effort > for this message!) but I hope this gives more insight and not > more confusion! > > Cheers, > > > Jay Cox > > >

2 1

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

08 Apr '02

Thanks, but it still does not help... > Well, you've removed the parentheses that give you the > information you want. > Yes, I overlooked the parentheses. I meant what you said below: > foldl (++) [] [[1],[2],[3],[4]] ... > -> (((([] ++ [1]) ++ [2]) ++ [3]) ++ [4]) > > now you have to ask what has to be evaluated in order to get > the head of the result. > > The answer is that you have to evaluate ((([] ++ [1]) ++ > [2]) ++ [3]) before you can find it, and to get that, you > have to evaluate (([] ++ [1]) ++ [2]) and so on. > I understand that I have to evaluate all that to get the head of the result, I just do not see how this ends up being quadratic. I have no problem seeing that if each function's argument had to be evaluated before the function is called but this is not the case here, right? To simplify, lets have (([] ++ [1]) ++ [2]) ++ [3]. To get the head of result (++) is called recursively three times. The last invocation returns [1] because its left argument is []. The invocation before it (... ++ [2]) receives [1], and can return (1:..) now, so it does. It does not finish constructing its whole result before something is returned to (... ++ [3]). Here is the root of my misunderstanding. The way I see it is that every time an element is output by (++) at the bottom of the invocation chain, it is propagated up the chain. No? konst

2 1

Re: Parsec: No newline after last line and 'many'
by Iavor Diatchki 08 Apr '02

08 Apr '02

hello, does this work? > pLine = many (noneOf "\n") > pLines = pLine `sepEndBy` char '\n' bye iavor On Sun, Apr 07, 2002 at 07:44:42PM +0200, Till Doerges wrote: > Hi folks, > > when trying to write a parser for unix-style textfiles, I stumbled > across the problem having to distinguish between lines w/ a newline > character at the end and lines w/o a newline at the end (i.e. the last > line in a file doesn't have to have it). > > Eventually I want to be able to use my parser 'linep' with 'many' on > no matter which text-files. > > The first version I tried, was > > --- snip --- > skip1 :: Parser() > skip1 = do > anyChar > return() > > linep :: Parser(String) > linep = do { cs <- many (noneOf "\n") > ; skip1 > ; return cs > } > --- snap --- > > Well, this only works, if the last line in the file is also terminated > by '\n'. So, I tried to be smarter using: > > --- snip --- > lineWith :: Parser(String) > lineWith = try (do { cs <- many (noneOf "\n") > ; skip1 > ; return cs > }) > > lineWithOut :: Parser(String) > lineWithOut = many anyChar > > linep :: Parser(String) > linep = lineWith > <|> lineWithOut > <?> "line" > --- snap --- > > But this doesn't do the trick either, instead it'll overflow my stack > if used in conjunction w/ 'many': > > --- snip --- > parse (do {many linep}) "stdin" (unlines ["hallo","ballo"]) > ^CInterrupted. > ReadOrig> parse (do {many linep}) "stdin" ("hallo\nballo") > ^CInterrupted. > --- snap --- > > Avoiding many OTOH works fine: > --- snip --- > parse (do {linep;linep}) "stdin" (unlines ["hallo","ballo"]) > Right "ballo" > ReadOrig> parse (do {linep;linep}) "stdin" ("hallo\nballo") > Right "ballo" > --- snap --- > > Besides these two attempts explicitly spelled out I've made quite a > few others, but none of them did the trick. > > The documentation for 'try' says that it'll only consume input upon > success, but why doesn't it work w/ 'many'? > > I know about the Prelude-functions unlines, lines etc., but they don't > really help, since linep should be used within another parser of mine. > > I am using Parsec as of Jan 25, 2001 (the version included w/ ghc 5.02). > > Any hints/solutions/... would be greatly appreciated! > > Bye -- Till > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell -- ---------------------------------------+---------------------------------------- Iavor S. Diatchki | email: diatchki(a)cse.ogi.edu Dept. of Computer Science | web: http://www.cse.ogi.edu/~diatchki OGI School of Science and Engineering | work phone: 5037481631 OHSU | home phone: 5036434085 ---------------------------------------+----------------------------------------

1 0

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

08 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 05 Apr '02

05 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