- Haskell-Cafe - Haskell.org

foldr
by James Ealing 02 Jan '04

02 Jan '04

Hi all, If I have a function: it f [a0, a1, a2, ...] = [a0, f a1, f (f a2), ...] Is there any way of expressing it f as an instance of foldr? Many thanks, Jim ________________________________________________________________________ Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html

2 1

Parsing library
by James Ealing 02 Jan '04

02 Jan '04

I'm trying to make use of the combinatorial parsing library to process strings. However, I can't figure out the correct syntax for the (|||) (^^^) (>>>) (<^^) and (^^>) functions. Can anyone see how to do it? If so it'd be really useful if you could put down a couple of examples of how each is used. Thanks Jim The library: Generic parsing functions >module Parse ( > Parse, succeed, token, spot, > (|||), (^^^), (<^^), (^^>), (>>>), > many, listOf, topLevel, > white, ws, parseVar, word, parseNum) >where --------------------------------------------------- -- Combinatory parsing library using Maybe types -- -- suitable for non-ambiguous grammars. -- -- sja4(a)mcs.le.ac.uk (21/10/96) -- --------------------------------------------------- >infixr 5 `into`, ^^^, <^^, ^^> >infixl 4 >>> >infixr 3 ||| Maybe defined in prelude: data Maybe a = Just a | Nothing --------------------- -- Type of parsers -- --------------------- >type Parse a = String -> Maybe (a, String) ------------------- -- Basic parsers -- ------------------- Succeed with the value given. >succeed :: a -> Parse a >succeed val inp = Just (val, inp) Recognize a specified token at the head of the input. >token :: Char -> Parse Char >token t (u:x) = if t == u then Just (t,x) else Nothing >token t [] = Nothing Recognize a token with a certain property. >spot :: (Char -> Bool) -> Parse Char >spot p (t:x) = if p t then Just (t,x) else Nothing >spot p [] = Nothing ------------------------- -- Parsing combinators -- ------------------------- A choice between two parsers. The function p1 ||| p2 returns the result of p1 whenever it succeeds and the result of p2 otherwise. >(|||) :: Parse a -> Parse a -> Parse a >(p1 ||| p2) inp = case p1 inp of > Nothing -> p2 inp > Just (v,x) -> Just (v,x) Sequencing of parsers. The function p1 ^^^ p2 returns the result, if any, of applying p1 to the input and then p2 to the remainder. >(^^^) :: Parse b -> Parse c -> Parse (b,c) >(p1 ^^^ p2) inp = > case p1 inp of > Nothing -> Nothing > Just (v,x) -> case p2 x of > Nothing -> Nothing > Just (u,y) -> Just ((v,u),y) Semantic action. The results from a parser p are transformed by applying a function f. >(>>>) :: Parse b -> (b -> c) -> Parse c >(p >>> f) inp = case p inp of > Nothing -> Nothing > Just (v,x) -> Just (f v, x) Sequencing of parsers, choosing one component or the other >(<^^) :: Parse b -> Parse c -> Parse b >p <^^ q = (p ^^^ q) >>> fst >(^^>) :: Parse b -> Parse c -> Parse c >p ^^> q = (p ^^^ q) >>> snd Repetition. The parser p is used as many times as possible and the results are returned as a list. >many :: Parse b -> Parse [b] >many p = ((p ^^^ many p) >>> cons) ||| (succeed []) >cons (x,xs) = x:xs ListOf p c applies parser p as many times as possible, with the instances separated by instances of c, and returns the result as a list. >listOf :: Parse b -> Char -> Parse [b] >listOf p sep = p ^^^ many (token sep ^^> p) >>> cons The top level parser is a function which maps a list of tokens to a value. A value p :: Parse a b can be converted to such a function by applying topLevel: >topLevel :: Parse b -> String -> b >topLevel p inp > = case p inp of > Just (result,[]) -> result > Just (result,rest) -> > error ("parse unsuccessful; input unconsumed:"++show rest) > other -> error "parse unsuccessful" Note there is an error if the input is not fully consumed. It is sometimes useful to test whether a given parser will accept the input without actually returning a result. >acceptedBy :: Parse b -> String -> Bool >acceptedBy parser inp > = case parser inp of > Just (result,[]) -> True > other -> False A more sophisticated form of sequencing. The into combinator allows the second parser to be chosen according the result of the first. >into :: Parse b -> (b -> Parse c) -> Parse c >into p f inp = case p inp of > Nothing -> Nothing > Just (v,x) -> f v x ========================================================================== Absorb white space >white = many (token ' ' ||| token '\t') >ws p = white ^^> p <^^ white ========================================================================== Consume and return variable: must start with small letter, and continue with alphanumberic characters >parseVar :: Parse String >parseVar = spot isLower ^^^ many (spot isAlphaNum) >>> cons Consume and return particular word >word :: String -> Parse String >word [c] = token c >>> (\ c -> [c]) >word (c:cs) = (token c ^^^ word cs) >>> cons Consume and return number >parseNum :: Parse Int >parseNum = spot isDigit ^^^ many (spot isDigit) >>> mknum > where mknum (d, ds) = foldl f (digitToInt d) ds > f n d = 10*n + digitToInt d ________________________________________________________________________ Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html

2 1

RE: foldr
by Garner, Robin 02 Jan '04

02 Jan '04

It's not too difficult to do: think 'fold map' and put it in the form that foldr needs. cheers -----Original Message----- From: James Ealing [mailto:jamesealing2000@yahoo.co.uk] Sent: Friday, 02 January, 2004 1:54 PM To: haskell-cafe(a)haskell.org Subject: foldr Hi all, If I have a function: it f [a0, a1, a2, ...] = [a0, f a1, f (f a2), ...] Is there any way of expressing it f as an instance of foldr? Many thanks, Jim ________________________________________________________________________ Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Module creation
by J & M van Berchem 02 Jan '04

