- Haskell-Cafe - Haskell.org

Question about use of | in a class declaration
by Guest, Simon 22 Aug '02

22 Aug '02

Hello all, Please could someone explain the meaning of | in this class declaration (from Andrew's example): class (Ord k) => Map m k v | m -> k v where lookupM :: m -> k -> Maybe v I couldn't find reference to this in any of my standard Haskell tutorials, nor the Haskell 98 report. Any references? cheers, Simon -----Original Message----- From: Andrew J Bromage [mailto:ajb@spamcop.net] Sent: 21 August 2002 04:19 To: haskell-cafe(a)haskell.org Subject: Re: Question about sets G'day all. On Tue, Aug 20, 2002 at 10:57:36AM -0700, Hal Daume III wrote: > Lists with arbitrary > elements are possible, but not very useful. After all, what could you do > with them? It's often useful to have containers of arbitrary _constrained_ types, because then you can do something with them. For example, given the class of partial mappings on orderable keys: class (Ord k) => Map m k v | m -> k v where lookupM :: m -> k -> Maybe v instance (Ord k) => Map (FiniteMap k v) k v where lookupM = lookupFM instance (Ord k) => Map [(k,v)] k v where lookupM m k = case [ v | (k',v) <- m, k == k' ] of [] -> Nothing (v:_) -> Just v instance (Ord k) => Map (k -> Maybe v) k v where lookupM = id You can make a list of elements, which can be any type so long as they are a member of that class: data MAP k v = forall m. (Map m k v) => MAP m type ListOfMap k v = [MAP k v] Then you can do things with it: lookupLom :: (Ord k) => ListOfMap k v -> k -> [ Maybe v ] lookupLom xs k = [ lookupM a k | MAP a <- xs ] test :: [Maybe Int] test = lookupLom maps 1 where maps = [ MAP finiteMap, MAP assocListMap, MAP functionMap ] finiteMap = listToFM [(1,2)] assocListMap = [(1,3)] functionMap = \k -> if k == 1 then Just 4 else Nothing It's a little unfortunate that you have to introduce the MAP type here. You can in fact construct a list of this type: type ListOfMap k v = [ forall m. (Map m k v) => m ] But then you can't use the elements in the list because the Haskell type checker can't find the (Map m k v) constraint. Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

7 7

Re: monads, modules, sandboxes
by Richard Uhtenwoldt 21 Aug '02

21 Aug '02

this will be my last message on this topic as I need to stop reading this list for a few months. Alastair Reid writes: >A potential difference (which Richard Uhtenwoldt hints at) is that it >can be hard to control the flow of OS capabilities as the capability >is passed from one process to another to another. This gets >especially tricky when you want policies like 'X can either read files >or use the network but not both' (so X cannot leak secrets learnt from >the filesystem). I think this is why capability OSs have fallen out >of favour in the OS community. I suspect that typesystems are better >able to express and enforce these policies. seems to me capabilities can do that: you just pass to X a capability (pointer) to an object that will return either a read-only capability to the filesystem or a capability to the network inferface but not both. either that or use the revocable-capability pattern twice in such a way that before the first network access happens, the filesystem capability is revoked and before the first filesystem read happens the network access capability is revoked. to flesh out that first alternative a little, the object passed to X could probably be coded up by modifying the following E language function (found at http://www.erights.org/elang/concurrency/race.html) for making "use-once" capabilities. and yes I realize this code is not exactly the essence of conciseness and brevity. > A "once" of a function is a use-once version of that function. Ie, > "once(func)" returns a object that will forward no more than one "run" > message to "func". The two argument form "once(verb, target)" is a > generalization which will forward no more than one "verb" message to > the target. > > For the Miranda Methods, the result of the once (the forwarder > below) must make good decisions about whether to override them and > possibly forward them, or not override them and let them default to > methods on the forwarder. For non-Miranda methods other than the > suppressed method, they are simply forwarded. > > def once { > to (verb, target) :any { > var used := false > def forwarder { > # use the Miranda order/3, though it shouldn't matter > > # use the Miranda optSealedDispatch/1 to protect the target > > # forward getAllegedType/0, though one could argue that, once > # used up, the type shouldn't include the supressed verb > to getAllegedType() :any { > target getAllegedType() > } > > # forward respondsTo, but supress verb. One could argue that res pondsTo > # and getAllegedType() should be consistent with each other. > to respondsTo(verb2, arity) :boolean { > verb != verb2 && target respondsTo(verb2, arity) > } > > # forward printOn/1 > to printOn(out) { target printOn(out) } > > # forward reactToLostClient > to reactToLostClient(problem) { > target reactToLostClient(problem) > } > > # use the Miranda whenMoreResolved/1 to protect the target > > # use the Miranda whenBroken/1 to protect the target > > # use the Miranda yourself/0 to protect the target > > # handle all other messages > match [verb2, args] { > if (verb == verb2) { > if (used) { > throw("used up") > } > used := true > } > E call(target, verb2, args) > } > } > } > > # default to suppressing "run" > to (target) :any { once("run", target) } > } what follows is not so much an explanation as a series of disconnected points that a bright and motivated reader might infer real knowledge from. point 1. I observe that type-systems work is very abstract and formal and if I were doing a type system for secure programming I would definitely look to the capability literature for conceptual guidance. too easy when doing formal work to lose sight of where the juicy "wins" (opportunities) lie and more generally to lose sight of the economic and social implications of the technical work and to start playing a sterile "glass bead game". insight and vision is where the capability literature is very fertile. here I'm speaking of the capability PL literature (much of which is ultimately based on Hewitt) not the older capability OS literature (eg Butler Lampson's paper from the early 1970s) which is all intertwined with hairy OS implementation issues and takes forever to learn, it seems to this languages geek. point 2. Alastair Reid writes: >> I now think the >> body of ideas around capability PLs (again mostly dynamically-typed >> OOPLs these days) is likely to be richer and more scientifically >> fertile for the long term than FP even. > >Can you say more about why you think OOP works better in this regard? >Is it because: >- the only way to act on them is via methods (I'm ignoring most > C++ features and public Java fields here) that is one of the things I like. on the E language list they say that certain languages have the AYCDISAM -- All You Can Do Is Send A Message -- property, which means you can always interpose a new object of arbitary behaviour between any two extant objects --a next level of modularity beyond the ADT. many capability PLs have the AYCDISAM property. the question comes up under AYCDISAM of how can you ever be sure you are talking to the real Bank of America (say) when there can be an arbitrary number of objects on the Network between you and the thing you think is the Bank of America object. note that simply asking a third object, eg, the Federal Reserve object, simply moves the problem. the solution is all elegant and subtle. in fact, ISTR it took bright folk years to figure out. "took years to figure out" is a big turn off to practical programmers, but to me, who would rather be a theoretical physicist than a programmer except programming is more economically important, it is a reccommendation when I can learn relatively few very subtle concepts (of the quality that they took years for a bright group to figure out) rather than many many many tedious uninspiring ungeneralizable details as in say most Linux software. point 3. I judge that it would be much easier (than say Linux) to be the system administrator of a complex "software environment" written to capability principles. you have more control over the environment because each individual software package (each of which is a kind of "guest of the system admin") has less control. for more see http://cap-lore.com/CapTheory/Politics.html point 4. the intellectual framework that underlies much of the capability PLs --Hewitt's Actors model -- is protean enough so that people have written articles that "redo" much of *physics* in Actors terminology and primitives. such protean-ness speaks well for fertility. in summary, I plan to keep on concentrating on the pure FP world because I calculate that it is more certain to gain (slowly: FP is not the Internet of 1993 by a long shot) in economic importance than the capability PL world is. the capability (PL and OS) stuff is either going to explode or remain obscure with obsure being the more likely fate next 6 years, and that makes for unreliable career planning. oh how cynical I have become! -- Richard Uhtenwoldt "It's a mammal thing; you wouldn't understand."

1 0

Re: Question about the use of an inner forall
by Jon Cast 21 Aug '02

21 Aug '02

"Scott J." <jscott(a)planetinternet.be> wrote: > Hi, > I am going to stop this discussion . What counts for me at this > moment is that I know how it works. Alright. > I thank everybody who replied to my email. You're welcome. > As for the discussion about Curry Howard isomorphism and more about > type theory, I shall gladly discuss these things further but than in > private email. Do you mean ``but in private email''? Why? I think that, because of the strong mathematical basis underlying Haskell, these things are on-topic. So, why not let the list profit from the discussion? > Hey, I hope really that I know how it works but this seems to be > confirmed in these emails. > I left Ocamel for Haskell for it's more functional approach. > I think documentation about the features extending Haskell 98 is > very needed for those who want only to program with the > language Haskell. True; unfortunately, too many extensions are documented only in technical papers... > Thx for all replies > Scott Jon Cast

5 6

Leical and syntactic analyzer
by Jonata Goulart 21 Aug '02

21 Aug '02

Does somebody know where can I find an example of a lexical and syntactic analyzer for arithmetic and conditional statements in Haskell? Thanks _________________________________________________________________ Chat with friends online, try MSN Messenger: http://messenger.msn.com

1 0

Re: Fw: Question about the use of an inner forall
by oleg＠pobox.com 21 Aug '02

21 Aug '02

> Leon Smith wrote: > >On Friday 16 August 2002 23:57, Scott J. wrote: > >runST :: forall a ( forall s ST s a) -> a ? > > > >In logic forall x forall y statement(x.y) is equivalent to: > > forall y forall x statement(x,y). > Now, using a different argument, since "s" does not appear free on > the R.H.S of the implication, "forall s" can be moved outside the > implication to quantify over the entire type. I'm afraid I disagree -- in general, we can't move quantifiers in and out with impunity. In our example: all a. ( (all s. ST s a) => a ) === all a. ( !(all s. ST s a) | a ) === all a. ( (exists s. !(ST s a)) | a ) === {using identity (exists x. p) | q === exists x. (p|q) where x is not free in q} === all a. (exists s. (!(ST s a) | a)) === all a. exists s. (ST s a => a) So, the type of runST is runST::exists s. (ST s a -> a) Alas, we can't use 'exists' quantifier in type expressions; therefore, we have to use the round-about trick with forall, on the _left-hand_ side of the implication. > Jon Cast wrote: > Polymorphic types form a sub-typing system, with the basic > sub-typing judgment: > (forall a. S) < [T/a]S I'd like to note a parallel with lambda-Prolog: If S is the set of type declarations and P is the set of program clauses, to prove (forall x::T. G) from <S,P>, we introduce a new unique _constant_ c of type T and attempt to prove [c/x]G from <S U {c},P> OTH, to prove (exists x::T . G) from <S,P>, we prove [_X/x]G from <S,P> where _X is just a (unbound) Prolog variable. We let the standard unification mechanism to bind _X to something that makes G true. On the subject of escaping of quantified variables, the lambda-Prolog Tutorial by Amy Felten gives an interesting example: ?- append (1::2::nil) z X. the answer is X == (1::2::z). ?- pi y\( append (1::2::nil) y X). the answer is NO. Indeed, as outlined before, we first choose a unique constant k and attempt to prove ?- append (1::2::nil) k X. The proof seemingly succeeds, with X bound to (1::2::k). However, this binding causes 'k' to 'escape'. Therefore, this binding is rejected, and the proof falls apart. Which indeed makes sense: the value of X that makes pi y\( append (1::2::nil) y X) true should not depend on any particular value of y. Only in this case the expression would be true for all y. ?- pi y\( append (1::2::nil) y (H y)). actually succeeds, with H bound to w\(1::2::w).

1 0

Re: Question about sets
by Jon Cast 20 Aug '02

20 Aug '02

"Scott J." <jscott(a)planetinternet.be> wrote: > As far a I know sets can implemented by implementing a list of > anything(a list of all types) The sets Haskell does have are AFAIK > sets of elements of the same type: these are not general sets. Ah. That's a static typing issue. However, I don't think it's really an issue. In axiomatic set theory, every set must be a subset of some other set, except for powersets and unions. Unions are implementable using Either, and powersets are implementable using Set (i.e., powerset :: Set a -> Set (Set a)). > Scott Jon Cast

1 0

questions
by Jonata Goulart 20 Aug '02

20 Aug '02

I'm trying to do a simple lex analyser in haskell I defined the function lexi that is intended to break a string into tokens returning them as a list but I received the following error: ERROR "TesteEval.hs":20 - Syntax error in input (unexpected symbol "restante") isLetter:: Char -> Bool isLetter c = or [isLower (c), isUpper (c)] isLetterorDigit:: Char -> Bool isLetterorDigit c = or [isLetter (c), isDigit (c)] main = lexi lexi " "= [] lexi (a:x) | isLetter a = token: lexi restante where S = takeWhile isLetterorDigit x line 20 ------> restante = dropWhile isLetterorDigit x token = 'Id' ++ S _________________________________________________________________ Chat with friends online, try MSN Messenger: http://messenger.msn.com

2 1

Questions about sets
by Scott J. 20 Aug '02

20 Aug '02

As far a I know sets can implemented by implementing a list of anything(a list of all types) The sets Haskell does have are AFAIK sets of elements of the same type: these are not general sets. Scott

1 0

Question about the use of an inner forall
by Scott J. 19 Aug '02

19 Aug '02

Hi, I am going to stop this discussion . What counts for me at this moment is that I know how it works. I thank everybody who replied to my email. As for the discussion about Curry Howard isomorphism and more about type theory, I shall gladly discuss these things further but than in private email. Hey, I hope really that I know how it works but this seems to be confirmed in these emails. I left Ocamel for Haskell for it's more functional approach. I think documentation about the features extending Haskell 98 is very needed for those who want only to program with the language Haskell. Thx for all replies Scott

1 0

Re: Question aboutthe use of an inner forall
by Jon Cast 19 Aug '02

19 Aug '02

"Scott J." <jscott(a)planetinternet.be> wrote: > Well I don't feel alone anymore. > Here follows how I think runST :: (forall s. ST s a) -> a works: > if a is represented by e.g. MutVar s a . Then the compiler complains > because it did find an s in the "data" represented by a. This s must > first be eliminated by some other combinators(?). Right. The `s' is appearing outside the area it is defined in. > I agree that something must be written for the argument of runST to > warn programmers about the possible "representations" of a. But I > still have problems that one has chosen forall. `forall' and `Pi' are the basic names for this sort of thing in type theory. See the discussion of the Howard-Curry isomorphism for `forall'. You probably don't want to know about `Pi'. > Scott Jon Cast

1 0

Re: Question aboutthe use of an inner forall
by Jon Cast 19 Aug '02

19 Aug '02

Jay Cox <sqrtofone(a)yahoo.com> wrote: > From: "Ashley Yakeley" <ashley(a)semantic.org> > > At 2002-08-16 20:57, Scott J. wrote: > > >However what for heaven's sake should I think of > > >runST :: forall a ( forall s ST s a) -> a ? > > runST :: forall a. ((forall s. ST s a) -> a) > > "For all a, if (for all s, (ST s a)) then a." > > You may apply runST to anything with a type of the form (forall > > s. ST s a), for any 'a'. > I'm very fuzzy to the details of type theory in general so please > forgive any errors. > I noted the same question as Scott's when I first learned about > ST threads. > When you have a rank-2 polymorphic function, like > runST::forall a . ( forall s . ST s a) -> a > the type means the function takes an argument ***at least as > polymorphic*** as (forall s . ST s (some type a independent of s)). I'm not sure I understand polymorphic types, but here's my best guess: Polymorphic types form a sub-typing system, with the basic sub-typing judgment: (forall a. S) < [T/a]S where T and S are types, and a may occur free in S, and (<) is the sub-typing relation. From this comes the typing judgment S < T x :: S ----------------- x :: T For the purposes of runST, we only need to worry about one other judgment, the standard judgment for sub-typing function arguments: S < T ------------------- (T -> R) < (S -> R) Justification: basically, the sub-typing statement (S < T) says that every element of S is an element of T. The typing statement (f :: S -> R) says that f can take any value of type S and deliver a value of type R (divergence is a value in Haskell!). Now, if every element of S is an element of T, and f can take every element of T, it follows that f can take every element of S. (x :: S) -> (x :: T) (x :: T) -> (f x :: R) ---------------------------------------------------- (x :: S) -> (f x :: R) is an equivalent way of stating the above judgment. So, runST's types are the super-types of (forall a. (forall s. ST s a) -> a), which means all functions types for which the argument is a super-type of (forall s. ST s a). Does that clarify things any? <snip> Jon Cast

1 0

Re: Question aboutthe use of an inner forall
by Jon Cast 19 Aug '02

19 Aug '02

"Scott J." <jscott(a)planetinternet.be> wrote: > Ok, a and s are type variables. It may be common usage for computer > people Bingo. You're trying to impose a non-CS understanding on a CS statement. If you're familiar with the analogy, it's like a French speaker trying to insist that ``demand'' in English cannot mean an insistence, since it doesn't mean that in English. > but for someone with a math background it is difficult Get used to difficulty. Seriously. > to call forall a a type . In logic one expects a statement in the > scope of forall a like this forall a is not a type (nor a statement) :) It's a phrase in any number of languages, including formal logic and type theory (and it has different, although cognate, meanings in those languages). > (forall a) statement. The statement may or may not depend on a. True. But if you have (forall a. type), that doesn't fit your form. And, just like (forall a. statement) is a statement, (forall a. type) is a type. Easy, no? > So let's come backe to runST. > runST ::( forall s) (ST s a )-> a May I ask a favor? If you're going to discuss type theory, learn our notation: > runST :: (forall s. ST s a) -> a Just a minor nit. > So I insist what is the statement ST s a ? It's not a statement, and forall s. is not a logic quantifier. ST s a is a type, and forall s. is a type quantifier. > Scott Jon Cast

1 0

Re: Fw: Question aboutthe use of an inner forall
by Jon Cast 19 Aug '02

19 Aug '02

Jan Brosius <jscott(a)planetinternet.be> wrote: > Still some question: Ok a is not a type but Integer is a type . > But a can be instantiated to integer. This comes pretty close to > call a therefore a type variable, Isn't it? > And otherwise why writing forall a etc. If s, t are types, the type s -> t says ``give me a value of type s, and I'll give you a value of type t''. If a is a type variable, and (given a is a type) s is a type, then forall a. s says ``give me a type t, and I'll give you a value of type s[t]''. More specifically, if you write > f :: a -> b f has the form (\ x :: a -> (y :: b)), where the \ binds values. If you write > f :: forall a. a f has the form (/\ a -> (x :: a)), where the /\ binds types. Now, runST's argument has type forall s. ST s a. In other words, it's essentially a function over types---and it has to take /any/ type runST wants to hand it. > Regards > Scott Jon Cast

1 0

Newbie question, installing hugs on redhat 7.2
by S H 19 Aug '02

19 Aug '02

I'm trying to install the current version of hugs on a red hat 7.1 system (running on VMWare 2.0.1 on top of Win 2K). I downloaded the file hugs98-Dec2001-1.i386.rpm onto the freshly-installed red hat 7.1 (no other software has been installed). It complains that libreadline.so.4 is needed. The system has the package readline-4.1-9 installed which provides libreadline.so.4.1. It appears to require exactly libreadline.so.4 (not >= 4). So, I tried uninstalling readline-4.1-9 so as to install the older package but it complained (unsurprisingly) that lots of packages rely on readline so it wouldn't erase it. I could try a --force with the erase but that seems a tad drastic. Does anyone know a workaround for this, or please tell me if I'm just doing something stupid. Thanks! Simon Handley Palo Alto, CA, USA __________________________________________________ Do You Yahoo!? HotJobs - Search Thousands of New Jobs http://www.hotjobs.com

4 3

The Curry-Howard Isomorphism
by Leon Smith 19 Aug '02

19 Aug '02

For an explanation why runST has the type it does, see page 4 of Simon Peyton-Jones and John Launchbury's paper "Lazy functional state threads" http://research.microsoft.com/Users/simonpj/Papers/lazy-functional-state-th… On Friday 16 August 2002 23:57, Scott J. wrote: >runST :: forall a ( forall s ST s a) -> a ? > >In logic forall x forall y statement(x.y) is equivalent to: > forall y forall x statement(x,y). True, but that isn't runST's type. "forall a" quantifies over the entire type, whereas "forall s" quantifies over the left hand side of the implication. In other words, you have "forall a. statement(a)", where statement includes a substatement "forall s. substatement(s,a)" Now, using a different argument, since "s" does not appear free on the R.H.S of the implication, "forall s" can be moved outside the implication to quantify over the entire type. However, this brings up an important point about the Curry-Howard Isomorphism, which basically says that types are statements in first-order logic, and the corresponding values are proofs of those statements. When we work in logic, we care mainly about the *statements*. Proofs are ways of justifying new statements. Equivalent statements are in a sense "equal", and can usually be freely substituted for each other. When we have a statement such as P /\ Q, where P and Q are statements such as "John is wearing a kilt" and "John is Scottish", it doesn't really matter which order they come in. Mathematicians generally understand that /\ is commutative, and thus we can use P /\ Q and Q /\ P interchangeably throughout our discussion. (Unless you are writing proofs in certain highly formal proof systems, such as Coq, Isabelle, or Haskell's type system) When we work in type theory, we care mainly about the *proofs*. Statements are ways of constraining our proofs to ensure they are at least somewhat sensible. When we have a type (Int, Char), where Int is the statement "my value is a 32-bit integer", and Char says "my value is a character", order does matter. Here, (4,'H') is a "proof" of the proposition (Int,Char), and ('H', 4) is a proof of the proposition (Char, Int). Although (Int, Char) <=> (Char, Int) are logically equivalent, (4,'H') is a different value than ('H', 4). This equivalence can be "proven" using the function: swap :: (a,b) -> (b,a) swap (x,y) = (y, x) Which, using the Curry-Howard isomorphism, is also a proof that /\ is commutative. In short, just because a type "a" implies type "b", and type "b" implies type "a", doesn't mean they are interchangeable as statements are in logic. Hope this helps, leon

1 0

Re: Question aboutthe use of an inner forall
by Ashley Yakeley 19 Aug '02

19 Aug '02

At 2002-08-18 20:12, Scott J. wrote: >So let's come backe to runST. > >runST ::( forall s) (ST s a )-> a > >So I insist what is the statement ST s a ? Oh it's not really a statement, it just plays a similar role in types that statements play in logic. The comparison runs something like this: type variable variable type statement type constructor function "->" implies application derivation "forall" universal quantification type specialisation specialisation For instance, in logic if you have "A" and you have "A implies B", you can derive "B". Likewise, if you have a value of type "a", and a value of type "a -> b", by using function application you can obtain a value of type "b". The type theory has the same structure as the logic, merely a different interpretation. -- Ashley Yakeley, Seattle WA

2 1

Re: Question aboutthe use of an inner forall
by Ashley Yakeley 19 Aug '02

19 Aug '02

At 2002-08-18 20:19, Jay Cox wrote: >#ST> runST (newSTRef (3::Prelude.Int)) ># >#Ambiguous type variable(s) `a' in the constraint `PrelShow.Show a' >#arising from use of `PrelIO.print' at <No locn> >#In a 'do' expression pattern binding: PrelIO.print it I don't understand this either, actually: $ ghci -fglasgow-exts -package lang ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.04, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Loading package haskell98 ... linking ... done. Loading package lang ... linking ... done. Prelude> :module ST Prelude ST> :type runST Inferred type is less polymorphic than expected Quantified type variable `s' escapes Expected type: ST s a -> t Inferred type: (forall s1. ST s1 a) -> a Prelude ST> What's up with that? Can't I even look at the type? Is this the monomorphism restriction or something? -- Ashley Yakeley, Seattle WA

1 0

Fw: Question aboutthe use of an inner forall
by Scott J. 19 Aug '02

19 Aug '02

Again a typo. Please read something like MutVar s Bool. Sorry Scott ----- Original Message ----- From: Scott J. To: Jay Cox Cc: haskell-cafe(a)haskell.org Sent: Monday, August 19, 2002 5:41 AM Subject: Re: Question aboutthe use of an inner forall Well I don't feel alone anymore. Here follows how I think runST :: (forall s. ST s a) -> a works: if a is represented by e.g. MutVar s a . Then the compiler complains because it did find an s in the "data" represented by a. This s must first be eliminated by some other combinators(?) . I agree that something must be written for the argument of runST to warn programmers about the possible "representations" of a. But I still have problems that one has chosen forall. Scott ----- Original Message ----- From: "Jay Cox" <sqrtofone(a)yahoo.com> To: "Scott J." <jscott(a)planetinternet.be>; "Haskell Cafe List" <haskell-cafe(a)haskell.org> Sent: Monday, August 19, 2002 5:19 AM Subject: Re: Question aboutthe use of an inner forall > > ----- Original Message ----- > From: "Ashley Yakeley" <ashley(a)semantic.org> > To: "Scott J." <jscott(a)planetinternet.be>; "Haskell Cafe List" > <haskell-cafe(a)haskell.org> > Sent: Friday, August 16, 2002 11:15 PM > Subject: Re: Question aboutthe use of an inner forall > > > > At 2002-08-16 20:57, Scott J. wrote: > > > > >However what for heaven's sake should I think of > > > > > >runST :: forall a ( forall s ST s a) -> a ? > > > > runST :: forall a. ((forall s. ST s a) -> a) > > > > "For all a, if (for all s, (ST s a)) then a." > > > > You may apply runST to anything with a type of the form (forall s. ST s > > a), for any 'a'. > > I'm very fuzzy to the details of type theory in general so please forgive > any errors. > > I noted the same question as Scott's when I first learned about ST threads. > > When you have a rank-2 polymorphic function, like > > runST::forall a . ( forall s . ST s a) -> a > > the type means the function takes an argument ***at least as polymorphic*** > as > (forall s . ST s (some type a independent of s)). If (runST stthread ) has > type String, then stthread must at least have type ST s String. > > Why do you need this apparent mumbo jumbo about Rank-2 polymorphism? It > insures your ST threads are threadsafe (or so I have been led to believe). > You will not be able to throw a mutable reference outside of the thread. > > take this long interaction from ghci (the ST> is the prompt, and what > follows > on the same line is the code entered. For instance :type gives the type of > the following code. I have separated ghci input/ouput from comments by > placing # in front of the IO). > > #ST> :type newSTRef (3::Prelude.Int) > #forall s. ST s (STRef s PrelBase.Int) > > The type variable a is replaced by, or a has the value of, (STRef s > PrelBase.Int) but this depends on s. > > #ST> :type readSTRef > #forall s a. STRef s a -> ST s a > #ST> :type (do x<-newSTRef (3::Prelude.Int);readSTRef x) > #forall s. ST s PrelBase.Int > > a here is replaced by PrelBase.Int. the code in the do statement is runnable > with runST > > #ST> runST (newSTRef (3::Prelude.Int)) > # > #Ambiguous type variable(s) `a' in the constraint `PrelShow.Show a' > #arising from use of `PrelIO.print' at <No locn> > #In a 'do' expression pattern binding: PrelIO.print it > # > #<interactive>:1: > # Inferred type is less polymorphic than expected > # Quantified type variable `s' escapes > # It is reachable from the type variable(s) `a' > # which is free in the signature > # Signature type: forall s. ST s a > # Type to generalise: ST s1 (STRef s1 PrelBase.Int) > # When checking an expression type signature > # In the first argument of `runST', namely > # `(newSTRef (3 :: PrelBase.Int))' > # In the definition of `it': runST (newSTRef (3 :: PrelBase.Int)) > > above is a demonstration of how the type checking prevents > using/reading/modifying references outside of the ST world. > > I realize this is a bit of an incomplete explanation: Some questions I > would like to answer to help your comprehension but cannot due to my > ignorance are: > > 1. how do you measure the polymorphic nature of a type so that you can say > it is "at least as polymorphic"? I have a fuzzy idea and some examples (Num > a => a vs. forall a . a vs. forall a . [a], etc.) but I haven't yet found > out for myself a precise definition. > 2. what does it mean that type variable "escapes", and why is it bad? A > reasonable answer isn't popping into my head right now. Something about how > the type of a program should be fully resolved pops into my head but nothing > cohesive. > > Maybe that helps. > > Jay Cox > > >

1 0

Re: Question aboutthe use of an inner forall
by Ashley Yakeley 19 Aug '02

19 Aug '02

At 2002-08-16 20:57, Scott J. wrote: >However what for heaven's sake should I think of > >runST :: forall a ( forall s ST s a) -> a ? runST :: forall a. ((forall s. ST s a) -> a) "For all a, if (for all s, (ST s a)) then a." You may apply runST to anything with a type of the form (forall s. ST s a), for any 'a'. -- Ashley Yakeley, Seattle WA

3 3

Re: Question aboutthe use of an inner forall
by Ashley Yakeley 19 Aug '02

19 Aug '02

At 2002-08-18 18:19, Scott J. wrote: >A question: s is not a type variable as a isn't it? Both are quantified type variables. But only one of those quantifiers can be placed at the top level of the expression. runST :: forall a. ((forall s. ST s a) -> a) > I mean a can be of type Integer while s cannot. Well yes, you can specialise "forall a" to Integer. So runST can be specialised to this type: runST ::[special] (forall s. ST s Integer) -> Integer ...whereas you cannot specialise "s" in the same way. Think of it in terms of logic, if for all a: f(a), then by simple specialisation f(Integer). -- Ashley Yakeley, Seattle WA

2 1

Re: Fw: Question aboutthe use of an inner forall
by Ashley Yakeley 19 Aug '02

19 Aug '02

At 2002-08-18 19:15, Jan Brosius wrote: >Still some question: Ok a is not a type but Integer is a type . But a can >be > instantiated to integer. This comes pretty close to call a therefore a type > variable, Isn't it? "a" is a type variable. "Integer" is a type. "forall a. a" is also a type, but frequently "forall"s at the top level are elided. -- Ashley Yakeley, Seattle WA

1 0

Fw: Question aboutthe use of an inner forall
by Scott J. 19 Aug '02

19 Aug '02

Sorry there are two mailers on this machine Regards SCott ----- Original Message ----- From: "Jan Brosius" <jscott(a)planetinternet.be> To: "Jon Cast" <jcast(a)ou.edu> Cc: <haskell-cafe(a)haskell.org> Sent: Monday, August 19, 2002 4:15 AM Subject: Fw: Question aboutthe use of an inner forall > Still some question: Ok a is not a type but Integer is a type . But a can > be > instantiated to integer. This comes pretty close to call a therefore a type > variable, Isn't it? > > And otherwise why writing forall a etc. > > Regards > > Scott > > ----- Original Message ----- > From: "Scott J." <jscott(a)planetinternet.be> > To: "Jon Cast" <jcast(a)ou.edu> > Cc: <haskell-cafe(a)haskell.org> > Sent: Monday, August 19, 2002 4:09 AM > Subject: Re: Question aboutthe use of an inner forall > > > > Still some question: Ok a is a type and Integer is a type . But a can be > > instantiated to integer. This comes pretty close to call a therefore a > type > > variable. > > > > Regards > > > > Scott > > > > ----- Original Message ----- > > From: "Jon Cast" <jcast(a)ou.edu> > > To: "Scott J." <jscott(a)planetinternet.be> > > Cc: "Ashley Yakeley" <ashley(a)semantic.org>; <haskell-cafe(a)haskell.org> > > Sent: Monday, August 19, 2002 3:48 AM > > Subject: Re: Question aboutthe use of an inner forall > > > > > > > "Scott J." <jscott(a)planetinternet.be> wrote: > > > > A question: s is not a type variable as a isn't it? I mean a can be > > > > of type Integer while s cannot. > > > > > > Guessing at your question: > > > > > > a has no type (and neither does s); it /is/ a type. In Haskell, types > > > have kinds. And, both a and s have kind *. > > > > > > Now then, the user can instantiate a to Integer, yes. And the user > > > cannot instantiate s to anything---that's what the `forall' is for. > > > runST will (theoretically) instantiate s to something. That could be > > > Integer if the language implementors felt like it. The user of runST > > > certainly has to be prepared for the possibility. > > > > > > Does that come close to answering your question? > > > > > > > Regards, > > > > > > > Scott > > > > > > Jon Cast > > > _______________________________________________ > > > Haskell-Cafe mailing list > > > Haskell-Cafe(a)haskell.org > > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

1 0

Fw: Question aboutthe use of an inner forall
by Jan Brosius 19 Aug '02

19 Aug '02

Still some question: Ok a is not a type but Integer is a type . But a can be instantiated to integer. This comes pretty close to call a therefore a type variable, Isn't it? And otherwise why writing forall a etc. Regards Scott ----- Original Message ----- From: "Scott J." <jscott(a)planetinternet.be> To: "Jon Cast" <jcast(a)ou.edu> Cc: <haskell-cafe(a)haskell.org> Sent: Monday, August 19, 2002 4:09 AM Subject: Re: Question aboutthe use of an inner forall > Still some question: Ok a is a type and Integer is a type . But a can be > instantiated to integer. This comes pretty close to call a therefore a type > variable. > > Regards > > Scott > > ----- Original Message ----- > From: "Jon Cast" <jcast(a)ou.edu> > To: "Scott J." <jscott(a)planetinternet.be> > Cc: "Ashley Yakeley" <ashley(a)semantic.org>; <haskell-cafe(a)haskell.org> > Sent: Monday, August 19, 2002 3:48 AM > Subject: Re: Question aboutthe use of an inner forall > > > > "Scott J." <jscott(a)planetinternet.be> wrote: > > > A question: s is not a type variable as a isn't it? I mean a can be > > > of type Integer while s cannot. > > > > Guessing at your question: > > > > a has no type (and neither does s); it /is/ a type. In Haskell, types > > have kinds. And, both a and s have kind *. > > > > Now then, the user can instantiate a to Integer, yes. And the user > > cannot instantiate s to anything---that's what the `forall' is for. > > runST will (theoretically) instantiate s to something. That could be > > Integer if the language implementors felt like it. The user of runST > > certainly has to be prepared for the possibility. > > > > Does that come close to answering your question? > > > > > Regards, > > > > > Scott > > > > Jon Cast > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Re: Question aboutthe use of an inner forall
by Jon Cast 19 Aug '02

19 Aug '02

"Scott J." <jscott(a)planetinternet.be> wrote: > A question: s is not a type variable as a isn't it? I mean a can be > of type Integer while s cannot. Guessing at your question: a has no type (and neither does s); it /is/ a type. In Haskell, types have kinds. And, both a and s have kind *. Now then, the user can instantiate a to Integer, yes. And the user cannot instantiate s to anything---that's what the `forall' is for. runST will (theoretically) instantiate s to something. That could be Integer if the language implementors felt like it. The user of runST certainly has to be prepared for the possibility. Does that come close to answering your question? > Regards, > Scott Jon Cast

2 1

Question aboutthe use of an inner forall
by Scott J. 17 Aug '02

17 Aug '02

Hi, It goes about the State tansformer monad ST s a. I think how it works but as a logician the use of an internal forall is difficult to swallow. Let's first see a statement in Haskell. One can type foo :: a -> b as a function We can be not sloppy (but this gives unnecessary clutter in the program I think) and type it as: forall a,b foo :: a -> b Now this is a statement in logic, it can be true or false. However what for heaven's sake should I think of runST :: forall a ( forall s ST s a) -> a ? In logic forall x forall y statement(x.y) is equivalent to: forall y forall x statement(x,y). Why the use of the inner forall in runST?This is not a normal function declaration in mathematics. Since Haskell is Hindley-Milner typed and can't use an inner forall . Why the use an inner forall. Has imagination dried up (sorry, if this seems impolite)? Thx Scott

1 0

RE: question about parsing integers and floats with Parsec
by Harris, Andrew 16 Aug '02

16 Aug '02

Hi - After a bit of monkeying around, it seems the following parser works to detect both integers and floats, both positive and negative. I'm sure you wizards have many better ways of doing this. Anyway here it is for your amusement: import Parsec import qualified ParsecToken as P import ParsecLanguage (emptyDef) lexer = P.makeTokenParser emptyDef integer = P.integer lexer float = P.float lexer genericgrab :: Parser (Either Integer Double) genericgrab = try ( do { n <- char '-' ; f <- float ; return (Right (-f)) } ) <|> try ( do { f <- float ; return (Right f) } ) <|> try ( do { f <- integer ; return (Left f) } ) -andrew > -----Original Message----- > From: Harris, Andrew [mailto:Andrew.Harris@jhuapl.edu] > Sent: Thursday, August 15, 2002 6:55 PM > To: 'haskell-cafe(a)haskell.org' > Subject: question about parsing integers and floats with Parsec > > > Hi - > > This isn't a pure "Haskell" question, but I'm trying to use the > Parsec library to parse out space separated numbers, which > could be integers > or floats and either positive or negative. I was using the > "naturalOrFloat" > lexeme parser from the ParsecToken module, until I realized > that it doesn't > seem to handle negative integers. I've been poking with > trying to pair the > integer and float lexeme parsers with try() blocks, but I > ain't no parsing > expert and am not making good progress. > > Any help/hints would be appreciated! > > thanks, > -andrew > > --- > Andrew Harris andrew.harris(a)jhuapl.edu > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

question about parsing integers and floats with Parsec
by Harris, Andrew 16 Aug '02

16 Aug '02

Hi - This isn't a pure "Haskell" question, but I'm trying to use the Parsec library to parse out space separated numbers, which could be integers or floats and either positive or negative. I was using the "naturalOrFloat" lexeme parser from the ParsecToken module, until I realized that it doesn't seem to handle negative integers. I've been poking with trying to pair the integer and float lexeme parsers with try() blocks, but I ain't no parsing expert and am not making good progress. Any help/hints would be appreciated! thanks, -andrew --- Andrew Harris andrew.harris(a)jhuapl.edu

2 1

RE: Text in Haskell: a second proposal
by Simon Marlow 15 Aug '02

15 Aug '02

[ moving to haskell-i18n(a)haskell.org ] > For ISO-8859-1 each Char is exactly one Word8, so surely it > would work fine with partial reads? > > decodeCharISO88591 :: Word8 -> Char; > > encodeCharISO88591 :: Char -> Word8; > > decodeISO88591 :: [Word8] -> [Char]; > decodeISO88591 = fmap decodeCharISO88591; > > encodeISO88591 :: [Char] -> [Word8]; > encodeISO88591 = fmap encodeCharISO88591; Sorry, I thought you were just using ISO8859-1 as an example. > >This is better: it doesn't force you to use lazy I/O, and when > >specialised to the IO monad it might get decent performance. The > >problem is that in general I don't think you can assume the lack of > >state. For example: UTF-7 has a state which needs to be retained > >between characters, and UTF-16 and UTF-32 have an endianness > state which > >can be changed by a special sequence at the beginning of the > file. Some > >other encodings have states too. > > But it is possible to do this in Haskell... > > The rule for the many functions in the standard libraries seems to be > "implement as much in Haskell as possible". Why is it any > different with the file APIs? I think we've lost track of the discussion here... I'll try to summarise. I think character encoding/decoding should be built-in to the I/O system. I also think there should be a low-level I/O interface that doesn't do any encoding, and high-level interfaces to the various encodings. Now, you can by all means specify the high-level I/O in terms of the low-level I/O + encodings, but I strongly suspect that implementing it that way will be expensive. Character I/O in Haskell is *already* very slow (see Doug Bagely's language shootout for evidence), and I don't want to add another factor of 2 or more to that. The point is that by building encoding into the I/O interface the implementor gets the opportunity to optimise. Cheers, Simon

1 0

RE: Analyzing Efficiency
by Simon Marlow 14 Aug '02

14 Aug '02

> I've come up with three different methods of approach to > solve the same > problem in haskell. I would like to compare the three in > terms of reductions, > memory usage, and overall big O complexity. > > What's the quickest way to gather these stats? I usually use the ghc > compiler, but also have hugs installed. The big O complexity > probably has to > be done by hand, but maybe there's a tool out there to do it > automagically. Apart from the "normal" ways (profiling, Unix 'time', GHC's +RTS -sstderr), here's another one I've been using recently: cachegrind. It's the wonderful cache profiling extension by Nick Nethercote that comes with Julian Seward's Valgrind. The great thing is that you don't even need to recompile the program - you just do 'cachegrind <program>', and it runs (very slowly) and outputs reliable cache statistics including how many instructions were executed. Get it from http://developer.kde.org/~sewardj/ Oh, it only works on Linux BTW. Cheers, Simon

1 0

Analyzing Efficiency
by Shawn P. Garbett 14 Aug '02

14 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I've come up with three different methods of approach to solve the same problem in haskell. I would like to compare the three in terms of reductions, memory usage, and overall big O complexity. What's the quickest way to gather these stats? I usually use the ghc compiler, but also have hugs installed. The big O complexity probably has to be done by hand, but maybe there's a tool out there to do it automagically. Shawn - -- You're in a maze of twisty little statements, all alike. Public Key available from http://www.garbett.org/public-key -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iD8DBQE9WU0BDtpPjAQxZ6ARAkTKAJ9qixYy5MT5QGyJ/95NGLNgVTECCQCfVVVV GHELk++jO8XzaWUbp/mb9Og= =MYjn -----END PGP SIGNATURE-----

2 1

RE: Text in Haskell: a second proposal
by Ashley Yakeley 14 Aug '02

14 Aug '02

At 2002-08-13 04:13, Simon Marlow wrote: >That depends what you mean by efficient: these functions represent an >extra layer of intermediate list between the handle buffer and the final >[Char], and furthermore they don't work with partial reads - the input >has to be a lazy stream gotten from hGetContents. For ISO-8859-1 each Char is exactly one Word8, so surely it would work fine with partial reads? decodeCharISO88591 :: Word8 -> Char; encodeCharISO88591 :: Char -> Word8; decodeISO88591 :: [Word8] -> [Char]; decodeISO88591 = fmap decodeCharISO88591; encodeISO88591 :: [Char] -> [Word8]; encodeISO88591 = fmap encodeCharISO88591; >> A monadic stream-transformer: >> >> decodeStreamUTF8 :: (Monad m) => m Word8 -> m Char; >> >> hGetChar h = decodeStreamUTF8 (hGetWord8 h); >> >> This works provided each Char corresponds to a contiguous block of >> Word8s, with no state between them. I think that includes all the >> standard character encoding schemes. > >This is better: it doesn't force you to use lazy I/O, and when >specialised to the IO monad it might get decent performance. The >problem is that in general I don't think you can assume the lack of >state. For example: UTF-7 has a state which needs to be retained >between characters, and UTF-16 and UTF-32 have an endianness state which >can be changed by a special sequence at the beginning of the file. Some >other encodings have states too. But it is possible to do this in Haskell... The rule for the many functions in the standard libraries seems to be "implement as much in Haskell as possible". Why is it any different with the file APIs? -- Ashley Yakeley, Seattle WA

1 0

Newbie question on "statefullness"
by Alex Peake 14 Aug '02

14 Aug '02

I am new to Haskell. I want to do something very simple (I thought) but got lost in the world of Monads. I want to implement something like the C idea of: n += i So how does one doe this in Haskell? Thanks, Alex

8 11

Re: Analyzing Efficiency
by Shawn P. Garbett 13 Aug '02

13 Aug '02

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 13 August 2002 01:37 pm, you wrote: > > I would like to compare the three in terms of reductions, memory > > usage, and overall big O complexity. > > I wouldn't use number of reductions as a guide if I was you. Number of reductions does make a difference in this case, because it's a simple test problem with three equivalent implementations (in the same compiler). Nothing to create confusion like a system call, well actually all three solutions must call a set of IO calls in the same order. So I think it would make a good baseline comparison. I do agree that it's not a good general measurement of efficiency, and really doesn't reflect the scalability of the solution either (whereas big O notation would). Thanks for the heads up though. The other tips and hints you gave me are exactly what I was looking for. No I just need a huge data set to pump into so it does a significant amount of garbage collection, and memory management... Shawn Garbett - -- You're in a maze of twisty little statements, all alike. Public Key available from http://www.garbett.org/public-key -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) iD8DBQE9WVM5DtpPjAQxZ6ARAn2XAJ98Y4jNmnCocHzHEFpUM/vN3kTGmACfTnkf Vk3m8x1OYHGyckskR4DDKQo= =OWav -----END PGP SIGNATURE-----

1 0

RE: Text in Haskell: a second proposal
by Simon Marlow 13 Aug '02

13 Aug '02

> At 2002-08-09 03:26, Simon Marlow wrote: > > >Why combine I/O and {en,de}coding? Firstly, efficiency. > > Hmm... surely the encoding functions can be defined efficiently? > > decodeISO88591 :: [Word8] -> [Char]; > encodeISO88591 :: [Char] -> [Word8]; -- uses low octet of > codepoint > > You could surely define them as native functions very efficiently, if > necessary. That depends what you mean by efficient: these functions represent an extra layer of intermediate list between the handle buffer and the final [Char], and furthermore they don't work with partial reads - the input has to be a lazy stream gotten from hGetContents. I don't want to be forced to use lazy I/O. > A monadic stream-transformer: > > decodeStreamUTF8 :: (Monad m) => m Word8 -> m Char; > > hGetChar h = decodeStreamUTF8 (hGetWord8 h); > > This works provided each Char corresponds to a contiguous block of > Word8s, with no state between them. I think that includes all the > standard character encoding schemes. This is better: it doesn't force you to use lazy I/O, and when specialised to the IO monad it might get decent performance. The problem is that in general I don't think you can assume the lack of state. For example: UTF-7 has a state which needs to be retained between characters, and UTF-16 and UTF-32 have an endianness state which can be changed by a special sequence at the beginning of the file. Some other encodings have states too. Cheers, Simon

1 0

Fw: Modification of State Transformer
by Scott J. 12 Aug '02

12 Aug '02

----- Original Message ----- From: "Scott J." <jscott(a)planetinternet.be> To: "Shawn P. Garbett" <Shawn(a)Garbett.org> Sent: Monday, August 12, 2002 9:04 PM Subject: Re: Modification of State Transformer > I 'm sorry, > > What I meant was discussion about the state transformer ST s a itself. And > how it works. What does mean the second inner forall loop and so on. I can't > find explanations of this in the Haskell library. > > Regards > > Scott > ----- Original Message ----- > From: "Shawn P. Garbett" <Shawn(a)Garbett.org> > To: "Scott J." <jscott(a)planetinternet.be> > Cc: <haskell-cafe(a)haskell.org> > Sent: Monday, August 12, 2002 4:19 PM > Subject: Re: Modification of State Transformer > > > > -----BEGIN PGP SIGNED MESSAGE----- > > Hash: SHA1 > > > > On Sunday 11 August 2002 07:26 pm, Scott J. wrote: > > > Hi, > > > > > > I invite you then to explain what happens with every step. > > > > > > The use of "forall" is misleading and fast to be misunderstood: I > mention > > > here the inner forall's. > > > > > > Thx > > > > > > Scott > > > > This list is great. The implementation in the ST module solves the > > > > problem and I understand how it works. > > > > > > > > Shawn > > > > Given the level of detailed explanations to date, I don't see the point. > But > > I'll go ahead and do so anyway, by summarizing what I've learned from the > > previous posts. > > > > I had read the example in Bird'd book on state transformers. The > definition > > of state however was a fixed type in the examples. Wanting to extend the > > definition and make it more general I was trying to figure out how to > modify > > the type. > > > > Bird's definition was: > > newtype St a = MkSt (State -> (a,State)) > > type State = type > > > > I had attempted to extend the type as follows > > newtype St a s = MkSt (s -> (a,s)) > > > > This died in the compiler when declaring this type as an instance of > Monad: > > instance Monad St where > > return x = MkSt f where f s = (x,s) > > p >>= q = MkSt f where f s = apply(q x) s' > > where (x,s') = apply p s > > ghc returned the following (referencing the instance line): > > Couldn't match `*' against `* -> *' > > Expected kind: (* -> *) -> * > > Inferred kind: (* -> * -> *) -> * > > When checking kinds in `Monad St' > > In the instance declaration for `Monad St' > > > > When a type constructor has an argument it has a type of `* -> *'. > > When a type constructor has two arguments it has a type of `* -> * -> *'. > > This construction of the type can be extended to n arguments by having the > > number of `->' match the n arguments of type and the `*' be n+1. > > > > The class definition of Monad contains the following: > > class Monad m where > > return :: a -> m a > > (>>=) :: m a -> (a -> m b) -> m b > > > > > > So the class of St a s needs reduction from `* -> * -> *' to `* -> *' to > fit > > the single argument type constructor of the Monad class. By using (St a) > > which causes the type constructor to be of type `(* -> *) -> *'. Since > `(* -> > > *)' can be used as `*', by creation of another type. This because > equivalent > > to `* -> *'. > > > > The only thing left is reversing the order so that the result type is of > the > > correct form in the Monad usage. I.e, in my initial ordering the `return' > of > > the Monad would end up returning something of type `s' which is not > > particularly useful, since type `a' is the desired return type from the > > transformer. > > > > So the corrected version of State becomes: > > newtype St s a = MkSt (s -> (a, s)) > > > > instance Monad (St s) where > > ... > > > > Shawn Garbett > > - -- > > You're in a maze of twisty little statements, all alike. > > Public Key available from http://www.garbett.org/public-key > > -----BEGIN PGP SIGNATURE----- > > Version: GnuPG v1.0.7 (GNU/Linux) > > > > iD8DBQE9V8P4DtpPjAQxZ6ARAq0VAJ9toEiEm+d58vgbKEofzXBISyXrEACfasbc > > eaEg2zVi9y90vk+fXKGSrt0= > > =OrwN > > -----END PGP SIGNATURE----- > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

2 1

Re: Modification of State Transformer
by Jon Cast 12 Aug '02

12 Aug '02

"Shawn P. Garbett" <listman(a)garbett.org> wrote: > I'm trying to modify Richard Bird's state transformer. The example > in his book (_Introduction_to_Functional_Programming_using_Haskell_) > has State defined as a explicit type. > I.e. Here's the relevant snippet: > -- State transformer definition > newtype St a = MkSt (State -> (a, State)) > type State = Int > -- State transformer applied to state > apply :: St a -> State -> (a, State) > apply (MkSt f) s = f s > -- State monad > instance Monad St where > return x = MkSt f where f s = (x,s) > p >>= q = MkSt f where f s = apply (q x) s' > where (x, s') = apply p s > ----------------------------------------- > What I want is something like this, so that the state transformer > has a generic state type: Btw: This has already been done, in GHC: see the ST module in GHC's library <http://www.haskell.org/ghc/docs/latest/html/base/Control.Monad.ST.html>. To answer your specific question, though: > newtype St a s = MkSt (s -> (a, s)) These are in the wrong order (see below); you want: > newtype St s a = MkSt (s -> (a, s)) > apply :: St a s -> s -> (a, s) > apply (MkSt f) s = f s Again, s/St a s/St s a/. > instance Monad St where > return x = MkSt f where f s = (x,s) > p >>= q = MkSt f where f s = apply (q x) s' > where (x, s') = apply p s > ----------------------------------------------------------- > The trouble occurs on the instance line > Couldn't match `*' against `* -> *' > Expected kind: (* -> *) -> * > Inferred kind: (* -> * -> *) -> * > When checking kinds in `Monad St' > In the instance declaration for `Monad St' > Failed, modules loaded: none. Right. The problem here is that St is a type constructor with two arguments (i.e., of kind (* -> * -> *)), whereas Monad wants a type constructor with one argument (i.e., of kind (* -> *)). Hence the error. This is the same type of error you'd get if you tried to declare an instance for `Eq Tree', where `Tree' is a standard (polymorphic) BST. The way you solve that is to instantiate `Eq (Tree a)', and it's the same thing here: instantiate `Monad (St s)'. Of course, you need to switch the order of the arguments to St first (as done above), so Haskell knows `s' is a the state type, not the result type. HTH Jon Cast

3 3

Re: Newbie question on "statefullness"
by Ashley Yakeley 12 Aug '02

12 Aug '02

At 2002-08-11 23:48, I wrote: >>I want to implement something like the C idea of: >>n += i >> >>So how does one doe this in Haskell? > > do { > val <- readIORef n; > writeIORef n (val + i); > }; Or even... modifyIORef n ((+) i); -- Ashley Yakeley, Seattle WA

1 0

Re: Newbie question on "statefullness"
by Ashley Yakeley 12 Aug '02

12 Aug '02

At 2002-08-11 17:36, Alex Peake wrote: >I want to implement something like the C idea of: >n += i > >So how does one doe this in Haskell? do { val <- readIORef n; writeIORef n (val + i); }; -- Ashley Yakeley, Seattle WA

1 0

Haskell-Cafe -- confirmation of subscription -- request 321501
by Cyril Baratoff 09 Aug '02

09 Aug '02

1 0

Combining type constraints
by Andrew J Bromage 09 Aug '02

09 Aug '02

G'day all. I have a large number of functions all of which use the same set of type constraints, such as: > foo :: (Monad m, Ord t, Show t) => ... Ideally, I'd like to combine them into one typeclass. At the moment, I'm using the equivalent of: > class (Monad m, Ord t, Show t) => Constraints m t where { } > instance (Monad m, Ord t, Show t) => Constraints m t where { } > foo :: (Constraints m t) => ... This requires undecidable instances. Is there a way to do this that doesn't require non-98 features apart from multi-parameter type classes? If not, is there an argument for a language construction which supports this idiom, analogous to type synonyms, except for type classes? Cheers, Andrew Bromage

1 0

Transformations of cyclic graphs [Was: Efficiency of list indices in definitions]
by oleg＠pobox.com 09 Aug '02

09 Aug '02

[Moved to Haskell-Cafe] Hello! Cycles sure make it difficult to transform graphs in a pure non-strict language. Cycles in a source graph require us to devise a way to mark traversed nodes -- however we cannot mutate nodes and cannot even compare nodes with a generic ('derived') equality operator. Cycles in a destination graph require us to keep track of the already built nodes so we can complete a cycle. An obvious solution is to use a state monad and IORefs. There is also a monad-less solution, which is less obvious: we can't add a node to the dictionary of constructed nodes until we have built the node, then means we can't use the updated dictionary when building descendants -- which need the dictionary when linking back. The problem can be overcome however with a credit card transform (a.k.a. "buy now, pay later" transform). To avoid hitting the bottom, we just have to "pay" by the "due date". The will use as an example the NFA->DFA transformation considered earlier. Perhaps we should first attempt a few obvious optimizations of a NFA/DFA recognizer. It seems that performance matters. finAuAcceptStringQ startStates string = or [faStateAcceptStringQ s string | s <- startStates] where faStateAcceptStringQ (FaState _ acceptQ _) [] = acceptQ faStateAcceptStringQ (FaState _ _ trans) (a:as) | null followerStates = False | otherwise = or [ faStateAcceptStringQ s as | s <- followerStates ] where followerStates = if a > (length trans) - 1 then [] else trans!!a Computing (length trans) when determining the followerStates is inefficient: even if 'a' is zero, we still have to traverse the whole list 'trans'. If our alphabet is binary, perhaps its better to specialize the FaState correspondingly and write: -- Automata over a binary alphabet data (Ord l,Show l) => FaState l = FaState {label :: l, acceptQ :: Bool, trans0:: [FaState l], trans1:: [FaState l]} -- Then a finite automaton is merely a list of starting FaStates: type FinAu l = [FaState l] --So, for example, an automaton equivalent to the regular expression --0*(0(0+1)*)* could be defined as: dom18 = [one] where one = FaState 1 True [one,two] [] two = FaState 2 True [two,one] [one,two] The acceptance function can be written as finAuAcceptStringQ start_states str = foldr (\l seed -> acceptP l str || seed) False start_states where acceptP (FaState _ acceptQ _ _) [] = acceptQ acceptP (FaState _ _ t0 t1) (s:rest) = finAuAcceptStringQ (if s then t1 else t0) rest We have simplified the original expression, and manually deforested it. test1= finAuAcceptStringQ dom18 $ map (>0) [0,1,0,1] test2= finAuAcceptStringQ dom18 $ map (>0) [1,1,0,1] test3= finAuAcceptStringQ dom18 [True] test4= finAuAcceptStringQ dom18 [False] It would be great to be able to compare and print the nodes: instance (Ord l,Show l) => Eq (FaState l) where (FaState l1 _ _ _) == (FaState l2 _ _ _) = l1 == l2 but printing a node is already a slight problem. We need to keep track of the already printed nodes to avoid looping. -- a data class for an occurrence check class OCC occ where empty:: occ a seenp:: (Eq a) => a -> occ a -> Bool put:: a -> occ a -> occ a -- Currently, it's just a list. -- In the future, we can pull in something fancier from the Edison instance OCC [] where empty = [] seenp = elem put = (:) -- Depth-first, pre-order traversal of the graph, keeping track of -- already printed nodes instance (Ord l,Show l) => Show (FaState l) where show state = "{@" ++ showstates [state] (empty::[FaState l]) "@}" where -- showstates worklist seen_states suffix showstates [] states_seen suffix = suffix showstates (st:rest) states_seen suffix | st `seenp` states_seen = showstates rest states_seen suffix showstates (st@(FaState l accept t0 t1):rest) states_seen suffix = showstate st $ showstates (t0++t1++rest) (st `put` states_seen) suffix showstate (FaState l accept t0 t1) suffix = "{State " ++ (show l) ++ " " ++ (show accept) ++ " " ++ (show $ map label t0) ++ " " ++ (show $ map label t1) ++ "}" ++ suffix Now, "print dom18" prints as [{@{State 1 True [1,2] []}{State 2 True [2,1] [1,2]}@}] For the NFA->DFA conversion, we need to keep track of already built states. -- A dictionary of states class StateDict sd where emptyd :: sd (l,FaState l) locate :: (Eq l) => l -> sd (l,FaState l) -> Maybe (FaState l) putd :: (l,FaState l) -> sd (l,FaState l) -> sd (l,FaState l) -- if performance matters, we can use a fancier dictionary from the Edison instance StateDict [] where emptyd = [] locate = lookup putd = (:) -- [nfa_state] -> dictionary_of_seen_states -> ([dfa_state],updated_dictionary) -- [dfa_state] is a singleton list determinize_cc states converted_states = -- first, check the cache case dfa_label `locate` converted_states of Nothing -> build_state Just dfa_state -> ([dfa_state],converted_states) where -- [NFA_labels] -> DFA_labels det_labels = sort . nub . (map label) dfa_label = det_labels states -- find out NFA-followers for [nfa_state] upon ingestion of 0 and 1 (t0_followers,t1_followers) = foldr (\st (f0,f1) -> (trans0 st ++ f0, trans1 st ++ f1)) ([],[]) states acceptQ' = or (map acceptQ states) -- really build the dfa state and return ([dfa_state],updated_cache) build_state = let -- node, dfa_state is computed _below_ converted_states1 = (dfa_label,dfa_state) `putd` converted_states (t0', converted_states2) = (determinize_cc t0_followers converted_states1) (t1', converted_states3) = (determinize_cc t1_followers converted_states2) dfa_state = (FaState dfa_label acceptQ' t0' t1') in ([dfa_state],converted_states3) finAuDeterminize states = fst $ determinize_cc states [] At the heart of the credit card transform is the phrase converted_states1 = (dfa_label,dfa_state) `putd` converted_states we added to the dictionary of the computed states the state that we haven't built yet. Because (,) is non-strict in its arguments and `locate` is non-strict in its result, we can get away with a mere promise to "pay". We can print the DFA for dom18 to see what we've got: finAuDeterminize dom18 -- shows [{@{State [1] True [[1,2]] [[]] } {State [1,2] True [[1,2]] [[1,2]]} {State [] False [[]] [[]] }@}] which is a DFA (which happens to be minimal) recognizing (0+1)* - 1(0+1)* An example from the original message: dom19 = [one,two] where one = FaState 1 True [two] [] two = FaState 2 True [one] [one] finAuDeterminize dom19 -- shows [{@{State [1,2] True [[1,2]] [[1]] } {State [1] True [[2]] [[]] } {State [2] True [[1]] [[1]] } {State [] False [[]] [[]] }@}] which recognizes (0+1)* - (0+1)*11(0+1)*

1 0

Modification of State Transformer
by Shawn P. Garbett 08 Aug '02

08 Aug '02

I'm trying to modify Richard Bird's state transformer. The example in his book (_Introduction_to_Functional_Programming_using_Haskell_) has State defined as a explicit type. I.e. Here's the relevant snippet: -- State transformer definition newtype St a = MkSt (State -> (a, State)) type State = Int -- State transformer applied to state apply :: St a -> State -> (a, State) apply (MkSt f) s = f s -- State monad instance Monad St where return x = MkSt f where f s = (x,s) p >>= q = MkSt f where f s = apply (q x) s' where (x, s') = apply p s ----------------------------------------- What I want is something like this, so that the state transformer has a generic state type: newtype St a s = MkSt (s -> (a, s)) apply :: St a s -> s -> (a, s) apply (MkSt f) s = f s instance Monad St where return x = MkSt f where f s = (x,s) p >>= q = MkSt f where f s = apply (q x) s' where (x, s') = apply p s ----------------------------------------------------------- The trouble occurs on the instance line Couldn't match `*' against `* -> *' Expected kind: (* -> *) -> * Inferred kind: (* -> * -> *) -> * When checking kinds in `Monad St' In the instance declaration for `Monad St' Failed, modules loaded: none.

3 3

Unicode
by ck15 08 Aug '02

08 Aug '02

Hi, Is there a way to include symbols like set union , set intersection etc in Haskell code ? Chitra

3 2

Jcreator
by Scott J. 06 Aug '02

06 Aug '02

Hi, can Jcreator be used also with GHC or only with Hugs as an IDE for Haskell? Thx Scott

1 0

multiple C compilers
by Scott J. 06 Aug '02

06 Aug '02

Hi, This is perhaps an idiot question , but I would like to know if one has to stick with one c compiler or if one can use different c compilers for Haskell2C ? Thx Scott

1 0

freeTR.com Artist olmak icin evden kacan Turk kizlarinin Beyoglunda cekilmis Acik sacik Cinsel birlesme iceren Videolari Date: Sun, 04 Aug 2002 19:57:21 +0300
by mimi 04 Aug '02

04 Aug '02

http://www.freeTR.com Artist olmak icin evden kacan Turk kizlarinin Beyoglunda cekilmis Acik sacik Cinsel birlesme iceren Videolari icin: http://www.freeTR.com

1 0

Fw: extenssions of Haskell
by Scott J. 04 Aug '02

04 Aug '02

Hi, I have allready read a lot of Haskell 98. What I cannot find are papers about the State transformer monad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GTK2? bindins. Are rpms for redhat also installable for MandrakeLinux .? Are there Haskell IDE's ? Sorry for thr typo's ----- Original Message ----- From: Scott J. To: haskell-cafe(a)haskell.org Sent: Sunday, August 04, 2002 1:41 AM Subject: extenssions of Haskell Hi, I have allrewdy read a lot of Haskell 98. What I cannot find are papers about the State transformermonad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GYK2? bindins. Are rpms for redhat also installable for MandrakeLinux .?

1 0

extenssions of Haskell
by Scott J. 04 Aug '02

04 Aug '02

Hi, I have allrewdy read a lot of Haskell 98. What I cannot find are papers about the State transformermonad in its present form and papers about rank m polymorphism. Thx Scott P.S. Where can I find the windows library for HOpenGL and Haskell+GYK2? bindins. Are rpms for redhat also installable for MandrakeLinux .?

1 0

[Xemacs] x-symbol mode for Haskell
by Jorge Adriano 04 Aug '02

04 Aug '02

Hi, I've always liked the X-Symbol package for Xemacs http://x-symbol.sourceforge.net/ I've searched for Haskell X-Symbol modes, but there doesn't seem to be one. It's kind of strange because it seems to me like most people who are into haskell would like to use non-ascii symbols like greek letters and some nice looking operators - just take a look at some haskell books, LaTeX modes for haskell etc. I tried to hack an x-symbol haskell mode. *I know nothing about elisp* or x-symbol internals so the mode is bloated with useless stuff and *does not works* properly (yet?). It is in fact just a very dirty non working hack... right now I just can't spend much time with it. I thought I'd ask if anyone (preferably with more experience :) is doing, or thinking about doing some good haskell x-symbol mode. J.A. P.S.: Just in case you want to take a look at it here to understand what it is supposedd to do, it goes in attchment. After installing it try typing something like f :: Num _alpha => [_alpha] -> [_alpha] f x = x+x The _alphas will turn into real alphas as you type them, the => and -> will also turn into good looking non-ascii arrows. :) The main problem is that the source file is not beeing saved correctly (decode token works, but not encode token), so you're not going to be able to compile it. Of course there are many other problems like <= turning into an arrow instead of a "less than equal", etc etc etc :) How to install it: X-Symbol: - download the latest x-symbol version. - run xemacs as root - M-x package-admin-add-binary-package (it will tell you the directory where it is installed) The quick-dirty-non-usable-x-symbol-haskell-mode :) - save the "x-symbol-haskell.el" and "x-symbol-hooks.el" files - compile them (open in xemacs, right click buffer, byte-compile this file) - copy (as root) the .el and .elc files to the directory where your other x-symbol .el and .elc files are. You may want to back up your old "x-symbol-hooks.el" file. To "use" it just "M-x x-symbol-mode" in an haskell buffer and type away.

1 0

RE: can a lazy language give fast code?
by Simon Marlow 01 Aug '02

01 Aug '02

> Can one write withthe Haskell compliler faster code than in > the examples of http://www.bagley.org/~doug/shootout/ where > GHC (old Haskell 98?) seems to be much slower than Ocaml or > Mlton both strict functional languages. > Can one expect any improvements in speed in the future? Many of those programs can be written differently to improve performance. One issue that is affecting performance in several cases is the speed of character I/O, and the representation of Strings as lists of characters. Dramatic improvements can be had by using unboxed arrays of Char (Data.Array.Unboxed), or PackedString (which these days is implemented using unboxed arrays in GHC). Cheers, Simon

6 10