Re: Export lists in modules
On 28/02/06, Johannes Waldmann <[EMAIL PROTECTED]> wrote:
> Cale Gibbard wrote:
>
> > This is exactly why lists are so common. If people ask why lists are
> > so common in lazy functional languages, they ought also to ask why
> > loops are so common in imperative languages.
>
> A loop is a sequence of actions. In FP, I don't typically have actions,
> rather I collect values, so I'd need several collections types,
> among them: sequences, and among them: classical left-biased lists.
Sure you do, you have pure functions, there are lots of those.
Further, you have things like sequence, which turns a list of monadic
actions into a monadic action returning a list of results, and mapM,
which is just mapping a function to construct those actions over a
list before sequencing them.
Numerical algorithms involving iteration can get quite a lot of
flexibility out of lists, using them to represent the output and
intermediate values of the algorithm at each iteration. These lists
are lazy of course, so that you can just take as many iterations off
as you need, and since it's so nicely explicit, it's comparatively
easy to determine where you'd like to chop, and to apply higher-order
methods of reducing error.
See "Why Functional Programming Matters" for some brilliant examples.
http://www.math.chalmers.se/~rjmh/Papers/whyfp.html
>
> I admit that my typical Haskell program does use such lists
> all over the place, but mostly in monad comprehensions:
> do x <- ... ; guard ; let ... ; return ...
> and often it's a list only because there is no such syntactical
> convenience for, e. g. Sets.
> (I have to write lots of setToList/mkSet, which look plain ugly.)
>
> Even if I really want sequences, I rarely rely on the
> left-biased representation. (E. g. in the above example,
> there's no visible pattern matching on the 'cons'.)
Then perhaps you're missing out :) It sounds like you might be using
lists like a strict functional programmer would, but not really
relying on the laziness aspect. When you start doing so, it becomes
much more apparent why lists are so special, and, for the many of the
places where they work, AVL trees, for example, just wouldn't do. (Not
that there's anything against AVL trees, it's just that they're not
any kind of a substitute for lists in these common lazy functional
programming cases.)
>
> For reference, in Java, List<> is an interface, not a type
> (it has instances like LinkedList<> and ArrayList<>).
>
> And, there's nice syntactic sugar for looping
> over collections: Collection c; for (E item : c) { ... }
> (it hides the pre-1.5 Iterator.hasNext/next stuff.
> I'd say this is an example of moving away from a left-biased
> representation, or at least freeing the programmer from having
> to think about it).
None of that is lazy, so it just isn't the same thing at all. The
important point is that the elements and structure of the collection
are being constructed one at a time as you iterate over it, and they
are easily garbage collected as soon as you're done with them. That's
what allows you to say "hey, these are actually loops which just
haven't happened yet". Only a list can really easily provide that for
linear iteration through a collection of values. Certain trees can
come close, (with a logarithmic additional space hit) and trees are
quite useful for directed searching, but they don't replace the high
position that lists have, just as non-linear forms of recursion don't
quite replace common linear recursion. (Look at some imperative
programs and count the loops and linear recursions compared with the
number of general recursive functions which are not linear recursive.)
Lists in the list-monad/list-comprehension usage are nearly trees
anyway, due to the means by which they are computed, but you can
always think of them as simple lists, or even as single
nondeterministic values (due to the monadic structure), which is
pretty neat. You can prune the tree by guards or the empty list, and
branch by using bind. In some sense, you're defining a long reified
loop which is strung along the leaves of a nonlinear recursive call
tree. You're not forced to look at it that way, though, which makes
things easy to think about when you're actually programming. It's also
what makes the list monad (and isomorphic nondeterminism monads)
really powerful.
- Cale
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
Johannes Waldmann <[EMAIL PROTECTED]> wrote:
> For reference, in Java, ... there's nice syntactic sugar for looping
> over collections: Collection c; for (E item : c) { ... }
> I'd say this is an example of moving away from a left-biased
> representation, or at least freeing the programmer from having
> to think about it).
In Haskell, this is called 'fmap'. :-)
Regards,
Malcolm
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re[2]: overlapping instances and constraints
Hello John, Tuesday, February 28, 2006, 4:23:24 AM, you wrote: >> i had plans to propose the same and even more: >> >> instance C2 a b | a/=b JM> I was thinking it would be all kinds of useful if we had two predefined JM> classes JM> class Eq a b JM> class NEq a b JM> where Eq has instances exactly when its two types are equal and NEq has JM> instances exactly when its two types are not equal. JM> Eq should be straightforward to implement, declaring any type JM> automatically creates its instances. (sort of an auto-deriving). NEq JM> might be more problematic as that would involve a quadratic number of JM> instances so its implementation might need to be more special. but JM> perhaps we can do with just 'Eq'. with 'Eq' class we can't do anything that is impossible without it :))) the whole devil is to make general instance NON-OVERLAPPING with specific one by EXPLICITLY specifying EXCLUSIONS with these "/=" rules: class Convert a b where cvt :: a->b instance Convert a a where -- are we need Eq here? :) cvt = id instance (NEq a b) => Convert a b where cvt = read.show ... yes, i recalled! my proposal was to allow "!" in instance headers: instance C Int where ... instance (!Int a, Integral a) => C a where ... instance (!Integral a, Enum a) => C a where ... adding your Eq class, it will be all we can do on this way interesting, that the language theoretics can say about decidability, soundness, and so on of this trick? :) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: overlapping instances and constraints
instance C2 a b | a/=b I was thinking it would be all kinds of useful if we had two predefined classes class Eq a b class NEq a b where Eq has instances exactly when its two types are equal and NEq has instances exactly when its two types are not equal. class Eq a b instance Eq a a class NEq a b instance Fail a => NEq a a instance NEq a b class Fail all -- no instances I think I first saw that class Fail trick in an HList talk. but having those instances doesn't help if they are not used (eg, by following instance constraints, to aid in overlap resolution, or to confirm FDs; or simply because the system doesn't use the fact that Fail never has instances). Even just extending Eq/NEq to type-level predicates (with a 3rd, functionally dependent parameter) runs into trouble. I'd prefer to extend the language so that those uses become expressible, but for the short term, it'd be nice if the predicates _and_ their uses were built-in. hence the special syntax to indicate that this predicate is actually looked at when checking the instance. cheers, claus Eq should be straightforward to implement, declaring any type automatically creates its instances. (sort of an auto-deriving). NEq might be more problematic as that would involve a quadratic number of instances so its implementation might need to be more special. but perhaps we can do with just 'Eq'. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: realToFrac issues
On Tue, Feb 28, 2006 at 12:44:04AM -0500, Cale Gibbard wrote: > I'm almost scared to ask: does this mean we need negative zero as well? good point. probably. > This change means that Rational is no longer a field. It makes me feel > uneasy at least. Should we really expect realToFrac to propagate those > values? Look at its type: > realToFrac :: (Real a, Fractional b) => a -> b > Nothing about the Fractional class would seem to indicate that NaN and > +-Infinity should be representable. In fact, it just looks like the > basic field operations, and fields don't tend to have such elements > (not that we require the field axioms to hold for every instance). It makes me uneasy too. Perhaps we can come up with something better. > I personally don't see any reason that realToFrac should propagate the > special error condition values of IEEE floating point types. Given its > type, I'd expect it to throw an exception. well, the main reason is that it is the only way we have to convert between various floating point types. If we can come up with another mechanism then perhaps that is a better solution, but it is not at all obvious to me what that other mechanism would be. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
Malcolm Wallace wrote:
> Johannes Waldmann <[EMAIL PROTECTED]> wrote:
>> For reference, in Java, ... there's nice syntactic sugar for looping
>> over collections: Collection c; for (E item : c) { ... }
> In Haskell, this is called 'fmap'. :-)
OK, then show me an "instance Functor Set" so that I can use it :-)
--
-- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 --
http://www.imn.htwk-leipzig.de/~waldmann/ ---
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
On Tue, Feb 28, 2006 at 08:52:00AM +0100, Johannes Waldmann wrote: > Cale Gibbard wrote: > > > This is exactly why lists are so common. If people ask why lists are > > so common in lazy functional languages, they ought also to ask why > > loops are so common in imperative languages. > > A loop is a sequence of actions. In FP, I don't typically have actions, > rather I collect values, so I'd need several collections types, > among them: sequences, and among them: classical left-biased lists. I think the point was that lists in haskell trancend just being a collection type or a data structure. They are a generally useful tool for composing functions. And like cale said, they often subsume loops and all sorts of other control constructs. I mean, even a for loop in haskell is done as mapM action [0..10] I'd say _most_ uses of lists are deforested away because they are used to express control and dataflow and arn't actually used as persistant structures. demoting them to just being a 'collection type' would be a disservice. That they can be used as a collection is a bonus, but not their main feature. the foldr/build trick for deforesting lists is really really cool! look at ghc core, it is amazing how all your lists just disapear and are turned into clever function compositions I would have never thought of :) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
Cale Gibbard wrote: > important point is that the elements and structure of the collection > are being constructed one at a time as you iterate over it, and they > are easily garbage collected as soon as you're done with them. OK, I kind of buy that argument. Though the very word "deforestation" indicates that it might work for structures other than left-biased lists... -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- http://www.imn.htwk-leipzig.de/~waldmann/ --- ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
Johannes Waldmann <[EMAIL PROTECTED]> wrote: > > In Haskell, this is called 'fmap'. :-) > > OK, then show me an "instance Functor Set" so that I can use it :-) instance Function Set where fmap = Data.Set.mapMonotonic Ok, so this introduces a precondition on the function being mapped, so there is a proof obligation on the programmer. But if contexts-on-datatypes worked correctly, data Set a = Ord a => then even the "real" map from Data.Set: map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b could be an instance method of Functor. (Because the Ord constraints would be packaged inside the Set type, rather than needing to be explicit.) Regards, Malcolm ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
instance Functor Set, was: Re: Export lists in modules
Malcolm Wallace wrote: > But if contexts-on-datatypes worked correctly, > > data Set a = Ord a => > > then even the "real" map from Data.Set: > > map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b > > could be an instance method of Functor. I'd love that. But I don't quite understand: do you think this is/should be possible with: current Haskell? Haskell-Prime? Current ghc (what extensions)? -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- http://www.imn.htwk-leipzig.de/~waldmann/ --- ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: realToFrac issues
Cale Gibbard wrote: This change means that Rational is no longer a field. It makes me feel uneasy at least. Should we really expect realToFrac to propagate those values? Look at its type: realToFrac :: (Real a, Fractional b) => a -> b Nothing about the Fractional class would seem to indicate that NaN and +-Infinity should be representable. In fact, it just looks like the basic field operations, and fields don't tend to have such elements (not that we require the field axioms to hold for every instance). I know for a fact that the Ratio type excludes 1%0 and 0%0 from the allowed values by design rather than by mistake. I discussed it with Joe Fasel many years ago, and he convinced me it was a bad idea. But I admit that the realToFrac argument carries some weight, even if I had never even thought about the problem before. -- Lennart ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: instance Functor Set, was: Re: Export lists in modules
> > But if contexts-on-datatypes worked correctly, > > > > data Set a = Ord a => > > > > then even the "real" map from Data.Set: > > > > map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b > > > > could be an instance method of Functor. > > I'd love that. But I don't quite understand: > do you think this is/should be possible with: > current Haskell? Haskell-Prime? Current ghc (what extensions)? It is not possible currently, because of the H'98 language definition. I do think it would be nice to fix this in Haskell-prime. However, although the idea is somewhat related to Polymorphic Components http://hackage.haskell.org/trac/haskell-prime/wiki/PolymorphicComponents there is no specific proposal about this issue on the wiki. (It was mentioned on some mailing list in the last couple of months, but I can't find the thread now.) By "working correctly" I mean that: it is a wart in Haskell'98 that you can declare a datatype to require some class constraints on contained elements, but that these extra constraints do not really buy you any expressive power. They just force you to repeat the same context decl on every function that uses such a type. Ideally, the data decl should be more like an "alias", capturing the constraints as part of the semantics associated with the type, so that you don't need to mention the constraints at every usage location of the type. Of course, there are some details to work out, about where you can validly omit the constraints, and where they are still required. Regards, Malcolm ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Export lists in modules
John Meacham wrote: I mean, even a for loop in haskell is done as mapM action [0..10] I'd say _most_ uses of lists are deforested away because they are used to express control and dataflow and arn't actually used as persistant structures. Yes, they are optimized away when ghc actually works. :) At the moment this seems to be broken (try length[1..n] in 6.4.1). -- Lennart ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re[2]: overlapping instances and constraints
Hello Claus, Tuesday, February 28, 2006, 1:54:25 PM, you wrote: CR> class NEq a b CR> instance Fail a => NEq a a CR> instance NEq a b i think that this definition just use ad-hoc overlapping instances resolution mechanism that we want to avoid :))) -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: the MPTC Dilemma (please solve)
It's very hard to follow you here. is it really? perhaps you're not trying hard enough: > - for each FD a given constraint is subject to, the range types > should be ignored during instance selection: the domain types > of the FD constitute the inputs and are sufficient to compute > unique FD range types as outputs of the type relation. the > computed range types may then be compared with the range > types given in the original constraint to determine whether the > constraint can be fulfilled or not is there a simpler way to put the idea? whatever way you formalize (n+1)-parameter classes "C t1..tn t(n+1)" with an FD "t1..tn -> t(n+1)", my suggestion is to formalize it in almost the same way, but treating parameter (n+1) differently. instead of checking checking for validity of instances wrt constraints of the form "C r1..rn r(n+1)" (where ri are the concrete types arising), check that any constraint "C r1..rn x" (where x is a free, but instantiable variable) will yield zero or one instantiations for x. then, when you have a constraint "C r1..rn r(n+1)", use something like this instead: "exists x. (C r1..rn x && x==r(n+1)" there, that's just as long, and not much clearer than saying that t1.. tn should be treated as inputs to and t(n+1) as an output of the inference process. Can you formalize your proposal below such that we can verify some formal results (e.g. tractable inference, coherence etc). I'd like to, but you're not giving me anything to work with. for instance, your "the TC to CHR translation" carefully omits all the features currently under discussion here. Why not be "macho" and use a formal framework in which this all can be expressed? because I'm the humble programmer and you're the mighty formalist?-) I don't find this style of discussion constructive. I'm interested in language design, so actually I do want to look at both theory and practice, but I'm most interested in using a language I can think in and thinking in a language I can use. for the present context, that is Haskell. if you prefer to think in CHRs, that's fine, but why do you expect me to translate for you? > ...make type classes a syntactic > representation of their semantic domain. What do you mean? Explaining type classes in terms of type classes? This can't work. that is neither what I meant, not what I said. semantics maps from some existing syntactic domain (here Haskell type classes) to some semantic domain (eg, QTs or CHRs), in order to help understand the former in terms of the latter and its nice theory. semantics-based language design maps from some semantic domain to some to be constructed syntactic domain, in order to help expressing the former in terms of the latter, preferably inheriting the elegance of the formers nice theory. QTs explain type classes, but QTs are more elegant, simple and expressive than current type class practice. most of Mark's extentions to type classes were based on this difference, as were most of his advanced programming techniques. I try to read current Haskell type classes as an immature, to be improved, representation of type predicate entailment, and where there are discrepancies, I prefer not to complicate the semantics, but to simplify the syntax. so, when I talk about "=>" in haskell, I think about predicate entailment in QT. and usually, I talk about cases where I can't map current practice to what predicate entailment would lead me to expect. In your previous email, you mentioned the Theory of Qualified Types (QT) and CHRs as formal type class frameworks but you seem to be reluctant to use either of these frameworks. Why? am I? give me a version of CHRs that accurately covers current type class practice, and I'll try to express my modifications. but you won't be able to do that until we have pinned down what current practice is. which is what I'm trying to do here.. In case, people don't know CHRs. Here's the type class to CHR translation. there is no "the" translation. and this one omits all the interesting features under discussion here (MPTCs with flexible instances, FDs, overlap resolution), and worse, includes optimizations based on those omissions. 1) For each class C => TC t we generate a propagation CHR rule TC t ==> C Ex: class Eq a => Ord a translates to rule Ord a ==> Eq a note that this is a case of encoding current syntax-level practice (of early, eager checking, then using) in the semantics. as I've argued in previous email discussing this, it seems quite possible to interpret implication as implication, if you are willing to accept more programs as valid. I think that would simplify the language. 2) For each instance C => TC t we generate a simplification CHR rule TC t <==> C Ex: instance Eq a => Eq [a] translates to rule Eq [a] <==> Eq a this should be: for each instance C => TC t rule TC t <= C you can combine those to for all known instanc
RE: Export lists in modules
On 28 February 2006 13:37, Lennart Augustsson wrote: > John Meacham wrote: >> >> I mean, even a for loop in haskell is done as >> mapM action [0..10] >> >> I'd say _most_ uses of lists are deforested away because they are >> used to express control and dataflow and arn't actually used as >> persistant structures. > > Yes, they are optimized away when ghc actually works. :) At the > moment this seems to be broken (try length[1..n] in 6.4.1). Known bug (well, known since a few weeks ago at least). http://cvs.haskell.org/trac/ghc/ticket/683 Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell'-private] pragmas and annotations (RE: the record system)
"Simon Marlow" <[EMAIL PROTECTED]> wrote:
> How does ENCODING work for a UTF-16 file, for example?
> We don't know the file is UTF-16 until we read the ENCODING pragma,
> and we can't read the ENCODING pragma because it's in UTF-16.
Use the same type of heuristic as XML uses (for instance).
* If the first three bytes of the file are "{-#", then keep reading in
ASCII/Latin-1/whatever until you discover an ENCODING decl (or not).
* If the first six bytes of the file are one of the two possible
UTF-16 representations of "{-#", then assume UTF-16 with that
byte-encoding until we find the ENCODING decl. (A missing decl in
this case would be an error.)
* If the first twelve bytes of the file are a UCS-4 representation of
"{-#" then ... you get the picture.
* For UTF-16 and UCS-4 variations, you must also permit the file to
begin with an optional byte-order mark (two or four bytes).
* Otherwise, there is no ENCODING pragma, so assume the implementation
default of {ASCII, Latin-1, UTF-8, ...}.
I know it's pretty horrible, but it seems to work in practice for the
XML people. In practice, the ENCODING decl is most needed for those
that have ASCII as a subset - one could argue that the heuristic tells
you the UTF-16 and UCS-4 variations without needing a pragma. (But
then, how would you guarantee that the first three characters in the
file must be "{-#" ?)
Regards,
Malcolm
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Re[2]: overlapping instances and constraints
On 2/28/06, Bulat Ziganshin <[EMAIL PROTECTED]> wrote: > Tuesday, February 28, 2006, 1:54:25 PM, you wrote: > CR> class NEq a b > CR> instance Fail a => NEq a a > CR> instance NEq a b > > i think that this definition just use ad-hoc overlapping instances > resolution mechanism that we want to avoid :))) Actually, it illustrates beautifully why ad-hoc overlapping doesn't work. There are two interpretations, the desired one, and one that just ignores the the first and uses the second for everything. -- Taral <[EMAIL PROTECTED]> "Computer science is no more about computers than astronomy is about telescopes." -- Edsger Dijkstra ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell'-private] pragmas and annotations (RE: the record system)
Malcolm.Wallace wrote:
> (But then, how would you guarantee that the first three characters
> in the file must be "{-#" ?)
In particular, what do you propose for literate source?
(I hardly have any .hs files.)
As far as I can see,
it seems to be possible to get LaTeX to work with UTF8;
the (apparently not extremely active) ``Unicode TeX project'' Omega
apparently started out with ``16-bit Unicode'' (http://omega.enstb.org/)
and now turned to 31-bit characters (http://omega.cse.unsw.edu.au/omega/),
and the future may of course bring us other variants...
(Isn't it great that we can add a new dimension to Wadler's law
by discussing character encodings? ;-)
Wolfram
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
RE: the MPTC Dilemma (please solve)
You addressed this to me -- but I'm an advocate for rather conservative
extensions whereas you are calling for extensions that go beyond what
any current implementation can do.
Anyway, there is already a ticket for overlapping instances, I think --
why don't you just add to that.
If you send me Wiki-marked-up text I'll gladly paste it in for you.
Simon
| -Original Message-
| From: Claus Reinke [mailto:[EMAIL PROTECTED]
| Sent: 25 February 2006 15:33
| To: Simon Peyton-Jones
| Cc: haskell-prime@haskell.org
| Subject: Re: the MPTC Dilemma (please solve)
|
| | Is the behaviour of GHC with -fallow-undecidable-instances (and
| | -fcontext-stack) well-understood and specifiable?
| >I would not say that it's well-specified, no.
|
| to start improving that situation, could we please have a task ticket
| for "document differences in unconstrained instance handling", then
| ask everyone to attach source examples showing such differences?
| [can guests attach code to task tickets?]
|
| the hope being, of course, that implementations nominally providing
| the same feature will eventually converge on providing the same
| interpretation of all programs using that feature.
|
| an example of the current oddities (at least they seem odd to me;):
| both hugs and ghc claim to resolve overlapping instances in favour
| of the most specific instance declaration. both claim that functional
| dependencies uniquely determine the range types from the domain
| types. but they do not agree on which programs to accept when
| we try to combine best-match with FDs.
|
| I've already given an example where ghc allows me to define
| record selection, while hugs complains that the overlap violates
| the FDs.
|
| I reported that as a hugs bug, because I think the best-match
| resolution of overlaps should ensure that the FD violation cannot
| happen, so the code should be valid. there are different ways to
| interpret FDs (something to check, or something to use), but it
| seemed that ghc was doing the right thing there. thread start:
|
| http://www.haskell.org//pipermail/hugs-bugs/2006-February/001560.html
|
| but after further experimentation, I'm not longer sure that ghc
| is doing the right thing for the right reasons. here is a tiny example
| of one of the disagreements:
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C a b | a -> b
| instance C a b
|
| so what is ghc doing there? is it going to guarantee that b will
| always be uniquely determined?
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C b | -> b where c :: b
| instance C b where c = error "b"
|
| safely m = m `CE.catch` print
| main = do
| safely $ print $ (c::Int)
| safely $ print $ (c::Bool)
| safely $ print [id,c]
|
| oh, apparently not. unless b is uniquely determined to be universally
| quantified, and the instantiations happen "after" instance selection.
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C b | -> b where c :: b
| instance C b where c = error "b"
|
| class D a where d :: a -> String
| instance C a => D a where d a = "a"
| instance C Int => D Int where d a = "Int"
|
| -- try at ghci prompt: (d 1,d (1::Int))
| -- gives: ("a","Int")
|
| so that parameter of C isn't all that unique. at least not long enough
| to influence instance selection in D.
|
| comments?
|
| cheers,
| claus
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: realToFrac issues
On 28/02/06, John Meacham <[EMAIL PROTECTED]> wrote: > On Tue, Feb 28, 2006 at 12:44:04AM -0500, Cale Gibbard wrote: > > I'm almost scared to ask: does this mean we need negative zero as well? > > good point. probably. > > > This change means that Rational is no longer a field. It makes me feel > > uneasy at least. Should we really expect realToFrac to propagate those > > values? Look at its type: > > realToFrac :: (Real a, Fractional b) => a -> b > > Nothing about the Fractional class would seem to indicate that NaN and > > +-Infinity should be representable. In fact, it just looks like the > > basic field operations, and fields don't tend to have such elements > > (not that we require the field axioms to hold for every instance). > > It makes me uneasy too. Perhaps we can come up with something better. > > > I personally don't see any reason that realToFrac should propagate the > > special error condition values of IEEE floating point types. Given its > > type, I'd expect it to throw an exception. > > well, the main reason is that it is the only way we have to convert > between various floating point types. If we can come up with another > mechanism then perhaps that is a better solution, but it is not at all > obvious to me what that other mechanism would be. How about, toRealFloat :: (RealFloat a, RealFloat b) => a -> b toRealFloat = uncurry encodeFloat . decodeFloat Presently, this doesn't quite work, but that's due to the inability of encodeFloat to produce pairs which mean NaN and -0. If we extend its codomain a bit to include those, that would seem fine. It would seem to me that if we want a conversion between IEEE floating point types, then it should be somewhere around here in the hierarchy anyway. - Cale ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: realToFrac issues
John Meacham wrote: On Tue, Feb 28, 2006 at 12:44:04AM -0500, Cale Gibbard wrote: I'm almost scared to ask: does this mean we need negative zero as well? good point. probably. If the point is to allow floating-point conversion to go through Ratio correctly, you might have to do that. However, I would think long and hard before actually doing this. We tried exactly this in Maple (introduce -0 in the rationals, after having implemented fully IEEE-754 floats/doubles/etc), and that broke the system in a huge number of weird ways that we could not hope to 'fix' in a sensible manner. So we backed that one change out (ie this was implemented internally, and the resulting system was completely broken for about a month as we tried to make sense of the resulting mess, then backed it out). My current belief is that floats are such a "non algebraic" (from a mathematical point of view) type that it is hopeless to try to get it to inter-operate with algebraic types (ie Fractional/Ratio). So realToFrac will necessarily lose information. Now, given realToFrac, the sign of a real number, isNaN, and isInfinity, one *can* construct an algebraic representation which will be complete, but it will have to contain more information than can be coded in a Fractional object. What *problem* are you actually trying to solve here? If it is "conversion between floating point types", then there are other solutions that do not need to ``pollute'' exact arithmetic. I did not see any tickets on this -- did I miss it/them? This is one issue where I should go and contribute, as I've been part of a team that has done just this to a programming language before, so at least I can claim to know the pitfalls to avoid! Jacques ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Re[2]: overlapping instances and constraints
Tuesday, February 28, 2006, 1:54:25 PM, you wrote: CR> class NEq a b CR> instance Fail a => NEq a a CR> instance NEq a b i think that this definition just use ad-hoc overlapping instances resolution mechanism that we want to avoid :))) I don't want to avoid it completely, I want to give it more specifics to work with. but yes, type inequality would avoid many overlaps. the example was just meant to demonstrate the programmers could already specify their intention in current Haskell, by using Eq/NEq (in instance constraints), but it wouldn't be much use as long as current Haskell implementations ignore those intentions. Actually, it illustrates beautifully why ad-hoc overlapping doesn't work. There are two interpretations, the desired one, and one that just ignores the the first and uses the second for everything. I'm not sure what you're talking about? both hugs and ghc clearly specify that the more specific instance declaration is chosen when overlapping instance declarations are permitted. the repeated a makes the first declaration more specific, so both hugs and ghc accept the attached code, and deliver the same result, as specified. [if only that could be said for all programs, Haskell' could be built on much safer grounds, and everybody happier:-] overlapping resolution by choosing the most specific instance is no more black art than pattern-matching resolution by choosing the first match - some would say, less so. cheers, claus TypeNotEq.hs Description: Binary data ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: the MPTC Dilemma (please solve)
You addressed this to me -- but I'm an advocate for rather conservative
extensions whereas you are calling for extensions that go beyond what
any current implementation can do.
generally, that may be true,-) but in this specific case, I was just asking
for an effort to document the differences in current handling of extended
Haskell in hugs and ghc, by collecting test cases such as those I included.
whether or not the haskell' process manages to help eradicate those
differences is another matter, but collecting them seems a useful basis
for decisions, hence a task rather than a proposal. I addressed that to
you because (a) I was hoping this more moderate approach would be
down your alley and (b) because you have a stake in this at ghc hq,
and probably would want to collect the test cases for possible fixing.
I guess I will create the ticket myself, but if no committee member
or implementer has a stake in it, that won't do much good..
Anyway, there is already a ticket for overlapping instances, I think --
why don't you just add to that.
that might work. apart from the fact that I really, really hate the
braindead wiki markup processor, especially when editing through
that tiny ticket change field instead of loading up text. I went through
that experience once, when Isaac suggested the same for my labels
proposal - I don't want to have to do that again.
If you send me Wiki-marked-up text I'll gladly paste it in for you.
perhaps I'll just restrict myself to attaching my example code to
some ticket (are guests allowed to update attachments?). will see..
thanks,
claus
| -Original Message-
| From: Claus Reinke [mailto:[EMAIL PROTECTED]
| Sent: 25 February 2006 15:33
| To: Simon Peyton-Jones
| Cc: haskell-prime@haskell.org
| Subject: Re: the MPTC Dilemma (please solve)
|
| | Is the behaviour of GHC with -fallow-undecidable-instances (and
| | -fcontext-stack) well-understood and specifiable?
| >I would not say that it's well-specified, no.
|
| to start improving that situation, could we please have a task ticket
| for "document differences in unconstrained instance handling", then
| ask everyone to attach source examples showing such differences?
| [can guests attach code to task tickets?]
|
| the hope being, of course, that implementations nominally providing
| the same feature will eventually converge on providing the same
| interpretation of all programs using that feature.
|
| an example of the current oddities (at least they seem odd to me;):
| both hugs and ghc claim to resolve overlapping instances in favour
| of the most specific instance declaration. both claim that functional
| dependencies uniquely determine the range types from the domain
| types. but they do not agree on which programs to accept when
| we try to combine best-match with FDs.
|
| I've already given an example where ghc allows me to define
| record selection, while hugs complains that the overlap violates
| the FDs.
|
| I reported that as a hugs bug, because I think the best-match
| resolution of overlaps should ensure that the FD violation cannot
| happen, so the code should be valid. there are different ways to
| interpret FDs (something to check, or something to use), but it
| seemed that ghc was doing the right thing there. thread start:
|
| http://www.haskell.org//pipermail/hugs-bugs/2006-February/001560.html
|
| but after further experimentation, I'm not longer sure that ghc
| is doing the right thing for the right reasons. here is a tiny example
| of one of the disagreements:
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C a b | a -> b
| instance C a b
|
| so what is ghc doing there? is it going to guarantee that b will
| always be uniquely determined?
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C b | -> b where c :: b
| instance C b where c = error "b"
|
| safely m = m `CE.catch` print
| main = do
| safely $ print $ (c::Int)
| safely $ print $ (c::Bool)
| safely $ print [id,c]
|
| oh, apparently not. unless b is uniquely determined to be universally
| quantified, and the instantiations happen "after" instance selection.
|
| {- ghc ok
|hugs "Instance is more general than a dependency allows" -}
|
| class C b | -> b where c :: b
| instance C b where c = error "b"
|
| class D a where d :: a -> String
| instance C a => D a where d a = "a"
| instance C Int => D Int where d a = "Int"
|
| -- try at ghci prompt: (d 1,d (1::Int))
| -- gives: ("a","Int")
|
| so that parameter of C isn't all that unique. at least not long enough
| to influence instance selection in D.
|
| comments?
|
| cheers,
| claus
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Re[2]: overlapping instances and constraints
On 2/28/06, Claus Reinke <[EMAIL PROTECTED]> wrote: > I'm not sure what you're talking about? both hugs and ghc clearly > specify that the more specific instance declaration is chosen when > overlapping instance declarations are permitted. I have trouble with this "more specific" term. It's not well-defined, i.e. not a total order on possible instance declarations. The point I was trying to make was that in the case where a precondition (in this case, Fail a) does not apply, what stops the resolution algorithm falling back on the other instance declaration? -- Taral <[EMAIL PROTECTED]> "Computer science is no more about computers than astronomy is about telescopes." -- Edsger Dijkstra ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
relaxed instance rules spec (was: the MPTC Dilemma (please solve))
The specification is here:
http://www.haskell.org/ghc/dist/current/docs/users_guide/type-extensions.html#instance-decls
two questions/suggestions about this:
1. there are other termination criteria one migh think of, though
many will be out because they are not easy to specify. but here
is an annoyingly simple example that doesn't fit the current rules
even though it is clearly terminating (it's not even recursive):
class Fail all -- no instances!
class TypeNotEq a b
instance Fail a => TypeNotEq a a
instance TypeNotEq a b
class Test a b where test :: a -> b -> Bool
instance TypeNotEq a b => Test a b where test _ _ = False
instance Test a a where test _ _ = True
main = print $ (test True 'c', test True False)
never mind the overlap, the point here is that we redirect from
Test a b to TypeNotEq a b, and ghc informs us that the
"Constraint is no smaller than the instance head".
it is true that the parameters don't get smaller (same number,
same number of constructors, etc.), but they are passed to a
"smaller" predicate (in terms of call-graph reachability: there
are fewer predicates reachable from TypeNotEq than from
Test - in particular, Test is not reachable from TypeNotEq).
this is a non-local criterion, but a fairly simple one. and it seems
very strange to invoke "undecidable instances" for this example
(or is there anything undecidable about it?).
2. the coverage condition only refers to the instance head. this
excludes programs such as good old record selection (which
should terminate because it recurses over finite types, and is
confluent -in fact deterministic- because of best-fit overlap
resolution):
-- | field selection
infixl #?
class Select label val rec | label rec -> val where
(#?) :: rec -> label -> val
instance Select label val ((label,val),r) where
((_,val),_) #? label = val
instance Select label val r => Select label val (l,r) where
(_,r) #? label = r #? label
now, it is true that in the second instance declaration, "val" is
not covered in {label,(l,r)}. however, it is covered in the recursive
call, subject to the very same FD, if that recursive call complies
with the (recursive) coverage criterion. in fact, for this particular
task, that is the only place where it could be covered.
would it be terribly difficult to take such indirect coverage (via
the instance constraints) into account? there'd be no search
involved (the usual argument against looking at the constraints),
and it seems strange to exclude such straightforward "consume
a type" recursions, doesn't it?
cheers,
claus
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: Re[2]: overlapping instances and constraints
both hugs and ghc clearly specify that the more specific instance declaration is chosen when overlapping instance declarations are permitted. I have trouble with this "more specific" term. It's not well-defined, i.e. not a total order on possible instance declarations. The point I was trying to make was that in the case where a precondition (in this case, Fail a) does not apply, what stops the resolution algorithm falling back on the other instance declaration? preconditions (instance constraints) are not taken into account in best-fit overlap resolution. the ordering is plain substitution: instance A is more specific than instance B if there is a (non-empty) substitution that can be applied to make B's head identical to A's. where that is not possible, the overlapping declarations are not accepted. see, eg.: http://www.haskell.org/ghc/dist/current/docs/users_guide/type-extensions.html#instance-overlap in that sense, the flag name -fallow-overlapping-instances is slightly misleading, because it really only permits a subset of overlaps - ones that can be resolved unambiguously, using a substitution ordering of the instance heads. it is always clear which instance to choose - no search, no backtracking. cheers, claus ps people, including me, have argued the instance context ought to be taken into account. but again, that doesn't need to lead to much search - most of us would be happy if instance contexts would be required to uniquely determine the instance to be chosen, a rather conservative extension of current practice. that is because we often use a pair of instance declarations where the context for one includes the negation of some of the context in the other - they are mutually exclusive, so everything is happily deterministic, but the implementation does not notice.. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: [Haskell'-private] pragmas and annotations (RE: the record system)
Malcolm Wallace wrote:
* If the first three bytes of the file are "{-#", then keep reading in
ASCII/Latin-1/whatever until you discover an ENCODING decl (or not).
* If the first six bytes of the file are one of the two possible
UTF-16 representations of "{-#", then assume UTF-16 with that
byte-encoding until we find the ENCODING decl. (A missing decl in
this case would be an error.)
* If the first twelve bytes of the file are a UCS-4 representation of
"{-#" then ... you get the picture.
* For UTF-16 and UCS-4 variations, you must also permit the file to
begin with an optional byte-order mark (two or four bytes).
You'd also want to look for the UTF-8 BOM, which is very common in Windows.
As for literate source, I suppose you could forbid .lhs files from using
UTF-16 or UCS-32 unless there's a BOM. Then unlit wouldn't need to know the
encoding (I think), and the .hs heuristics would work on the output.
-- Ben
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: overlapping instances and constraints
Simon Peyton-Jones wrote: - A program that type checks can have its meaning changed by adding an instance declaration - Similarly adding "import M()" can change the meaning of a program (by changing which instances are visible - Haskell would need to be a lot more specific about exactly where context reduction takes place. I think all of these problems would go away if overlap was permitted within a module but forbidden across modules. Are there uses of overlapping instances for which this isn't flexible enough? -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: overlapping instances and constraints
Claus Reinke wrote: most of us would be happy if instance contexts would be required to uniquely determine the instance to be chosen, a rather conservative extension of current practice. How would that work? There's no way to prove that instance (Num a) => Foo a where ... instance Foo Char where ... don't overlap, because there's no way to know what instances of Num might be declared in other modules. If you reason based on what's in scope, you end up with the same problems that Simon detailed for overlapping instances. I can't think of any situation where the context could safely be used to resolve overlap except for a class private to the current module whose instances are locally constrained, but that doesn't seem like it would be very useful. -- Ben ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: instance Functor Set, was: Re: Export lists in modules
On 2/28/06, Johannes Waldmann <[EMAIL PROTECTED]> wrote:
> Malcolm Wallace wrote:
>
> > But if contexts-on-datatypes worked correctly,
> >
> > data Set a = Ord a =>
> >
> > then even the "real" map from Data.Set:
> >
> > map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
> >
> > could be an instance method of Functor.
>
> I'd love that. But I don't quite understand:
> do you think this is/should be possible with:
> current Haskell? Haskell-Prime? Current ghc (what extensions)?
as Oleg:
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
module Map where
import qualified Data.Set
class MyMap f a b where
myMap :: (a -> b) -> f a -> f b
instance (Functor f) => MyMap f a b where
myMap = fmap
instance (Ord a, Ord b) => MyMap Data.Set.Set a b where
myMap = Data.Set.map
Jim
___
Haskell-prime mailing list
Haskell-prime@haskell.org
http://haskell.org/mailman/listinfo/haskell-prime
Re: overlapping instances and constraints
On 2/28/06, Ben Rudiak-Gould <[EMAIL PROTECTED]> wrote: > Simon Peyton-Jones wrote: > > - A program that type checks can have its meaning changed by adding an > > instance declaration > > > > - Similarly adding "import M()" can change the meaning of a program (by > > changing which instances are visible > > > > - Haskell would need to be a lot more specific about exactly where > > context reduction takes place. > > I think all of these problems would go away if overlap was permitted within > a module but forbidden across modules. Are there uses of overlapping > instances for which this isn't flexible enough? Certainly! In HSP [1] there is a class (simplified here) class IsXML xml where toXML :: xml -> XML data XML = Element | CDATA String that deals with how things should be represented as XML. There are a number of basic instances for this, such as instance IsXML String where toXML = CDATA instance (Show a) => IsXML a where toXML = toXML . show The intention of the latter is to be a default instance unless another instance is specified. These instances can be found in the base HSP module, but the idea is that HSP users should be able to work with their own datatypes and only need to define the translation into XML via instanciating IsXML. This would have to be done in the user modules, so overlap across module boundaries are essential for this to work. :-) /Niklas [1] http://www.cs.chalmers.se/~d00nibro/hsp/ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: relaxed instance rules spec (was: the MPTC Dilemma (please solve))
On Tue, Feb 28, 2006 at 07:53:38PM -, Claus Reinke wrote: > class Fail all -- no instances! > > class TypeNotEq a b > instance Fail a => TypeNotEq a a > instance TypeNotEq a b > > class Test a b where test :: a -> b -> Bool > instance TypeNotEq a b => Test a b where test _ _ = False > instance Test a a where test _ _ = True > > main = print $ (test True 'c', test True False) > >never mind the overlap, the point here is that we redirect from >Test a b to TypeNotEq a b, and ghc informs us that the >"Constraint is no smaller than the instance head". > >it is true that the parameters don't get smaller (same number, >same number of constructors, etc.), but they are passed to a >"smaller" predicate (in terms of call-graph reachability: there >are fewer predicates reachable from TypeNotEq than from >Test - in particular, Test is not reachable from TypeNotEq). Yes, one could waive these restrictions on the constraint and head if they were not part of a cycle. Then when you added an instance that completed a cycle, the restrictions would come into force, on all the instances in the cycle. Non-local criteria are a bit more complex for the programmer, though (ignoring the implementor for the moment). I'll add the possibility to the wiki. >this is a non-local criterion, but a fairly simple one. and it seems >very strange to invoke "undecidable instances" for this example >(or is there anything undecidable about it?). Any termination criterion will be necessarily conservative, and will bite in some cases where termination is obvious to the human eye. The question is how far out to push the boundary, trading power for complexity. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: overlapping instances and constraints
Claus Reinke wrote: > most of us would be happy if instance contexts > would be required to uniquely determine the instance to be > chosen, a rather conservative extension of current practice. I'm not so sure about the "most of us", as you note yourself the defaulting pattern is quite popular (and useful). I certainly couldn't live without it. And even that aside, I'd much rather have the type system infer a "most particular" instance than to have to specify that myself. Also IMHO, adding a new construct (type (in)equality) to the language is a lot more obtrusive than to do something meaningful of the constructs that the language already provides. So I'd have issues with "conservative" as well... Of course, this is all from the perspective of a user, not a type inference engine implementor... ;-) /Niklas ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
