March 2003 - Haskell - Haskell.org

RE: fundeps for extended Monad definition
by Simon Peyton-Jones 05 Mar '03

05 Mar '03

Interesting example | class Monad2 m a ma | m a -> ma, ma -> m a where | return2 :: a -> ma | bind2 :: Monad2 m b mb => ma -> (a -> mb) -> mb | _unused :: m a -> () | _unused = \_ -> () | instance Monad2 [] a [a] where | bind2 = error "urk" The functional dependencies say m a -> ma Instantiating this with the instance declaration instance Monad2 [] a [a] we can deduce that given any constraint (Monad2 t1 t2 t3), if t1 = [], then t3 must be [t2] In the instance declaration, we instantiate the type of bind2 to get the type of bind2 needed for this particular instance declaration: bind2 :: forall b mb. Monad2 [] b mb => ma -> (a -> mb) -> mb Now the rule above says "that means mb must be [b]" and that gives rise to the error. GHC is consistent about this --- if you don't supply an defn for bind2, it makes one up, and complains in more or less the same way. Here's a less complicated variant of the same problem: class C a b | a -> b where {} instance C Int Int where {} f :: (C Int b) => Int -> b f x = x Is the defn of f legal? Both GHC and Hugs reject it because the inferred type of f is more like C Int Int => Int -> Int Functional dependencies tell us that 'b' must be Int, so in fact the two types are equivalent. In this example the programmer could write the 'correct' type, but in your case you can't because the type signature arises by instantiating the one in the class declaration. I'm really not sure what to do about this. GHC has an excellent way of keeping me honest in type-checking: the type checker has to produce a translation of the program into the (typed) core language. What could f's translation look like. It must presumably be f (d::C Int Int) (x::Int) = x giving f the type f :: C Int Int -> Int -> Int Another translation could be f b (d::C Int b) (x::Int) = x (the 'b' is a type variable, a big-lambda binding) giving f the type f :: forall b. C Int b -> Int -> Int But what I *cannot* get is the type f : forall b. C Int b -> Int -> b how could I write the term? f b (d:: C Int b) (x::Int) = ????? I suppose I could use (unsafeCoerce x) as the RHS, which amounts to saying "in every call to f, b will be Int, so we know that the coercion is safe". But that is a scarily global property. For example, if a call site of f does not "see" the instance declaration, it might call f with an argument of type (C Int Bool) or something. Nor can I see an easy way to insert the 'right' coercions in general. Bottom line: excellent point, but I can't see how to fix it. Maybe there are some fundep experts out there who can guide us through the swamp? Simon

3 3

RE: First-class types
by Simon Peyton-Jones 05 Mar '03

05 Mar '03

| 1) Coerce a a can be defined as coerce=id for all a. However, this | may of course lead to overlap in the type structure, so we must | write a separate instance definition for Coerce Int Int, Coerce | Double Double, etc. if we want types to be decidable. I'd love for | some clever person to solve this little difficulty. Indeed so. And instance Coerce a a where coerce = id does not overlap with instance Coerce Int Bool where ... instance Coerce Bool Int where ... There's no overlap here. (Overlap = there is a Coerce t1 t2, which matches more than one instance decl.) Furthermore, it works fine; I just tried it. | 2) When we define D a b c, we know that D b a c is also allowed. | Again, decidability prevents us from asserting this directly. | Again, a clever solution could save us a lot of code and even more | debugging. I suspect this may be a marginally easier nut to crack | than the previous one. Much harder, I think. Commutativity is always tricky! Simon

1 0

compiling
by Mike T. Machenry 05 Mar '03

05 Mar '03

I am having a problem compiling my code. Usually I run it with ghci -package data -fglashow-exts Main.hs Main declares a main function and imports all my other files. when I try to ghc it to compile I get that it can't find an interface file for each file in my project. How do I compile something? Also it can't find an interface for Data. How do I make an interface file for that? Thanks, -mike

2 1

Persistant (as in on disk) data
by Iavor S. Diatchki 04 Mar '03

04 Mar '03

hello, a recent post reminded me of a feature i'd like. for all i know it is already implemenetd in GHC so pointers are welcome. i'd like to be able to dump data structures to disk, and later load them. currently i do that with Show/Read but it is very slow and it seems as a kind of "ovarloaded" use fo Show. and it doesn't work with circular structures. so i'm thinking something like "deriving Persistant". for functions perhaps the easiest thing is to leave it to the user to create the instances. perhaps: class Persistant t where save :: t -> String -> IO () load :: String -> IO t here the String is the name of the file where to store/load the data. so is there such a thing already, and if not would it be difficult to add to say GHC? bye iavor -- ================================================== | Iavor S. Diatchki, Ph.D. student | | Department of Computer Science and Engineering | | School of OGI at OHSU | | http://www.cse.ogi.edu/~diatchki | ==================================================

