February 2006 - Haskell-prime

the MPTC Dilemma (please solve)
by isaac jones 25 Mar '06

25 Mar '06

I've created a wiki page and a ticket to record solutions to what I'm calling the "Multi Parameter Type Class Dilemma". It's summarized thusly: MultiParamTypeClasses are very useful, but mostly in the context of FunctionalDependencies. They are particularly used in the monad transformer library found in fptools. The dilemma is that functional dependencies are "very, very tricky" (spj). AssociatedTypes are promising but unproven. Without a solution, Haskell' will be somewhat obsolete before it gets off the ground. I've proposed a few solutions. Please help to discover more solutions and/or put them on the ticket/wiki. Wiki page: http://hackage.haskell.org/trac/haskell-prime/ticket/90 Ticket: http://hackage.haskell.org/trac/haskell-prime/wiki/MultiParamTypeClassesDil… peace, isaac -- isaac jones <ijones(a)galois.com>

13 42

Restricted Data Types Now
by oleg＠pobox.com 22 Mar '06

22 Mar '06

It seems we can emulate the restricted data types in existing Haskell. The emulation is good enough to run the examples recently suggested on this list. So, we can start gaining experience with the feature. The emulation involves a slight generalization of the Monad class -- something that also addresses concerns by Amr Sabry http://www.haskell.org/pipermail/haskell/2005-January/015113.html that is, defining monad-like things with additional value constraints. The generalization of the Monad class seems to be backward compatible: > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module RestrictedMonad where > > import List > > class MN2 m a where > ret2 :: a -> m a > fail2 :: String -> m a > > class (MN2 m a, MN2 m b) => MN3 m a b where > bind2 :: m a -> (a -> m b) -> m b That is, we introduce two classes, and we spell out the types of values produced by monadic computations. The standard monad stuff seems to work, at least in the tried cases. For example, we can define Maybe monad in the traditional way > instance MN2 Maybe a where > ret2 = Just > fail2 _ = Nothing > > instance MN3 Maybe a b where > bind2 (Just x) f = f x > bind2 Nothing _ = Nothing and can write the regular code > test3f () = bind2 (ret2 "a") (\x -> ret2 $ "b" ++ x) > test3f' () = bind2 (fail2 "") (\x -> ret2 $ "b" ++ x) whose inferred type is *RestrictedMonad> :t test3f test3f :: (MN3 m [Char] [Char]) => () -> m [Char] which is quite reasonable. We can instantiate that to the Maybe monad: > test3:: Maybe String = test3f () *RestrictedMonad> test3 Just "ba" Let us now run the example suggested by John Meacham > data Eq a => Set a = Set [a] deriving Show > unSet (Set x) = x > > singleton :: Eq a => a -> Set a > singleton x = Set [x] BTW, the Eq constraint in singleton's signature is forced upon us. If we give the signature, we must mention the constraint. OTH, we can omit the signature and it will be inferred. > instance Eq a => MN2 Set a where > ret2 = singleton > > instance (Eq a,Eq b) => MN3 Set a b where > bind2 (Set x) f = Set (nub . concatMap (unSet . f) $ x) Again, we cannot forget the Eq constraints, because the typechecker will complain (and tell us exactly what we have forgotten). Now we can instantiate the previously written test3f function for this Set monad: > test4 :: Set String = test3f () *RestrictedMonad> test4 Set ["ba"] The latter code shows that the Eq constraint (required by nub) is indeed being provided by the `monad', although the test3f function had _no_ Eq constraints. > test5 = case test3f () of Set x -> nub x Here's another similar example. Again, test6 per se has no Eq constraints (and it is polymorphic over the value a) > test6 x = bind2 (ret2 x) (\x -> ret2 x) > test7 = case test6 True of Set x -> nub x > test7' = case test6 True of Just x -> x *RestrictedMonad> :t test6 test6 :: (MN3 m a a) => a -> m a Here's Ashley Yakeley's recent example: > class HasInt a where > getInt :: a -> Int > instance HasInt Int where > getInt = id > instance HasInt Bool where > getInt = const 1 > > data HasInt a => T a = T Int a deriving Show > > -- forced constraint > instance HasInt a => MN2 T a where > ret2 a = T (getInt a) a > > instance (HasInt a, HasInt b) => MN3 T a b where -- forced constraints > bind2 (T i1 i2) f = let (T _ b) = f i2 in T i1 b > > foo () = bind2 (ret2 True) (const (ret2 3)) > > fooT :: T Int > fooT = foo ()

2 2

RE: overlapping instances and constraints
by Simon Peyton-Jones 11 Mar '06

11 Mar '06

