- Haskell-Cafe - Haskell.org

Why the Prelude must die
by Andrzej Jaworski 30 Mar '07

30 Mar '07

>What I want to push is a 'mathematically sound' numeric prelude. A proper >numerical prelude should have bona fide mathematical obects like groups, >rings, and fields underlying common numerical classes. Why not Clifford algebra: to simplify mathematical physics, mechanics, computer vision, improve neural networks etc.? That would probably be easier with OCaml-style categorical machine architecture. But then why not go for combinatorial stuff like matroids or graphs? More mathematics in a programming language won't harm general applications written in it. On the contrary, almost any human endeavor could be mathematically structured and thus programmed. Present languages are office-oriented for lack of mathematical knowledge and not any hidden virtue. Cheers, -Andrzej

3 4

Simple task for parsec.
by Paolo Veronelli 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

Parsing words with parsec
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

A simple parsing task for parsec.
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

A simple parsing task for parsec.
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

A simple parsing task for parsec.
by paolino 29 Mar '07

29 Mar '07

Hi, I had a bad time trying to parse the words of a text. I suspect I miss some parsec knowledge. In the end it seems working, though I haven't tested much and this example contains the main features I was looking. *Main> parseTest (parseLine eof) "paolo@gmail sara,mimmo! 9ab a9b ab9 cd\n" ["paolo@gmail","sara","mimmo","cd"] --------------------- manyTillT body terminator joiner = liftM2 joiner (manyTill body (lookAhead terminator)) terminator wordChar = letter <|> oneOf "_@" <?> "a valid word character" nonSeparator = wordChar <|> digit wordEnd = do x <- wordChar notFollowedBy nonSeparator return x word = manyTillT wordChar (try wordEnd) (\b t -> b ++ [t]) <?> "a word" wordStart = do (try nonSeparator >> unexpected "non separator") <|> anyChar lookAhead wordChar nextWord = manyTill anyChar (try wordStart) >> (try word <|> nextWord) parseLine end = do f <- option [] $ return `fmap` try word r <- many $ try nextWord manyTill anyChar end return (f ++ r) ----------- Any comment to simplify this code is welcome. Paolino.

1 0

Monad/Functor Book
by Dominic Steinitz 29 Mar '07

29 Mar '07