1 0

big lambda in class declarations
by Hal Daume III 04 Mar '03

04 Mar '03

So the word on the street is that allowing big lambda makes type inference undecidable. This makes sense to me since allowing big lambda essentially allows you to program at the type level and thus of course you'll get undecidability. However, I'm having difficulty understanding where the undecidability sneaks in if you allow big lambda in class declarations. I suppose the cannonical example is when you want to write something like: > class Set s where { ... } > instance Set (/\ a. FiniteMap a ()) where { ... } but now you have to write: > data FMSet a = FMSet (FiniteMap a ()) > instance Set FMSet where { ... } The big lambda is of course equivalent to not applying type synonyms completely, somethign like: > type FM a = FiniteMap a () > instance Set FM where { ... } will of course also be rejected (since this would give us a way to do big lambda). Could some one help my intuition a bit here and explain to me how you could use big lambdas in class declarations to write programs? Thanks! - Hal -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume

1 0

RE: First-class types
by Simon Peyton-Jones 04 Mar '03

04 Mar '03

| The following is a more flexible alternative to overloading. We | essentially define a function on types and invoke it, seemingly at run | time. No Dynamics or unsafe computations are employed. We only need | existential types, multi-parameter classes and functional | dependencies. The code also shows how to manipulate values which | cannot be manipulated. Ingenious, but unnecessarily complicated. You don't need existential types at all. (See the code below, which is considerably simpler and, I fancy, a bit more efficient.) Also, I'm not sure why you make 'Type' (which is pretty much the Typable class in the Dynamic library) into a superclass of D; it's not used. The idea of using a value (which is never evaluated) as a proxy for a type is exactly what the Typable class does. Indeed, it is a really useful technique. The clever things about your solution are a) You avoid the nasty ambiguity trap that many such schemes fall into e.g. when you see (a + b) * (c-d), what is type are the intermediate values (a+b) and (c-d). You drive the type of the result from the type of the arguments, which makes sense. (Albeit, if you you want to add two Floats and get an Int, you'll have to do a conversion at the end.) b) You separate the coercion stuff from the operations in a nice way. Simon class D a1 a2 b | a1 a2-> b where typeof :: a1 -> a2 -> b instance D Bool Bool Int instance D Int Bool Int instance D Bool Int Int instance D Int Int Int instance D () Int Int instance D Int () Int instance D () () Int instance D Int Float Float instance D () Float Float instance D Float Int Float instance D Float Float Float -- The coercion function class Coerce a b where coerce :: a -> b -> b instance Coerce () Int where coerce _ _ = 0 instance Coerce () Float where coerce _ _ = 0 instance Coerce Int Int where coerce = const instance Coerce Float Float where coerce = const instance Coerce Int Float where coerce x _ = fromInteger $ toInteger x instance Coerce Bool Int where coerce True _ = 1 coerce False _ = 0 add x y = let general_type = typeof x y x' = coerce x general_type y' = coerce y general_type in x' + y'

2 1

RE: Persistent data
by Simon Peyton-Jones 04 Mar '03

04 Mar '03

GHC has a multi-generational garbage collector. If you have enough physical memory on your machine so that the GC isn't thrashing trying to find the 100 free bytes that remain, then you should find the database migrates to the oldest generation and stays there. If you use +RTS -Sstderr you'll see info about when GC happens, and which generation. There should be lots of young-gen collections for each old-gen one. You can increase the number of generations with a command-line flag to the runtime system (see the user manual). Simon | -----Original Message----- | From: Sengan.Baring-Gould(a)nsc.com [mailto:Sengan.Baring-Gould@nsc.com] | Sent: 03 March 2003 18:38 | To: haskell(a)haskell.org | Subject: Persistent data | | Is there some way to reduce the cost of garbage collection over large persistent | datastructures without resorting to escaping to C to malloc memory outside the | heap? | | The program I'm working is part database, which cannot discard information. | The net result is that I see figures like 82.9% of the time taken by garbage | collection. The heap profile looks like a charging capacitor: a linear increase | (as expected) which is slowly dilated as time increases by the garbage collector | thrashing memory. | | When I worked on the LOLITA natural language processor we solved the problem | by moving a lot of the data out to C++, so that the heap only contains things | soon to be freed. I know generational garbage collection is supposed to help, | but it doesn't seem to. Is there a pure Haskell solution to this problem? | | Sengan | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

RE: fundeps for extended Monad definition
by Simon Peyton-Jones 04 Mar '03

04 Mar '03

