- Haskell-Cafe - Haskell.org

what's the definition of "satisfy" and "<?>" ?
by z_axis＠163.com 21 May '09

21 May '09

I cannot understand the following code very well as i donot know the definition of "satisfy" and "<?>". -- | Case-insensitive variant of Parsec's 'char' function. caseChar :: Char -> GenParser Char a Char caseChar c = satisfy (\x -> toUpper x == toUpper c) -- | Case-insensitive variant of Parsec's 'string' function. caseString :: String -> GenParser Char a () caseString cs = mapM_ caseChar cs <?> cs Would somebody mind to explain the code in detail ? Sincerely!

3 2

Re: [Haskell-cafe] showing a user defined type
by michael rice 21 May '09

21 May '09

Thanks for the extra patience. What does "unsafe" mean? From my perspective, you had a perfectly good chain_take function fun chain_take(0,_) = nil | chain_take(n,Link(i,f)) = i :: chain_take(n-1,f(i)) - chain_take(5,always1(6)); val it = [1,1,1,1,1] : int list Putting aside weird_chain_take for now, what, if anything, is unsafe about chain_take? Michael --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Wednesday, May 20, 2009, 2:21 PM Actually, I was saying that "chain" already emulates laziness, just in a somewhat unsafe way, as demonstrated by weird_take. In Haskell you'd probably just write > ints :: Int -> [Int] > ints n = [n..] and be done with it. -- ryan On Wed, May 20, 2009 at 9:41 AM, michael rice <nowgate(a)yahoo.com> wrote: > OK, I think I understand. You were explaining how ML could be made to > emulate Haskell laziness using streams, ala Scheme type delayed evaluation, > so it's kind of like you were explaining a question I hadn't quite asked > yet, which maybe explains my puzzlement, I hope. > > Also, though my understanding of both Haskell and ML syntax is still > rudimentary, I did catch an error in your definition of chain_take: the > first arg of the cons should be i rather than n. > > I'm still going through your code and may have further questions. > > Thanks for your input. > > Michael > > > --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > > From: Ryan Ingram <ryani.spam(a)gmail.com> > Subject: Re: [Haskell-cafe] showing a user defined type > To: "michael rice" <nowgate(a)yahoo.com> > Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, > haskell-cafe(a)haskell.org > Date: Wednesday, May 20, 2009, 4:12 AM > > (Apologies for my mutilation of ML syntax, I don't completely know the > language) > > Consider the ML type int list, and this function to build one: > > broken_repeat :: int -> int list > broken_repeat n = Cons(n, broken_repeat(n)) > > This function is recursive, and doesn't terminate; it tries to build > an infinite list of ints and your computer runs out of heap and/or > stack trying to evaluate it. > > But the "chain" type doesn't have this problem; you can see it as an > int list that gets evaluated "on demand": > > repeat :: int -> chain > repeat(n) = Link(n, repeat) > > always1 :: int -> chain > always1(_) = Link(1, always1) > > chain_take :: int * chain -> int list > chain_take (0,_) = Nil > chain_take (n,Link(i,f)) = Cons(n, chain_take(n-1, f(i))) > > But, nothing in the "chain" type stops you from passing a different > value to the function in the link: > > weird_take :: int * int * chain -> int list > weird_take (0,_,_) = Nil > weird_take (n,v,Link(i,f)) = Cons(i, weird_take(n-1,v,f(v))) > > Now, it's possible that chain_take returns the same list for two > different "chain" inputs, but weird_take might return different lists > depending on how f is implemented. For example: > chain_take(5, repeat(1)) = [1,1,1,1,1] > chain_take(5, always1(1) = [1,1,1,1,1] > > weird_take(5, 2, repeat(1)) = [1,2,2,2,2] > weird_take(5, 2, always1(1)) = [1,1,1,1,1] > > One way to fix this is to embed the "state" of the chain in the closure > itself. > > So, in ML, the type > unit -> X > is commonly called a "thunk"; it can be used to delay computation > until later, until it's demanded, just like any lazy value in Haskell. > > f :: unit -> Int > f () = 1 > > This f isn't very useful; it's basically the same as "1". But > consider this type: > > datatype stream = Stream of (int * (unit -> stream)) > > stream1 () = Stream(1, stream1) > > stream_take :: int*stream -> int list > stream_take(0,_) = Nil > stream_take(n,Stream(i,f)) = Cons(i, stream_take(n-1, f())) > > Now there is no way to pass a different value like we did in > weird_take; there's only (). > > The difference is that the state gets embedded in the closure for the thunk: > > stream_ints :: int -> (unit -> stream) > stream_ints = fun n => fun () => Stream(n, stream_ints(n+1)) > > What you are doing here is encoding laziness; the Haskell version of this > type: > >> data Stream = Stream !Int Stream -- !Int means the Int value is strict >> stream1 = Stream 1 stream1 >> stream_ints n = Stream n (stream_ints(n+1)) > >> stream_take :: Int -> Stream -> [Int] >> stream_take 0 _ = [] >> stream_take n (Stream x xs) = x : stream_take (n-1) xs > > No extra (\() -> ...) thunk is required, due to laziness :) > > -- ryan > > On Tue, May 19, 2009 at 4:25 PM, michael rice <nowgate(a)yahoo.com> wrote: >> Hi Ryan, >> >> I'm afraid you've lost me. Maybe if you showed how this would be used in >> ML >> I would get the picture. >> >> Michael >> >> --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: >> >> From: Ryan Ingram <ryani.spam(a)gmail.com> >> Subject: Re: [Haskell-cafe] showing a user defined type >> To: "michael rice" <nowgate(a)yahoo.com> >> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, >> haskell-cafe(a)haskell.org >> Date: Tuesday, May 19, 2009, 2:40 PM >> >> On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: >>> A little further along in "The Little MLer" the ints function is replaced >>> by >>> other functions like primes and fibs, which also return Links: >>> >>> fun primes(n) >>> = if is_prime(n+1) >>> then Link(n+1,primes) >>> else primes(n+1) >>> >>> fun fibs(n)(m) >>> = Link(n+m,fibs(m)) >>> >>> which are passed to chain_item: >>> >>> fun chain_item(n,Link(i,f)) >>> = if eq_int(n,1) >>> then i >>> else chain_item(n-1,f(i)) >>> >>> which can be called to request the nth (12th) prime number beginning at >>> 1. >>> >>> - chain_item(12,primes(1)); >>> GC #0.0.0.1.3.61: (1 ms) >>> val it = 37 : int >>> - >>> >>> So I guess the answer to your question about whether the function is ever >>> called with a different value may be, yes. >> >> Actually, it's not calling it with another value; notice that >> chain_item calls f(i), with i coming directly from the chain. >> Consider this alternate definition: >> (I'm not sure the syntax is exactly right, but you get the idea) >> >> datatype chain = >> Link of (int * ( unit -> chain )) >> >> fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) >> fun ints(n) = intsFrom n () >> >> Now you *can't* call the function embedded in the link with another value. >> >> fun chain_item(n,Link(i,f)) >> = if eq_int(n,1) >> then i >> else chain_item(n-1,f unit) >> >> And this type for "chain" is almost the same as [Int] in Haskell, due >> to laziness. >> >> -- ryan >> >> > >

2 1

Tree traversal / stack overflow
by Matthew Eastman 20 May '09

20 May '09

Hi, I've been writing some code to calculate the stretch factor of a tree of points. What it means is that for every node in a tree (lets call it 'pivot'), I have to traverse the same tree (lets call each node 'current') and sum d_t(pivot, current) / d(pivot, current) for each node, where d_t is the tree path distance between two nodes and d is the Euclidean distance. What I've been doing is traversing the tree, pivoting up each node into the root position, and calculating the stretch factor for each new tree. ex. +===+ +===+ +===+ | 1 | | 2 | | 3 | +===+ .---+===+----. +===+ / / | | \ \ +---+ +---+ +---+ +---+ +---+ +---+ | 2 | ---> | 3 | | 4 | | 5 | | 1 | ---> | 2 | etc. .+---+. +---+ +---+ +---+ +---+ .+---+. / | \ / | \ +---+ +---+ +---+ +---+ +---+ +---+ | 3 | | 4 | | 5 | | 4 | | 5 | | 1 | +---+ +---+ +---+ +---+ +---+ +---+ The code I have right now works great on point sets of size ~10,000, but when I go up much higher things start to go wrong. I start hitting stack overflows, so I increased the stack size. For ~100,000 points though, running the code with +RTS -sstderr -K128m it chugged along for over an hour and then died with a stack overflow. The stats said it spent 50 seconds MUT time and 5300 seconds (almost 90 minutes!) GC time, which seems odd. The performance has been really good for lower numbers of points, but the professor I'm working for wants to handle over a million points later on. I've only been writing Haskell for a year, and I'm not quite sure how to rewrite this so that it won't blow the stack, since I'm pretty sure this kind of tree traversal can't be done with tail calls (I would love to proved wrong, though!). Any help would be appreciated. Thanks, Matt module ASF ( averageStretchFactor ) where import Data.Tree import Data.Foldable (foldr') type Point = (Double,Double) square :: Double -> Double square x = x * x dist :: Point -> Point -> Double dist (x1,y1) (x2,y2) = sqrt (square (x2 - x1) + square (y2 - y1)) add :: Tree a -> Tree a -> Tree a add (Node p sts) t = Node p (t:sts) -- Calculate the average stretch factor of a tree of size n. It's the sum of -- the average stretch factor of each node in the tree, divided by n choose 2 -- (the number of possible pairs of points in in a tree of size n) averageStretchFactor :: Tree Point -> Double -> Double averageStretchFactor tree n = stretchRotations tree / (n * (n - 1) / 2) -- Calculate the stretch factor of a tree. -- The stretch of two points is the tree path distance between the two points -- divided by the euclidean distance between the two points. The stretch factor -- of a tree is the sum of the stretches between the root and every other node -- in the tree. stretchFactor :: Tree Point -> Double stretchFactor (Node point sts) = stretch 0 point sts where stretch _ _ [] = 0 stretch d p ((Node p' sts'):ts) = pd / ed + stretch pd p' sts' + stretch d p ts where pd = d + dist p p' -- path distance ed = dist point p' -- euclidean distance -- Calculate the stretch factor of every point by pulling up each node in the -- tree to the root position. Note that the overall structure of the tree -- doesn't change, we're essentially just traversing the tree and calculating -- the stretch factor of each node by pretending we're at the root. stretchRotations :: Tree Point -> Double stretchRotations tree = rotate tree [] where rotate tree@(Node p sts) path = stretchFactor (foldr' add tree path) + pivot [] sts path p pivot _ [] _ _ = 0 pivot ls (r:rs) path p = rotate r (Node p (ls ++ rs) : path) + pivot (r:ls) rs path p ./main 10000 +RTS -sstderr -K128m ASF = 22.441 1,298,891,896 bytes allocated in the heap 20,191,904 bytes copied during GC 3,107,116 bytes maximum residency (7 sample(s)) 47,480 bytes maximum slop 8 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 2471 collections, 0 parallel, 0.06s, 0.07s elapsed Generation 1: 7 collections, 0 parallel, 0.03s, 0.03s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 13.05s ( 13.18s elapsed) GC time 0.09s ( 0.11s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 13.14s ( 13.29s elapsed) %GC time 0.7% (0.8% elapsed) Alloc rate 99,506,082 bytes per MUT second Productivity 99.3% of total user, 98.2% of total elapsed ./main 100000 +RTS -sstderr -K128m Stack space overflow: current size 128000000 bytes. Use `+RTS -Ksize' to increase it. 33,097,322,168 bytes allocated in the heap 3,004,248,280 bytes copied during GC 704,391,196 bytes maximum residency (29 sample(s)) 67,420,196 bytes maximum slop 1731 MB total memory in use (14 MB lost due to fragmentation) Generation 0: 62561 collections, 0 parallel, 5364.16s, 5619.83s elapsed Generation 1: 29 collections, 0 parallel, 4.50s, 48.73s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 49.85s ( 78.94s elapsed) GC time 5368.66s (5668.56s elapsed) EXIT time 0.00s ( 7.88s elapsed) Total time 5418.51s (5747.56s elapsed) %GC time 99.1% (98.6% elapsed) Alloc rate 663,930,946 bytes per MUT second Productivity 0.9% of total user, 0.9% of total elapsed

1 1

Re: [Haskell-cafe] showing a user defined type
by michael rice 20 May '09

20 May '09

OK, I think I understand. You were explaining how ML could be made to emulate Haskell laziness using streams, ala Scheme type delayed evaluation, so it's kind of like you were explaining a question I hadn't quite asked yet, which maybe explains my puzzlement, I hope. Also, though my understanding of both Haskell and ML syntax is still rudimentary, I did catch an error in your definition of chain_take: the first arg of the cons should be i rather than n. I'm still going through your code and may have further questions. Thanks for your input. Michael --- On Wed, 5/20/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Wednesday, May 20, 2009, 4:12 AM (Apologies for my mutilation of ML syntax, I don't completely know the language) Consider the ML type int list, and this function to build one: broken_repeat :: int -> int list broken_repeat n = Cons(n, broken_repeat(n)) This function is recursive, and doesn't terminate; it tries to build an infinite list of ints and your computer runs out of heap and/or stack trying to evaluate it. But the "chain" type doesn't have this problem; you can see it as an int list that gets evaluated "on demand": repeat :: int -> chain repeat(n) = Link(n, repeat) always1 :: int -> chain always1(_) = Link(1, always1) chain_take :: int * chain -> int list chain_take (0,_) = Nil chain_take (n,Link(i,f)) = Cons(n, chain_take(n-1, f(i))) But, nothing in the "chain" type stops you from passing a different value to the function in the link: weird_take :: int * int * chain -> int list weird_take (0,_,_) = Nil weird_take (n,v,Link(i,f)) = Cons(i, weird_take(n-1,v,f(v))) Now, it's possible that chain_take returns the same list for two different "chain" inputs, but weird_take might return different lists depending on how f is implemented. For example: chain_take(5, repeat(1)) = [1,1,1,1,1] chain_take(5, always1(1) = [1,1,1,1,1] weird_take(5, 2, repeat(1)) = [1,2,2,2,2] weird_take(5, 2, always1(1)) = [1,1,1,1,1] One way to fix this is to embed the "state" of the chain in the closure itself. So, in ML, the type unit -> X is commonly called a "thunk"; it can be used to delay computation until later, until it's demanded, just like any lazy value in Haskell. f :: unit -> Int f () = 1 This f isn't very useful; it's basically the same as "1". But consider this type: datatype stream = Stream of (int * (unit -> stream)) stream1 () = Stream(1, stream1) stream_take :: int*stream -> int list stream_take(0,_) = Nil stream_take(n,Stream(i,f)) = Cons(i, stream_take(n-1, f())) Now there is no way to pass a different value like we did in weird_take; there's only (). The difference is that the state gets embedded in the closure for the thunk: stream_ints :: int -> (unit -> stream) stream_ints = fun n => fun () => Stream(n, stream_ints(n+1)) What you are doing here is encoding laziness; the Haskell version of this type: > data Stream = Stream !Int Stream -- !Int means the Int value is strict > stream1 = Stream 1 stream1 > stream_ints n = Stream n (stream_ints(n+1)) > stream_take :: Int -> Stream -> [Int] > stream_take 0 _ = [] > stream_take n (Stream x xs) = x : stream_take (n-1) xs No extra (\() -> ...) thunk is required, due to laziness :) -- ryan On Tue, May 19, 2009 at 4:25 PM, michael rice <nowgate(a)yahoo.com> wrote: > Hi Ryan, > > I'm afraid you've lost me. Maybe if you showed how this would be used in ML > I would get the picture. > > Michael > > --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: > > From: Ryan Ingram <ryani.spam(a)gmail.com> > Subject: Re: [Haskell-cafe] showing a user defined type > To: "michael rice" <nowgate(a)yahoo.com> > Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, > haskell-cafe(a)haskell.org > Date: Tuesday, May 19, 2009, 2:40 PM > > On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: >> A little further along in "The Little MLer" the ints function is replaced >> by >> other functions like primes and fibs, which also return Links: >> >> fun primes(n) >> = if is_prime(n+1) >> then Link(n+1,primes) >> else primes(n+1) >> >> fun fibs(n)(m) >> = Link(n+m,fibs(m)) >> >> which are passed to chain_item: >> >> fun chain_item(n,Link(i,f)) >> = if eq_int(n,1) >> then i >> else chain_item(n-1,f(i)) >> >> which can be called to request the nth (12th) prime number beginning at 1. >> >> - chain_item(12,primes(1)); >> GC #0.0.0.1.3.61: (1 ms) >> val it = 37 : int >> - >> >> So I guess the answer to your question about whether the function is ever >> called with a different value may be, yes. > > Actually, it's not calling it with another value; notice that > chain_item calls f(i), with i coming directly from the chain. > Consider this alternate definition: > (I'm not sure the syntax is exactly right, but you get the idea) > > datatype chain = > Link of (int * ( unit -> chain )) > > fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) > fun ints(n) = intsFrom n () > > Now you *can't* call the function embedded in the link with another value. > > fun chain_item(n,Link(i,f)) > = if eq_int(n,1) > then i > else chain_item(n-1,f unit) > > And this type for "chain" is almost the same as [Int] in Haskell, due > to laziness. > > -- ryan > >

2 1

Free theorems for dependent types?
by Eugene Kirpichov 20 May '09

20 May '09

Hello, Is there any research on applying free theorems / parametricity to type systems more complex than System F; namely, Fomega, or calculus of constructions and alike? This seems very promising to me for the following reason: Take the free theorem for 'sort::(a->a->Bool)->[a]->[a]'. The theorem could possibly be a lot more powerful if there were a way to encode in the type of 'sort' that it accepts a reflexive transitive antisymmetric predicate, but the only way to express that is with dependent types. Looks like the only thing one needs to add to System F is the relational translation rule for a dependent product; but I haven't tried doing it myself. -- Eugene Kirpichov Web IR developer, market.yandex.ru

7 11

Problem with haddock importing definition
by Maurício 20 May '09

20 May '09

Hi, I have a situation like this: module A imports R (a newtype declaration) from module B, and lists it in its (module A) export list. Documentation for R is included by haddock in documentation for module A, as I want. However, if my package exposes only module A, documentation for R desapears. So: if my .cabal file lists A and B in 'exposed-modules', documentation for R is included in A documentation. If I remove B from 'exposed-modules', R documentation in A desapears. Do you know what should I do? Thanks, Maurício

3 5

HaL4: Haskell-Treffen in Halle/Saale, 12. Juni 2009 - Programm und Anmeldung
by unknown＠example.com 20 May '09

20 May '09

Kindly excuse the German noise, please ... Liebe Haskell-Freunde! Das Programm fuer unser Haskell-Treffen steht jetzt so gut wie fest und man kann sich online anmelden. --------------------------------------------- HaL4 : Haskell - Tutorial + Workshop + Party am Freitag, dem 12. Juni 2009, in Halle/Saale --------------------------------------------- Das traditionsreiche HaL-Treffen bietet eine gute Mischung von Haskell-bezogenen Themen aus Forschung, Anwendung und Lehre mit vielen Möglichkeiten zu Diskussion und Unterhaltung bei der anschließenden Party. Der Workshop wird in diesem Jahr ergänzt durch Tutorien für Haskell-Ein- und Umsteiger. Diesmal findet das Treffen in Halle/Saale im Institut für Informatik der Martin-Luther-Universität Halle-Wittenberg statt. Wir bieten: 10 Uhr: Entwurfsmuster vom Kopf auf die Fuesse gestellt: data, fold und laziness statt Kompositum, Visitor, Iterator. Johannes Waldmann, HTWK Leipzig. 11 Uhr: CAL/openquark: (openquark.org) Haskell + Java => CAL, eine praktische Einfuehrung (Eclipse als CAL-IDE, Excel lesen, typsicheres SQL = LINQ fuer Java?) Alf Richter, iba Consulting, Leipzig 12 Uhr: Wie man das Semikolon ueberlaedt: Code-Strukturierung und -Wiederverwendung durch Monaden 15 Uhr: Hayoo! Haskell API Search Timo Huebel, FH Wedel 16 Uhr: Haskell als reine Spezifikationssprache Baltasar Trancon y Widemann, Universit Bayreuth 17 Uhr: Funktional-logische Programmierung mit Curry Jan Christiansen, Universitaet Kiel 19 - 22 Uhr: Grillparty Wir freuen uns auf rege Teilnahme sowie spannende Vorträge mit heißen Diskussionen und bitten um Anmeldung bis zum 31. Mai. Weitere Informationen auf http://www.iba-cg.de/hal4.html Beste Gruesse Henning Thielemann

1 0

Re: [Haskell-cafe] How i use GHC.Word.Word8 wit Int ?
by spoon＠killersmurf.com 20 May '09

20 May '09

While just writing 33 instead of length [1..33] saves an awful lot of bother, the function you'd probably want in similar circumstances is `fromIntegral` See the Prelude. Also, you can use Data.ByteString.head instead of unpack and then Data.List.head rollDice :: Word8 -> IO Word8 rollDice n = do bracket (openFile "/dev/random" ReadMode) hClose (\hd -> do v <- fmap B.head $ B.hGet hd 1 return $ (v `mod` n) + 1)

1 0

Expression parsing problem
by leledumbo 20 May '09

20 May '09

I'm writing a paper as a replacement for writing exam and decided to write a simple compiler (got a little experience with it). However, I got trouble in parsing expression. The grammar: expression = "get" | [ "+" | "-" ] term { ( "+" | "-" ) term } term = factor { ( "*" | "/" ) factor } factor = IDENTIFIER | VALUE | "(" expression ")" I can't make term parse, for instance "1 * 2 / 3" (the number is not important, identifier is also accepted). It stops after parsing 2, i.e. only the first multiplication is parsed. Interchanging * and / gives the same result, only differs in operation. Whichever got encountered first will be parsed. The same problem also arises from expression, where it can't parse "1 + 2 - 3". Both problems are identical, but I can't figure out what's wrong (don't count the optional +/- before term in expression, I haven't done it yet). Sorry, but I'm lack of knowledge about Monad. I know it can be done better with it, but I need to learn a lot about it, while I don't have enough time (only 2 weeks). Below are necessary definitions for the parser (some taken from the scanner). For testing purpose, please try: expression [("1",Value),("+",Plus),("2",Value),("-",Minus),("3",Value),("EOF",EOF)] term [("1",Value),("*",Times),("2",Value),("/",Slash),("3",Value),("EOF",EOF)] expression [("1",Value),("-",Minus),("2",Value),("+",Plus),("3",Value),("EOF",EOF)] term [("1",Value),("/",Slash),("2",Value),("*",Times),("3",Value),("EOF",EOF)] > data Token = Identifier | OpenBlock | CloseBlock | SemiColon | Slash | > Equals | OpenBrace | CloseBrace | Minus | Times | > Plus | Nil | Value | Var | Const | > Put | Get | Comma | EOF > deriving (Show,Eq) > type Symbol = (String,Token) > type ASL = [Symbol] > type ParseFunc = ASL -> (ASL,[String]) > expression :: ParseFunc > expression (h:s) > | snd h == Get = (s,["IN"]) > | op `elem` [Plus,Minus] = (s2,r1 ++ r2 ++ [operation op]) > | otherwise = (s1,r1) > where (s1,r1) = term (h:s) > (s2,r2) = term $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > expression s = (s,[]) > term :: ParseFunc > term s = if op `elem` [Times,Slash] > then (s2,r1 ++ r2 ++ [operation op]) > else (s1,r1) > where (s1,r1) = factor s > (s2,r2) = factor $ tail s1 > op = if s1 /= [] then snd $ head s1 else Nil > factor :: ParseFunc > factor ((id,Identifier):s) = (s,["LOAD " ++ id]) > factor ((val,Value):s) = (s,["PUSH " ++ val]) > factor (("(",OpenBrace):s) = if head s1 == (")",CloseBrace) > then (tail s1,r1) > else error $ "\")\" expected, got" ++ (show $ fst $ head s1) > where (s1,r1) = expression s > factor s = (s,[]) -- View this message in context: http://www.nabble.com/Expression-parsing-problem-tp23610457p23610457.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 8

Re: [Haskell-cafe] showing a user defined type
by michael rice 20 May '09

20 May '09

Hi Ryan, I'm afraid you've lost me. Maybe if you showed how this would be used in ML I would get the picture. Michael --- On Tue, 5/19/09, Ryan Ingram <ryani.spam(a)gmail.com> wrote: From: Ryan Ingram <ryani.spam(a)gmail.com> Subject: Re: [Haskell-cafe] showing a user defined type To: "michael rice" <nowgate(a)yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery(a)ece.cmu.edu>, haskell-cafe(a)haskell.org Date: Tuesday, May 19, 2009, 2:40 PM On Tue, May 19, 2009 at 7:07 AM, michael rice <nowgate(a)yahoo.com> wrote: > A little further along in "The Little MLer" the ints function is replaced by > other functions like primes and fibs, which also return Links: > > fun primes(n) > = if is_prime(n+1) > then Link(n+1,primes) > else primes(n+1) > > fun fibs(n)(m) > = Link(n+m,fibs(m)) > > which are passed to chain_item: > > fun chain_item(n,Link(i,f)) > = if eq_int(n,1) > then i > else chain_item(n-1,f(i)) > > which can be called to request the nth (12th) prime number beginning at 1. > > - chain_item(12,primes(1)); > GC #0.0.0.1.3.61: (1 ms) > val it = 37 : int > - > > So I guess the answer to your question about whether the function is ever > called with a different value may be, yes. Actually, it's not calling it with another value; notice that chain_item calls f(i), with i coming directly from the chain. Consider this alternate definition: (I'm not sure the syntax is exactly right, but you get the idea) datatype chain = Link of (int * ( unit -> chain )) fun intsFrom(n) = fun unit => (n, intsFrom (n+1)) fun ints(n) = intsFrom n () Now you *can't* call the function embedded in the link with another value. fun chain_item(n,Link(i,f)) = if eq_int(n,1) then i else chain_item(n-1,f unit) And this type for "chain" is almost the same as [Int] in Haskell, due to laziness. -- ryan

2 1