> On 3/27/07, Dave at haskell.org <Dave at haskell.org> wrote: > > Given the amount of material posted at haskell.org and elsewhere > > explaining IO, monads and functors, has anyone considered publishing > > a comprehensive book explaining those subjects? (I am trying to > > read all the material online, but books are easier to read and don't > > require sitting in front of a computer to do so. Plus I can write in > > books :-). ) > > I've thought about writing extended tutorials on the relationship > between Haskell programming and category theory but there's a problem > I run into. It's tempting to make the identifications: > types<->objects, Haskell function<->arrows, suitably polymorphic > functions<->natural transformations, and so on. But the fact is, this > doesn't really work in the obvious way even though it seems like it > should at first (eg. Haskell functions aren't always total functions > in the mathematical sense and if you allow partial functions you can > do weird stuff). So either: > > (1) we need some technical work to patch up the differences (and > unfortunately I don't know what the patch-up is), > (2) we restrict ourselves to certain types of Haskell function for > which the theory works or > (3) we deliberately leave things a little vague. > > I usually tend to go for option (3), but that wouldn't be satisfactory > for an extended treatment. > > Has anyone else given this subject much thought? > -- > Dan Dan, It's a long time since I looked at this so this might be a complete red herring but have you thought about using the category of \omega-CPOs. Types are then objects (\omega-cpos) and functions are then arrows (continuous functions in the \omega-cpo sense). These papers may be of use: 1. Meijer http://research.microsoft.com/~emeijer/Papers/CWIReport.pdf 2. Mitchell Wand: Fixed-Point Constructions in Order-Enriched Categories 3. Freyd: Recursive Types Reduced to Inductive Types. Dominic.

1 0

Prologue junk? - compiling lambdabot:Plugin.Pl.Transform
by Iain Alexander 29 Mar '07

29 Mar '07

I'm trying to build lambdabot 4.0 with ghc-6.4.1 (gcc (GCC) 3.4.2 (mingw- special)) and Cabal-1.1.6.1 on WinXP SP2. I've got as far as Plugin.Pl.Transform.hs, and I get *** Mangler g:\ghc\ghc-6.4.1\perl g:\ghc\ghc-6.4.1\ghc-asm C:\DOCUME~1\IAINAL~1\LOCALS~1\Tem p\ghc2736.raw_s C:\DOCUME~1\IAINAL~1\LOCALS~1\Temp\ghc2736.s 4 Prologue junk?: _s7f7_ret: xorl %ecx, %ecx xorl %eax, %eax movl %ecx, 8(%esp) movl %eax, 12(%esp) /APP Transform.hs uses {-# OPTIONS -fvia-C -O2 -optc-O3 #-} I've tried and failed to make sense of why the mangler's failing. I don't know if this is a known problem with 6.4.1 on XP. I'm not sure what to try next. I could turn off the aggressive optimisation, but I don't know how much that would cost me. I've got 6.4.2 installed, so I could try that, although I'd need to rebuild all the prerequisites. Anything else? -- Iain Alexander ia(a)stryx.demon.co.uk

2 1

cost of modules
by Fawzi Mohamed 29 Mar '07

29 Mar '07

ehm, never post from someone's else computer with a new mailer... sorry for the double posts (to glasgow-haskell-users(a)haskell.org and here). Simon Peyton-Jones wrote: > Generally speaking GHC will inline *across* modules just as much as > it does *within* modules, with a single large exception. > > If GHC sees that a function 'f' is called just once, it inlines it > regardless of how big 'f' is. But once 'f' is exported, GHC can > never see that it's called exactly once, even if that later turns out > to be the case. This inline-once optimisation is pretty important > in practice. > > So: do not export functions that are not used outside the module > (i.e. use an explicit export list, and keep it as small as possible). This is very interesting to know, as it explains a strange effect that I was seeing: I had an algorithm and I began to add variants of it as separate functions in the same module. Then I saw the original function (which I had not touched) get slower and slower. I even wondered if the compiler was not maybe taking common parts of my functions out of them to reduce the evaluations making my original function slower, but then it was that it wasn't inlining anymore some functions. This means the with haskell (with ghc) cleaning up old code and keeping the modules as clean as possible pays off even more than in other languages... good to know, and very important when benchmarking various algorithms: commenting out a variant is better as having it as separate function.... Fawzi

2 2

Re: [Haskell-cafe] Newbie: a parser for a list of objects?
by Daniel Fischer 29 Mar '07

29 Mar '07

> -----Ursprüngliche Nachricht----- > Von: "Dmitri O.Kondratiev" <dokondr(a)gmail.com> > Gesendet: 26.03.07 16:44:12 > An: haskell-cafe(a)haskell.org > Betreff: [Haskell-cafe] Newbie: a parser for a list of objects? > Please see my questions inside comments {-- --} : > Thanks! > > --- > module Parser where > > import Data.Char > > type Parse a b = [a] -> [(b, [a])] > > {-- > Newbie: a parser for a list of objects? > > I am working with the section 17.5 "Case study: parsing expressions" of the book "Haskell The Craft of Functional Programming", where a parser for a list of objects is defined. > I called this function pList in order to avoid confusion with 'list' as a term for data structure. > > Please help me to understand how pList works (please, see the rest of the code at the end of this message): > --} > > pList :: Parse a b -> Parse a [b] > pList p = (succeed []) `alt` > ((p >*> pList p) `build` (uncurry (:))) > > > {-- > First of all, I don't quite understand why there must be a choice ('alt') between the function ('succeed') that always returns an empty list and the other part? This results in adding [] to the front, why? > Well, if the parser p doesn't succeed, we don't want the whole thing to fail. And p will (almost certainly) fail when the end of input is reached. So without the alternative 'succeed []', we'd get pL1 dig "12" = [(('1':y),rem) | (y,rem) <- pL1 dig "2"] = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- pL1 dig ""]] = [(('1':y),rem) | (y,rem) <- [(('2':z),rem2) | (z,rem2) <- []] = [(('1':y),rem) | (y,rem) <- []] = [] because dig "" = [] > I thought that 'simplified' version of pList should still work fine. Trying to prove this I wrote : > --} > > pL1 :: Parse a b -> Parse a [b] > pL1 p = (p >*> pL1 p) `build` (uncurry (:)) > > {-- > Which, as expected, does not work correctly - just gives an empty list [] - but I don't understand why: because the parser eventually fails when the end of input is reached. > > *Parser> t1 "12345" > [] > *Parser> > > Also, I don't understand why the textbook version of pList gives this result: > > *Parser> test "12345" > [("","12345"),("1","2345"),("12","345"),("123","45"),("1234","5"),("12345","")] That's because of the order of alt's arguments: (succeed [] `alt` p) inp = [([],inp)] ++ (p inp) with pList p = ((p >*> pList p) `build` (uncurry (:))) `alt` succeed [] the resulting list woulde be reversed. > > *Parser> > > In particular, I don't understand where the first element ("","12345") of the resulting list comes from? > > I am trying to figure out how pList recursively unfolds. To my mind operators in the expression: > > > (succeed []) `alt`((p >*> pList p) `build` (uncurry (:))) > > has the following execution order: > 1) >*> > 2) 'build' > 3) 'alt' > No, the first argument of alt gets evaluated first, because (p1 `alt` p2) inp = (p1 inp) ++ (p2 inp), thus we need p1 inp first. Then we see we haven't hit bottom, so we need the second argument of (++) (resp. alt). So next we need to evaluate p, then pList p, combine the results of those with the second argument of build, uncurry (:). > It seems that operation >*> should be done as many times as many elements the input list has. Right? > Unfortunately not. Let's stay with pList dig. Say your input starts with n digits. >From the example above you can conjecture that length (pList dig inp) == (n+1). Now in the outermost (dig >*> pList dig) branch, you apply (pList dig) to an input beginning with (n-1) digits, returning a list of length n, to each element of this list you adjoin the first digit, resulting in n + (n-1) + ... + 1 = n*(n+1)/2 applications of (>*>). (Lesson: you need an exclusive choice, using the second parser only if the first one fails and a maximal munch combinator in your library, too) > > Signature: > > (>*>) :: Parse a b -> Parse a c -> Parse a (b, c) > > implies that second argument of the expression: > > p >*> pList p > > should be of type 'Parse a c' but in this application it is of type 'Parse a b -> Parse a [b]' > c is [b], so p >*> pList p has type Parse a (b,[b]), then (p >*> pList p) `build` (uncurry (:)) has type Parse a [b] > How can that be? > How recursion termination conditinon is expressed in pList? recursion terminates when p fails. HTH, Daniel > --} > > none :: Parse a b > none inp = [] > > succeed :: b -> Parse a b > succeed val inp = [(val, inp)] > > suc:: b -> [a] -> [(b, [a])] > > suc val inp = [(val, inp)] > > spot :: (a -> Bool) -> Parse a a > spot p [] = [] > spot p (x:xs) > | p x = [(x, xs)] > | otherwise = [] > > alt :: Parse a b -> Parse a b -> Parse a b > alt p1 p2 inp = p1 inp ++ p2 inp > > bracket = spot (=='(') > dash = spot (== '-') > dig = spot isDigit > alpha = spot isAlpha > > infixr 5 >*> > > (>*>) :: Parse a b -> Parse a c -> Parse a (b, c) > > (>*>) p1 p2 inp = [((x,y), rem2) |(x, rem1) <- p1 inp, (y, rem2) <- p2 rem1] > > build :: Parse a b -> (b -> c) -> Parse a c > build p f inp = [ (f x, rem) | (x, rem) <- p inp] > > test = pList dig > t1 = pL1 dig > > > -----------------------------------------------------------------

2 5