RE: no continuations
Kevin S. Millikin wrote: > It sure looks like the example contradicts the assertion, but I happen > to know that there is a set! (or some other assignment) in the macro > expansion of define. I'm just using call/cc to get at that, rather > than getting at the one in the expansion of letrec. In Scheme 'define' is normally a primitive because in most of the systems a top-level 'define' must create a top-level variable binding, and there is no other R5RS form that can do that. Still, you're right about set!. R5RS says: "5.2.1. Top level definitions At the top level of a program, a definition (define variable expression) has essentially the same effect as the assignment expression (set! variable expression) if variable is bound. If variable is not bound, however, then the definition will bind variable to a new location before performing the assignment... Some implementations of Scheme use an initial environment in which all possible variables are bound to locations, most of which contain undefined values. Top level definitions in such an implementation are truly equivalent to assignments." Similarly, R5RS obligates any Scheme implementation to resort to assignments when processing a letrec form. An implementation may not use a (polyvariadic) Y to implement letrec, unless the implementation can prove that the difference is unobservable for the form in question. Incidentally, one can easily observe how letrec is implemented. For example, in Ocaml, the observation says that "let rec" is implemented via an assignment. So, in the examples mentioned earlier, call/cc simply pries open the assignment that was already present in letrec or define. Alone, call/cc cannot emulate assignments. There was a message exactly on the same topic "call/cc is insufficient to emulate set!" posted on comp.lang.scheme two years ago: http://google.com/groups?selm=200103010316.TAA30239%40adric.cs.nps.navy.mil Threads http://google.com/groups?threadm=200102212311.PAA76922%40adric.cs.nps.navy.mil http://google.com/groups?threadm=200102212321.PAA76933%40adric.cs.nps.navy.mil http://google.com/groups?threadm=200102220358.TAA77339%40adric.cs.nps.navy.mil might also be useful. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: foldr
Title: RE: foldr 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:[EMAIL PROTECTED]] Sent: Friday, 02 January, 2004 1:54 PM To: [EMAIL PROTECTED] 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Module creation
J & M van Berchem wrote: > 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. Use a text editor, then load the file with ":load Foo.hs". You can't type definitions into the hugs/ghci interpreter, just expressions; definitions have to be loaded from a file. [Actually, ghci is slightly more liberal; it also allows let forms (e.g. "let foo = ...") and IO actions (e.g. "foo <- getLine").] -- Glynn Clements <[EMAIL PROTECTED]> ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Perspectives on learning and using Haskell
G'day all. Quoting Graham Klyne <[EMAIL PROTECTED]>: > (2) I find that I spend a far greater portion of my time *thinking* about > what I'm trying to do than actually coding it. There used to be an adage > in the software industry that programmer productivity in lines-of-code per > day was independent of programming language: with Haskell, I suspect that > old rule breaks down, because it seems that actually coding has become a > relatively small part of the overall exercise. In theory, that's true of other languages too. Programmers are *supposed* to spend more time doing non-coding than coding (where I don't, for example, count writing unit tests as "coding"). I suspect that this is actually an artifact of your level of experience with Haskell. I know that I used to spend more time thinking than coding. When you get familiar enough, you get to the stage where you can think on your feet. > (4) I have noticed that it's often very easy to write some inefficient code > (sometimes *very* inefficient) to do some task in Haskell, and then to > optimize it. This, I believe, is one of the most unappreciated (by non-declarative programmers, anyway) aspects of declarative programming. It's easy to write could-be-slow code that works first time, once you've fixed all the bugs caught by the compiler. Then, it's straightforward to swap out implementations and replace them with more efficient ones as the need arises. This is possible to do in non-declarative languages. It's even encouraged in "agile" OO methodologies, like XP. However, it's so much less painful in a declarative language, because you're far less tempted to introduce hidden dependencies to begin with. In fact, I find that my "working but slow" code has almost no weird dependencies. I find myself having to _introduce_ them during the "get it faster" phrase. From an engineering point of view, this is almost exactly the right thing, because that way you (in theory) end up with as few dependencies as possible. > (6) I have found that Haskell seems to a particularly effective platform > for pursuing some ideas of extreme programming, There you go. :-) There is only one problem I've found with test-driven development in Haskell. In C++, it's possible to break the "module" abstraction (yes, I know, C++ doesn't have modules; it has classes, which are really instantiable modules) by using "friend". In Haskell, I find myself occasionally having to expose parts of a module which I would prefer not to, in order for the unit tests suite to do their job effectively. I wonder if there might be a way to fix this, say, by allowing modules to selectively expose parts of their interface depending on who wants to use it. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: no continuations
On Tuesday, December 30, 2003 5:04 PM, Kevin S. Millikin [SMTP:[EMAIL PROTECTED] wrote: > Oh, sure. I didn't mean to quibble with the idea that continuations > are computational effects. Just wanted to point out that (I think) > you can't macro express mutation with call/cc, unless you've already > got mutation anyway. [snip] > Yup. If you do that, you can use d as your setter and c as your > getter: > > > (define c (make-cell)) > > (define d c) > > ((d 'set) 9) > > (c 'get) > 9 > > ((d 'set) 17) > > (c 'get) > 17 It sure looks like the example contradicts the assertion, but I happen to know that there is a set! (or some other assignment) in the macro expansion of define. I'm just using call/cc to get at that, rather than getting at the one in the expansion of letrec. Moved to Haskell Cafe. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Module creation
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 advanceJacques van Berchem ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Perspectives on learning and using Haskell
At 17:44 23/12/03 -0500, Derek Elkins wrote: On Tue, 23 Dec 2003 17:26:20 + Graham Klyne <[EMAIL PROTECTED]> wrote: (moved to Haskell-Cafe as this reply might generate several more) > I've spent part of the past few months learning Haskell and developing > a moderately sized application. I came to this from a long background > (20 years or so) of "conventional" programming in a variety of > languages (from Fortran and Algol W to Java and Python). For me, > learning Haskell has been one of the steepest learning curves of any > new language that I have ever learned. Before this project, I was > aware of some aspects of functional programming, but had never > previously done any "in anger" (i.e. for real). Well, the obvious question is: after climbing partway up that curve, what do you think of the view? Was it worth learning? Is it worth continuing to use? Does the code seem 'better' than what you might produce in other languages you've used? I think the view is good :-) Others have written about the advantages of FP, and I won't try to repeat that. My personal observations include: (1) I notice that it's very easy to pick up and use third-party functions; there doesn't seem to be the square peg/round hole effect that one gets with third-party libraries in conventional programming languages. I don't know why this is, but two possibly contributing factors may be: (a) many Haskell expressions are just values, so in some respects they're closer to data than to code. There isn't a procedural aspect to get in the way (e.g. no need to coordinate passage through the "von Neumann bottleneck"?) (b) the type system permits, even encourages, typing details that are not relevant to some function to be left unspecified. (2) I find that I spend a far greater portion of my time *thinking* about what I'm trying to do than actually coding it. There used to be an adage in the software industry that programmer productivity in lines-of-code per day was independent of programming language: with Haskell, I suspect that old rule breaks down, because it seems that actually coding has become a relatively small part of the overall exercise. (3) it has often been noted that despite the influx of "new" programming languages, little is truly new -- the act of programming is pretty much unchanged since, er, the 60's? I know the basic ideas of FP have been around for several decades, but I do think there is some truly new thinking being applied in the area of FP, compared with conventional languages. I think I do see some truly different approaches being explored in the FP community, and some of those do seem to have some real value. (e.g. the way that Monads turn out to be such a flexible idea. I haven't yet started to look at arrows.) Related to this, it seems to me that Haskell's lazy functional model is capable of subsuming many other programming models. One that I discovered quite early was mimicking the test-and-backtrack style of Prolog. More recently, looking at the like of "scrap your boilerplate" ideas, it seems that FP is capable of tackling the separation of "cross-cutting concerns" that seem to motivate the more recent Aspect Oriented Programming ideas, without really adding any new language features. (4) I have noticed that it's often very easy to write some inefficient code (sometimes *very* inefficient) to do some task in Haskell, and then to optimize it. My current project is currently riddled with horrendous inefficiencies, but I don't care because I am confident that I can optimize as and when I need to. (The GHC profiling system is one reason for this confidence, and also the availability of off-the-shelf libraries to improve many of my very inefficient data structures.) (5) working as I do in the area of Internet and Web protocols, I like the idea that I can (often) write code that is closely and "obviously" related to a specification that I'm trying to implement. (This is an area that I'd like to explore further.) (6) I have found that Haskell seems to a particularly effective platform for pursuing some ideas of extreme programming, and in particular test-led development. (I do this very imperfectly, but I'm learning ;-) For example, Dean Herington's unit testing framework seems to fit more comfortably into the host language than, say, the JUnit framework from which it takes its inspiration. Adding new styles of test-case has been a breeze compared with my experience of using JUnit or PyUnit (and I have found those frameworks to be very satisfactory). (7) For the first time since learning Pascal, I'm impressed at how reliable my Haskell code (messy as much of it may be by Haskell standards) has turned out to be. If I sit here longer, I will probably think of more. But, in summary, I think a combination of: - improved language implementations - improved hardware - new ideas about how to use/deploy FP - the nature of some Int
Parsing library
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. --
-- [EMAIL PROTECTED] (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 to
Re: Parsec question
Thanks to Tom for his interesting points. I am still developing an
inuition for how the error reporting goes. (-:
On Thu, 1 Jan 2004, Derek Elkins wrote:
(snip)
> > > testOr3 = do{ try (string "(a"); char ')'; return "(a)" }
(snip)
> example both issues come up. If we successfully parse the
> "(a" then the second alternative "(b)" can't possibly succeed and since
> it can't succeed there's no point in saving the input "(a" to be
> reparsed when backtracking since there's no point in backtracking.
(snip)
Ah, that makes sense - thanks! I think part of my problem might have been
the quoted and real brackets and braces - at least a couple of times, I
thought the char and the return were within the try. (-: I will try to
look more carefully next time.
-- Mark
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Parsec question
On Wed, Dec 31, 2003 at 07:21:54PM -0500, Mark Carroll wrote:
> 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?
testOr3 is a bit better at error reporting, for example:
*> parseTest testOr2 "(a"
parse error at (line 1, column 1):
unexpected "a"
expecting "(b)"
*> parseTest testOr3 "(a"
parse error at (line 1, column 3):
unexpected end of input
expecting ")"
But it still gives silly error messages in some cases:
*> parseTest testOr3 "("
parse error at (line 1, column 1):
unexpected end of input
expecting "(b)"
The original testOr1 is better here:
*> parseTest testOr1 "(a"
parse error at (line 1, column 3):
unexpected end of input
expecting ")"
*> parseTest testOr1 "("
parse error at (line 1, column 2):
unexpected end of input
expecting "a" or "b"
*> parseTest testOr1 ""
parse error at (line 1, column 1):
unexpected end of input
expecting "("
> (BTW, I like Parsec. Thanks, Daan. (-:)
I like Parsec too :)
Tom
--
.signature: Too many levels of symbolic links
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Parsec question
On Wed, 31 Dec 2003 19:21:54 -0500 (EST)
Mark Carroll <[EMAIL PROTECTED]> wrote:
> 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?
As soon as you reach a point where a syntax error means no parse will
succeed you want to commit to that alternative for two reasons. 1) As
long as there appears to be a possibility for an alternative parse the
input needs to be saved and 2) there's no point backtracking if all
other alternatives will fail; it just wastes time. In the above
example both issues come up. If we successfully parse the
"(a" then the second alternative "(b)" can't possibly succeed and since
it can't succeed there's no point in saving the input "(a" to be
reparsed when backtracking since there's no point in backtracking.
Obviously, this example is merely to illustrate the idea as there'd be
little to no inefficiency in this case.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