02 Jan '04

New to Haskell, I got a version, through Fink, for my Mac OS X. I like the interpreter very much, but I do not see how I may get out of "Prelude" in order to write a program. Could you advise me ? Thanks in advance Jacques van Berchem

2 1

Parsec question
by Mark Carroll 01 Jan '04

01 Jan '04

I tried posting this before but, from my point of view, it vanished. My apologies if it's a duplicate. In http://www.cs.uu.nl/~daan/download/parsec/parsec.html we read, > testOr2 = try (string "(a)") > <|> string "(b)" > > or an even better version: > > testOr3 = do{ try (string "(a"); char ')'; return "(a)" } > <|> string "(b)" Why is the latter better? (BTW, I like Parsec. Thanks, Daan. (-:) -- Mark

3 3

Monads
by Mark Carroll 01 Jan '04

01 Jan '04

Omitting the typeclass bit, I'm trying to write something like (s1 -> s2) -> StateT s1 m () -> StateT s2 m a -> StateT s1 m a That is, it sequences two StateT computations, providing a way to translate from the first's state to the second to keep the chain going. I can easily write something for when s1 and s2 are the same, and my understanding of much of Control.Monad.* remains tenuous at best, but if it's easy for anyone to provide me with some tips, then I thought I should mention that it'd certainly be helpful. And Happy New Year, everyone! -- Mark

3 3

Type checking/inference
by Lee Dixon 28 Dec '03

28 Dec '03

Hi, I've run into a small problem whilst doing some manual type checking, to see if I could match the results given by hugs prelude> :t foldr filter foldr filter :: [a] -> [a -> Bool] -> [a] -- This was fine and was the same as my answer, so I tested it with prelude> foldr filter [1,2,3,4] [even,odd] -- and the answer was indeed an empty list -- However I got stuck when attempting to derive the result of map (foldr filter) -- Hugs says that: prelude> :t map (foldr filter) map (foldr filter) :: [[a]] -> [[a -> Bool] -> [a]] Two main questions: 1/ How does hugs derive this answer? 2/ What input can I give so that it yields a correct result? I've tried giving it a list of lists but it fails... Any pointers would be greatly appreciated! Many Thanks, Lee _________________________________________________________________ Stay in touch with absent friends - get MSN Messenger http://www.msn.co.uk/messenger

4 3

Re: Perspectives on learning and using Haskell
by Graham Klyne 24 Dec '03

24 Dec '03

[switching to Haskell-cafe] At 19:37 23/12/03 +0100, Tomasz Zielonka wrote: >On Tue, Dec 23, 2003 at 05:26:20PM +0000, Graham Klyne wrote: > > > [1] http://www.ninebynine.org/Software/Learning-Haskell-Notes.html > >Thanks, that was a nice reading :) Thanks! (If by any chance there's anything here that might be useful for the Wiki, anyone may feel free to plunder it.) >I have some comments: > >8. Your explanation of Functor excludes many useful Functors which are > rather not collections. For example, every monad (like IO) can > be a Functor if you take fmap = Monad.liftM. > > For [] and Maybe this would give the same operation as in their > normal instances. That's an interesting perspective that I wasn't aware of... I need to think about that. Meanwhile, I've added your observation to my notes. [later] It now seems to me that (some?) Monads are kinds of Functors, generalized to handle the "no value" case, and also composition. This also had me thinking about sequence: is there a generalization to arbitrary monads that rearranges the monadic structure? >11 and 18. > If you define an instance of Monad for ((->) e) then > > return (putStrLn "Hello!") 'x' > > is a proper IO () value. Probably still not sensible ;) Ah, I think I see your point. It would apply where monads are "nested", right? > Special treatment of 'return' could be helpful, but I am afraid that > it could also make it look special, like a return keyword in C. I certainly wouldn't argue for special treatment _in the language_, but OTOH, I think it might be helpful if compiler diagnostics hinted at the possibility when a type error is detected in a form like return x y. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

Re: looking for data structure advice
by Jon Cast 24 Dec '03

24 Dec '03

Conor McBride <c.t.mcbride(a)durham.ac.uk> wrote: <snip> > I've always been a little bothered by the MonadPlus class: zero and > plus are associated (no pun intended) in my mind with monoidal > structure. Is there more to MonadPlus than a clumsy workaround for > the lack of quantified constraints? Yes. For every functor m with a MonadPlus instance, m () has /two/ monoids, (mzero, mplus) and (return (), (>>)). MonadPlus is thus no more a workaround than the category Field; MonadPlus is simply a way to specify that a functor has two monoid-like structures, one more exact than the other, together with the expectation that the two monoids are related in a manner similar to the relationship of the two (more-or-less-) groups that make up a field. > If we could have quantified constraints, e.g. > > (Monad m, forall x. Monoid (m x)) > > wouldn't that be better than having Monad-specific monoids? No. Consider the monad Writer (IO ()). The Writer monad wants a Monoid instance, and the most natural such instance is often (return (), (>>)). OTOH, this monad is always wrong in the cases where, currently, you would use mplus. So you can't just replace MonadPlus with Monoid; you need to be more specific about your choice of monoid than can be accounted for by a single class. <snip> Jon Cast

2 1

Hugs Nov-2003 release: traceShow goes missing
by Graham Klyne 19 Dec '03

19 Dec '03

I've just upgraded my Hugs installation to the Nov-2003 release, and I notice that function traceShow is missing from library module Debug.Trace. I assume this is unintentional, as it's still mentioned in the Hugs manual. (In my installation, I've copied the 2-line function implementation from the previous Hugs release into this module, and added it to the module export list.) #g -- ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0