| I believe something along the lines of the following would work: | | > class C a b | a -> b where { foo :: b -> String } | > instance C Int Int where { foo x = show (x+1) } | > x :: forall b. C Int b => b | > x = 5 | | (Supposing that the above definition were valid; i.e., we didn't get the | type signature error, this reads that x has type "b" for all types | "b" such that C Int b -- the fact that there is only one such type (due to | the fun dep) is for us to know.) | | Then, we should be able to say: | | > foo x | | and get "6". I understand that is what you would like, but I do not know how to achieve it in a reasonable way. (By "reasonable" I mean both in terms of a reasonably simple type inference algorithm, and in terms of a reasonable translation into a typed intermediate language. The latter is, in a sense, just an implementation matter, but I have found it to be an excellent sanity check.) Simon |

1 0

Re: Tutorial for literate Haskell
by b.i.mills＠massey.ac.nz 03 Mar '03

03 Mar '03

Hi, Since I sent this to the haskell list in the first place, I'd better let everyone know that it all worked out. > Hmm, there were no problems in simply doing so. Ok, I've cut your example down a bit (just from a minimalist tendency). The complete modified code is ... \documentclass{report} \usepackage{verbatim} % vital \begin{document} \newenvironment{code}{\footnotesize\verbatim}{\endverbatim\normalsize} HaskellModule.lhs: Maybe some text... We call our module Foo, because this name is very meaningful. \begin{code} module Foo where \end{code} \end{document} Works just fine and seems robust. My original problem ... an over-developed tendency to go it alone? I was not using package verbatim, which does help, doesn't it. > I hope this will help. Yup, thanks. Bruce.

1 0

First-class types
by oleg＠pobox.com 03 Mar '03

03 Mar '03

The following is a more flexible alternative to overloading. We essentially define a function on types and invoke it, seemingly at run time. No Dynamics or unsafe computations are employed. We only need existential types, multi-parameter classes and functional dependencies. The code also shows how to manipulate values which cannot be manipulated. As an example, we define a _function_ (not a method!) 'add' such that: Main> add True False 1 Main> add () (5::Int) 5 Main> add () (5::Float) 5.0 Main> add (4::Int) True 5 Main> add (10::Int) (5::Float) 15.0 The example works both in GHC and Hugs. The signature of add is quite revealing: forall b a2 a1. (Num b, Coerce a2 b, Coerce a1 b, D a1 a2 b) => a1 -> a2 -> b That is, 'add' is capable of adding any two _things_, provided they both can be "generalized" and "coerced" into a number. The "type function" D computes the generalization of two types -- in a manner we specify. The function add is actually quite simple: > add x y = let general_type = typeof x y > x' = coerce x general_type > y' = coerce y general_type > in x' + y' The function 'typeof' is also interesting. It has a type forall b a2 a1. (D a1 a2 b) => a1 -> a2 -> b Note that it returns 'b' forall b! In a sense, the function performs a type computation at run time. The code follows. We should note that we could have achieved the same effect by defining an appropriate class with the method 'add'. In our solution however, the acts of generalizing, coercion, and addition are all separated. If we later decide to subtract things rather than add them, we do not need to alter the class and all the instances. We merely need to introduce the subtraction function. This makes the maintenance of the code easier. The distinct characteristic of the following code is an indirect manipulation of an untouchable, existential value. We were able to force a value to be of a specific type without any means of accessing the value directly. > class Type a where > name :: a -> String > instance Type Bool where > name a = "Bool" > instance Type Int where > name a = "Int" > --instance Type Char where > -- name a = "Char" > instance Type () where > name a = "()" > instance Type Float where > name a = "Float" > -- Type generalization function: type -> type -> type > class (Type b) => D a1 a2 b | a1 a2-> b > instance D Bool Bool Int > instance D Int Bool Int > instance D Bool Int Int > instance D Int Int Int > instance D () Int Int > instance D Int () Int > instance D () () Int > instance D Int Float Float > instance D () Float Float > instance D Float Int Float > instance D Float Float Float > -- The coercion function > class Coerce a b where > coerce :: a -> b -> b > instance Coerce () Int where > coerce _ _ = 0 > instance Coerce () Float where > coerce _ _ = 0 > instance Coerce Int Int where > coerce = const > instance Coerce Float Float where > coerce = const > instance Coerce Int Float where > coerce x _ = fromInteger $ toInteger x > instance Coerce Bool Int where > coerce True _ = 1 > coerce False _ = 0 > newtype M a1 a2 = M (forall b.(D a1 a2 b) => b) > data M1 a1 a2 = M1 a1 a2 (M a1 a2) > typeof v1 v2 = case (M1 v1 v2 (M undefined)) of M1 _ _ (M y) -> y > typeof1 v1 v2 = case (M1 v1 v2 (M undefined)) of M1 _ _ y -> y > add x y = let general_type = typeof x y > x' = coerce x general_type > y' = coerce y general_type > in x' + y'

1 0