Overlapping instances are undoubtedly useful, but they raise lots of interesting questions. Such as - 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. Consider f xs x = xs == [x] Do we infer the type (Eq a) => [a] -> a -> Bool? Thereby committing to a particular choice of instance? Or do we (as GHC does) infer the type (Eq [a]) => [a] -> a -> Bool, so that if f is applied at (say) type Char, then an instance Eq [Char] instance would apply. GHC is careful to do the latter. - When exactly is overlap permitted? Is this ok? instance C a Int instance C Bool b Previously GHC rejected this, on the grounds that it could be ambiguous when you came across (C Bool Int). But not GHC accepts it, on the grounds that (C Bool Char) is quite unambiguous. [Actually this last point is relevant for MPTCs even if overlap isn't allowed.] Concerning using the instance context, yes, it's attractive, but it involves *search* which the current mechanism does not. Presumably you have in mind that the type system should "commit" only when there is only one remaining instance declaration that can fit. You need to be very careful not to prune off search branches prematurely, because in a traditional HM type checker you don't know what all the type are completely. And you need to take functional dependencies into account during the search (but not irrevocably). I have not implemented this in GHC. I don't know anyone who has. I don't even know anyone who has specified it. All good stuff to debate. I'd be happy to see the traffic on MPTCs reach half the level that syntax debates do! In general, I think that type-system proposals are much easier to evaluate when accompanied with formal type rules. It's not just a macho thing -- it really helps in debugging the dark corners. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Claus Reinke | Sent: 26 February 2006 16:28 | To: haskell-prime(a)haskell.org | Subject: overlapping instances and constraints | | | the point about overlapping instances is that they shouldn't, | so we are looking for ways to resolve what looks like overlaps | unambiguously, so that there are no overlapping instances left. | | we don't want overlapping instances in the language definition, | but we do want more expressive means of defining non- | overlapping instances. | | 1. resolving overlaps in favour of the most specific declaration | does so, so why is that approach slated as "adopt: probably no"? | | http://hackage.haskell.org/trac/haskell-prime/ticket/54 | | 2. FDs can help to make types in instance declarations more | specific, thus avoiding some overlaps or at least helping the | "best-match" to resolve overlaps. defaults resolve some of | the simplest overlaps (which instance of Num did you mean?), | but not others, because their overloading is not expressed in | terms of classes (which empty list did you mean?). | | 3. in this context, could someone please remind me what exactly | is the reason that class constraints in instance declarations are | ignored when deciding whether two instances overlap? | | we have two worlds to consider, the unconstrained world of | semi-decidable type class programming, and the restricted | world which guarantees termination of type class inference. | | in the first world, it seems there is no reason not to look at | the constraints, because there are no termination guarantees | anyway. and in the second world, it seems there is no reason | not to look at the constraints, because we know that doing | so will terminate nicely, thank you. | | so why are some instance declarations still rejected as | overlapping even if their constraints clearly say they don't? | | cheers, | claus | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

9 20

Re: Export lists in modules
by Ketil Malde 03 Mar '06

03 Mar '06

Wolfgang Jeltsch <wolfgang(a)jeltsch.net> writes: >> Personally, I would greatly prefer to have libraries that do not clash >> with common Prelude functions. > I would solve this problem by reducing the Prelude to just a core. List > function could go, for example, (mostly) into Data.List. If this means that you must import Data.List almost everywhere, this won't change anything - only add yet another import to every file. I know most - if not all - of my modules use lists, but just in case, I checked with the darcs sources - 95 of 107 source files appear to use lists. Ignoring the : and ++ operators (looking for null, map, and filter) the count is 76 files. >> If you always have to qualify it, what's the advantage of >> Data.Set.empty over emptySet again? At least with 'emptySet' I know >> what to grep for. > I would import Data.Set as Set. So I would use Set.empty instead of > emptySet. The problem is that I might import Data.Set as S. Joe would import it as something else, and Frank would use yet another prefix. > The advantage is that Set.empty is more structured. I'm not sure why that is such an advantage. To me, structure sounds like a means rather than an end. If it made things simpler, I'd be all for it, but IMO it doesn't - and it makes some things more difficult. > You can easily distinguish the kind of operation (empty) and the > type you are working with (Set). Only by convention - i.e. I must manually rename the module in a way that is meaningful with respect to the type. (As an aside, 'empty' is a rather poor example, as it is not a Prelude function. Take 'null' or 'map' or - why not - '(:)' instead) Don't get me wrong, I don't want to go back to the old ways of prefixing *every* identifier with a module abbreviation. But I resent having to add a multi-line half-standardized set of imports to over 90% of my source files. In short, I'm fairly comfortable with the scope of the Prelude¹ and I don't mind modules like e.g. Data.Map and Data.Set, which are similar in many ways to recycle some of their identifiers. However, I think minimizing the number of name clashes should be a goal, and modules that are intended to be used together, should try to avoid using the same identifiers. And this implies that Prelude identifiers should *not* be recycled, unless you intend to replace the Prelude. -k ¹ I might want to shove some of the association list stuff into Data.List, but certainly not all list functionality. -- If I haven't seen further, it is by standing in the footprints of giants

12 29

RE: the MPTC Dilemma (please solve)
by Simon Peyton-Jones 02 Mar '06

02 Mar '06

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:claus.reinke@talk21.com] | Sent: 25 February 2006 15:33 | To: Simon Peyton-Jones | Cc: haskell-prime(a)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

