Re: the MPTC Dilemma (please solve)
On Thu, 23 Mar 2006, Claus Reinke wrote: class Graph (g e v) where src :: e - g e v - v tgt :: e - g e v - v we associate edge and node types with a graph type by making them parameters, and extract them by matching. If I understand correctly, this requires all graphs to be polymorphic in the types of edges and vertices. Thus, you cannot (easily) define a graph which provides, say, only boolean edges. Moreover, doesn't this require higher-order matching? I've already answered the last question. as for polymorphism, all this requires is for a graph type parameterized by an edge and vertex type (just as the SML solution, which got full marks in this category, requires instantiations of the edge and vertex types in the graph structure). Ah, I see. You are suggesting to introduce phantom type parameters to fake polymorphism for types which aren't really polymorphic. This might be acceptable as a temporary workaround but I don't think it is a good long-term solution. The ML implementation is not really comparable to this as instantiating structures is quite different from instantiating types. class Edge g e | g - e instance Edge (g e v) e class Vertex g v | g - v instance Vertex (g e v) v class (Edge g e,Vertex g v) = Graph g where src :: e - g - v tgt :: e - g - v (this assumes scoped type variables; also, current GHC, contrary to its documentation, does not permit entirely FD-determined variables in superclass contexts) This does not seem to be a real improvement to me and, in fact, seems quite counterintuitive. it is, however, probably as close as we can come within current Haskell, In what sense is this current Haskell? For this to work, you need at the very least to a) allow FD-determined variables to appear only in the superclass contexts but not in the head of class declarations (not supported by GHC at the moment), b) rely on scoped type variables (in a way which GHC doesn't support at the moment) and c) provide a way to keep FD outputs abstract even when the inputs are known (not supported by GHC). While a) and b) might be fairly minor changes to GHC, c) seems to be a major one. Even if all this is added, what you end up with is essentially a verbose and counterintuitive hack for something which should be easy to do. This is not meant as a criticism of your (very interesting, IMO) approach - I agree that this is probably the best you can do with FDs. It's just that FDs simply seem to be a less than optimal mechanism for this kind of programming. Also, it might be worth pointing out that even if all of the above worked, you still couldn't do data VertexPair g = VP (Vertex g) (Vertex g) fstVertex :: Graph g = VertexPair g - Vertex g fstVertex (VP v1 v2) = v1 type Vertices g = [Vertex g] Roman ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
seq as a class method
Hello, it seems that there is not yet a ticket about putting seq into a type class (again). In my opinion, having seq available for every type is a serious flaw. One problem is that the law f = \x - f x doesn't hold anymore since the equation is false for f = _|_. There was also a discussion on one of the mailing lists some time ago which revealed that the Monad instance for IO doesn't satisfy the monad laws because of the availability of seq for IO, I think. In addition, the automatic definition of seq for every type can make implementation details visible which were thought of as completely hidden. For example, it might make a difference whether one uses data or newtype for a one-alternative-one-field datatype, even if the data constructor is hidden. I therefore propose to declare a class like this: class Seq a where seq :: a - b - b (Perhaps the class name should be chosen better.) Generation of standard instances should be supported via deriving clauses or Template Haskell. For an algebraic datatype declared via data T a1 ... an = C1 t11 ... t1m1 | ... | Ck tk1 ... tkmk the implementation of seq should be something like this: seq (C1 _ ... _) = id seq _ = id What do others think? Best wishes, Wolfgang ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: the MPTC Dilemma (please solve)
On Thu, 23 Mar 2006, Claus Reinke wrote: Ah, I see. You are suggesting to introduce phantom type parameters to fake polymorphism for types which aren't really polymorphic. This might be acceptable as a temporary workaround but I don't think it is a good long-term solution. The ML implementation is not really comparable to this as instantiating structures is quite different from instantiating types. if we could actually write the instance implementations, it would be easier to say whether this is an adequate approach. once the phantom types are connected to the actual types used in the implementation, I suspect this would be very similar to the use of structure sharing and signature inclusion in the ML implementation. I would consider relying on any similarities between Haskell's data types and ML structures to be a bad thing, since the two are entirely different beasts. In particular, although the phantom types trick works to an extent, it is highly problematic from the software engineering point of view. Suppose I have a library which defines a monomorphic IntGraph type with specific vertex and edge types and does not know nor care about my Graph class. With your approach, I have to do something like data IntGraph' v e = IG IntGraph type MyIntGraph = IntGraph' Int (Int,Int) declare all the instances and provide an impedance matching module which provides all IntGraph operations (which I want to use in addition to the Graph operations) for MyIntGraph. With ATs, I just have to do instance Graph IntGraph where type Vertex IntGraph = Int type Edge IntGraph = (Int,Int) ML structures are equally easy to use. it is, however, probably as close as we can come within current Haskell, In what sense is this current Haskell? ignoring accidental limitations in current implementations. Are you sure that all these limitations really are accidential? thanks. I'm not saying that ATS are a bad thing, either, just that once we have a proper basis on which to rid current FD implemenations of accidental limitations, we should be able to implement ATS as a syntax transformation. Even if it is possible to push FDs far enough to be able to translate ATs into them, why would you want to do so in the context of Haskell's development (it is certainly an interesting theoretical question, though)? Having both mechanisms in one language doesn't seem to be a good idea to me and ATs seem to fit much better with the rest of Haskell and, consequently, are much easier to program with. Also, it might be worth pointing out that even if all of the above worked, you still couldn't do data VertexPair g = VP (Vertex g) (Vertex g) fstVertex :: Graph g = VertexPair g - Vertex g fstVertex (VP v1 v2) = v1 fstVertex :: Graph g = VertexPair g - Vertex g fstVertex (VP v1 v2) = v1 a variation of problem (a) above: contexts can introduce new, FD-bound variables only in type signatures at the moment, not in class or data declarations. data Vertex g v = VertexPair g v = VP v v fstVertex :: (Vertex g v, Graph g) = VertexPair g v - v fstVertex (VP v1 v2) = v1 otherwise, we could omit the spurious v parameter, as we'd like to. I presume you are suggesting data Vertex g v = VertexPair g = VP v v This would only affect the type of VP. Suppose we have rank :: (Vertex g v, Graph g) = g - v - Int Presumably, we could then write rankFst :: Graph g = g - VertexPair g - Int rankFst g (VP v1 v2) = rank g v1 How does rankFst get the dictionary for Vertex g v which it must pass to rank (in a dictionary-based translation, at least)? It can be extracted from the Graph dictionary, but how does the compiler know? Alternatively, we might try data VertexPair g = forall v . Vertex g v = VP v v but now fstVertex doesn't work anymore (for reasons which, IIRC, are not accidential). These problems disappear with ATs (I think) as here, only the Graph dictionary is required by all operations. Roman ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: Strict tuples
Am Mittwoch, 22. März 2006 14:19 schrieb Bulat Ziganshin: Hello Wolfgang, you said WHAT you think but not said WHY? my motivation is to be able to use myriads of already implemented algorithms on new datatypes I think, I already tried to explain why I think the way I think in an earlier mail: Strictness has to refer to attributes (the things you apply a data constructor to). In you approach, strictness is connected to type arguments. This causes problems. For example, if you have data T a = C a a, what would T !a mean? Would both attributes be strict? But how would you force only one attribute to be strict then? By the way, would it be okay for you to answer below the quotation, not above it? And would it be possible to use just a sign, followed by a space for marking quotations. My MUA gets confused by things like “WJ ”. Thank you very much. [...] Best wishes, Wolfgang ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