3 2

RE: Export lists in modules
by Simon Peyton-Jones 01 Mar '06

01 Mar '06

These days, hs-boot files are pretty close to source files, with masses of stuff omitted. However, you must process the import declarations of the hs-boot file to figure out the name spaces involved. In the original source file, you can't process the import declarations because those modules have not been compiled yet. It's not clear which ones to omit. Similarly in the body of the source file, there are lots of references to things in imported modules, but those imported modules have not been compiled yet. You could imagine a) compiling recursive groups "all at once" b) somehow magically filtering the source file to omit anything undefined, leaving only defined stuff..... which ought to be enough to tie the knot. But GHC currently requires the programmer to perform (b) manually. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ben Rudiak-Gould | Sent: 23 February 2006 21:26 | To: haskell-prime(a)haskell.org | Subject: Re: Export lists in modules | | Malcolm Wallace wrote: | > An explicit interface would be useful for many purposes besides | > machine-checked documentation. For instance, it could be used to | > eliminate the hs-boot or hi-boot files used by some compilers when | > dealing with recursive modules. | | Why *does* ghc require hs-boot files? What can be gleaned from an hs-boot | file that couldn't be expressed in the corresponding hs file? For example, | why doesn't ghc simply require that at least one module in a recursive group | contain an explicit export list mentioning only explicitly typed symbols? | | -- Ben | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

4 3

RE: the MPTC Dilemma (please solve)
by Simon Peyton-Jones 28 Feb '06

28 Feb '06

With help from Martin Sulzmann and Ross Paterson, GHC (HEAD) now implements a richer form of functional dependencies than Mark Jones's version, but still decidable etc. The rules for what must appear in the context of an instance declaration are also relaxed. The specification is here: http://www.haskell.org/ghc/dist/current/docs/users_guide/type-extensions .html#instance-decls I think this is a step forward, and a serious candidate for Haskell'. I think that if you stick to these rules, everything is nailed down as Martin so rightly says it should be. And I am not sure we can go much further. Of course -fallow-undecidable-instances still lifts all restrictions, and then all bets are off. Many thanks to Ross and Martin. You can try it out by downloading a GHC snapshot (or by building from source). Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | isaac jones | Sent: 11 February 2006 01:29 | To: haskell-prime(a)haskell.org | Subject: the MPTC Dilemma (please solve) | | I've created a wiki page and a ticket to record solutions to what I'm | calling the "Multi Parameter Type Class Dilemma". It's summarized | thusly: | | MultiParamTypeClasses are very useful, but mostly in the context of | FunctionalDependencies. They are particularly used in the monad | transformer library found in fptools. The dilemma is that functional | dependencies are "very, very tricky" (spj). AssociatedTypes are | promising but unproven. Without a solution, Haskell' will be somewhat | obsolete before it gets off the ground. | | I've proposed a few solutions. Please help to discover more solutions | and/or put them on the ticket/wiki. | | Wiki page: | http://hackage.haskell.org/trac/haskell-prime/ticket/90 | | Ticket: | http://hackage.haskell.org/trac/haskell-prime/wiki/MultiParamTypeClasses Dilemma | | | peace, | | isaac | | | | -- | isaac jones <ijones(a)galois.com> | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

4 3

Re: [Haskell'-private] pragmas and annotations (RE: the record system)
by Malcolm Wallace 28 Feb '06

28 Feb '06

"Simon Marlow" <simonmar(a)microsoft.com> 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

3 2

realToFrac issues
by John Meacham 28 Feb '06

28 Feb '06

I am not sure if this has been brought up for haskell-prime or not, but a while ago someone noticed that 'realToFrac' as specified in the report can't propagate NaN or infinity values properly since it goes through a Rational intermediate stage. this has the odd effect in ghc of making such conversions only work when optimization is used so the RULES turning Float<->Double conversion into their C counterparts fire. The proposed solution was to add NaN, +Infinity, and -Infinity to rational with the representations 0 :% 0, 1 :% 0, and -1 :% 0 respectively. Seems straightforward, (and generally useful) but we should make sure not to forget it for haskell-prime. John -- John Meacham - ⑆repetae.net⑆john⑈

5 7

RE: Export lists in modules
by Simon Marlow 28 Feb '06

28 Feb '06

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

1 0