June 2005 - Haskell-Cafe

Re: [Haskell-cafe] Why distinct tyvars in instance declarations?
by Frank-Andre Riess 27 Jun '05

27 Jun '05

Hi there, > but GHC complains: > > Illegal instance declaration for `Foo (Either b b)' > > (The instance type must be of form (T a b c) > > where T is not a synonym, and a,b,c are distinct type variables) > > In the instance declaration for `Foo (Either b b)' unless I'm totally mistaken, your problem isn't the distinction thingy, but rather an error like supplying an Int for where you need (Int -> Int -> Int). That is, you're trying make (Either String String) an instance of Foo, (Either String String) already being a fully constructed type; Foo, on the other hand, seems to require a type constructor that is yet to parameterize over three more types (e.g. StateT). Greets, Frank-Andre Riess

3 2

Re: [Haskell-cafe] Noob error: Type b -> c b Does not match IO a
by kynn＠panix.com 27 Jun '05

27 Jun '05

Some simplifications might help you here... > prodList [] = 1 > prodList (0:xs) = 0 > prodList (x:xs) = x * prodList xs Simplified: prodList xs = foldl (*) 1 xs But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong? (I realize that, given that the function product is already available, there is no point in defining my function prodList above, but my question is a more general one, having to do with how best to implement short-circuiting.) Thanks! kj

6 8

type inference and named fields
by Malcolm Wallace 27 Jun '05

27 Jun '05

I have discovered something I believe to be a problem in Haskell'98, although it is not a simple bug as such - it has more of the flavour of an unintended mismatch in the interaction of two separate features. Since Haskell is deeply principled language, a feature conflict is extremely rare, and so worthy of note. So here it is: Some attempts to use named field updates are prohibited by type inference, even though the code is perfectly type safe. Here is an example. > module Fieldbug where > data Fields a = > VariantWithTwo { field1 :: a > , field2 :: a } > | VariantWithOne { field1 :: a } The key point here is that the data structure with named fields has more than one constructor, and some fields are omitted in one of the variants. Now let's try to write a simple conversion function over values of this type, using only the named-field update style: > data Void = Void > > voidcast :: Fields a -> Fields Void > voidcast v@(VariantWithTwo{}) = v { field1 = Void , field2 = Void } > voidcast v@(VariantWithOne{}) = v { field1 = Void } It looks simple enough doesn't it? But none of the widely available Haskell implementations will accept this code. Hugs: ERROR "Fieldbug.hs":11 - Inferred type is not general enough *** Expression : voidcast *** Expected type : Fields a -> Fields Void *** Inferred type : Fields Void -> Fields Void ghc: Fieldbug.hs:11:32: Couldn't match the rigid variable `a' against `Void' `a' is bound by the type signature for `voidcast' Expected type: Fields Void Inferred type: Fields a In the record update: v {field1 = Void} In the definition of `voidcast': voidcast (v@(VariantWithOne {})) = v {field1 = Void} nhc98: ====== Errors after type inference/checking: Derived type for Fieldbug.voidcast at 10:1-11:42 does not match due to: given free variable a is bound to Void Derived:((Fields Void) -> (Fields Void)) Given :((Fields a) -> (Fields Void)) As far as I can tell, the problem is that in the final line, the expression v { field1 = Void } is interpreted by the type inference algorithm as if the variable v could contain either constructor VariantWithOne or VariantWithTwo. Obviously in the latter case the expression would indeed be incomplete because it casts only one of the fields, not both. But we know that can never be the case! By pattern-matching, this particular v /must/ be the former constructor. Unfortunately we cannot pass that knowledge into the type inference algorithm. It turns out that it is in fact /impossible/ to write this conversion function using only named field updates. It can only be written by using an explicit constructor on the rhs, which thus forces you to initialise all its fields explicitly. This negates any value from using named fields in the first place. Regards, Malcolm

10 32

RE: [Haskell-cafe] Re: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

> Off-hand, I recall a paper by Martin Odersky and the Scala people > discussing their approach to the Expression Problem, So ... http://icwww.epfl.ch/publications/documents/IC_TECH_REPORT_200433.pdf ... I guess The key innovative idea there is composition of mixins while replacing formal superclasses of mixins by the actual base class for mixin composition. I quote: "In a mixin composition A with B with C, class A acts as actual superclass of mixins B and C, replacing the declared superclasses of B and C. To maintain type soundness, A must be a subclass of the declared superclasses of B and C. A super reference in either B or C will refer to a member of class A. As is the case for trait composition, Scala's mixin composition is commutative in the mixins - A with B with C is equivalent to A with C with B." In OOHaskell, you would parameterize in the superclass and that's it. DISCLAIMER: we haven't tried this. Thanks for the inspiration. > and a related paper by Jacques Garrigue, > where he proposes to solve it using OCaml's polymorphic variants. I am not sure. Is this referring to "Objective Label"? Which paper exactly? > Hope this helps, It's interesting but I don't see how we make progress with the original (by now perhaps trivial) question regarding the transportation of an OO design into Haskell. The shapes problem doesn't call for Odersky's new contribution: I quote: "We add to this list the following criterion: * Independent extensibility: It should be possible to combine independently developed extensions so that they can be used jointly [21]." The shapes problem rather calls for silly subtyping polymorphism. So we are beating a dead horse (or a red herring) by detouring to Scala unless I don't get you were hinting at. BTW, I just notice that Oderksy's list of partial solutions isn't complete: - Visitor combinators (Joost Visser) complementing Palsberg et al. - Many forms of generic functional programming (Hinze etc.) - Haskell type classes allow for extension in both type and processor extension. It's getting late here. Ralf

2 1

RE: [Haskell-cafe] Re: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

Bulat wrote: > if you require several operations, you can pack them in tuple or > structure (really, tuple is a structure without field names) How are we going to anticipate all possible bodies of a for-loop? By comparison, when we build a normal Haskell list, does the construction precisely mirror what we are going to *do* with each element? Fold the map then!!! > if you need fields/interfaces inheritance, then this method will not > work. but in 90% of cases it's enough. What to do for the other 10%? > in C++, creating classes is the > most useful method of structuring program, so it is used for any > problem - from very simple to most complex. when you translate such > thing to Haskell, it's better to see which concrete problem are solved > with help of classes, and not to emulate the classes itself (because > in this case you will write many unneeded code) Yes, but we ought to solve the shapes problem. The shapes example is in Bulat's 10% region. > only because it's C-like :) you just can't believe that Haskell > program can be 3-10 times smaller while keeping the same functionality > :))) But note that "same functionality" is one thing, having "separate compilation" and "program extensibility" too is another one. Ralf

2 1

RE: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

Andreas Rossberg said: > [Followups to Haskell Cafe] > as far as I read it, "dynamic" or "late binding" is orthogonal to > subtyping, or typing in general. It is just that most typed OO languages > lump these concepts together. Absolutely agreed. > Often a simple first-class function, or a record thereof, > is enough (in fact, "dynamic binding" is just the OOO way > of saying "calling a first-class function"). In typical > functional programming style, you need the general > thing only rarely. Can you just tell how *you* would favor encoding the shapes example that was posed by poster? (It might just be that your code would be very close to Lennart's proposal?) Thanks, Ralf

2 1

RE: [Haskell-cafe] RE: Re[4]: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

I guess we just need to agree that we disagree. Of course, you are right that I am just a newbie when it comes to Haskell. How did you know that I am actually a Cobol programmer? Did you google? http://www.google.com/search?biw=1003&hl=en&q=Ralf+Cobol Seriously (?): 1. I never intended to impose any particular OO style on Haskeller's. Its more about the *intellectual* question whether we can take C++/C#/Java code and do a structure-preserving conversion to Haskell without starting to argue on paradigm conversion. Or as Alistair Bayley argues (Alistair, thanks for helping out!) http://www.haskell.org/tmrwiki/FpVsOo "... it might be that you need to interface with external OO code, or you are porting an existing program and need to remain faithful to the original design, if only because you don't understand it well enough to convert it to a functional design. ..." Bulat, why not read all of this? Also see the end of that Wiki page, where a reference to a paper is given, which seems to solve all these problems, but my brain is to small to really be sure. ;-) 2. No matter how much you try, the code that you showed was not very close to a faithful Shapes implementation. If you dare to read the spec: http://onestepback.org/articles/poly/ http://www.angelfire.com/tx4/cus/shapes/ You made two proposals that don't solve the problem no matter of *style*: 1st proposal of Bulat: > just create list of draw functions itself: > > [drawCircle (10,10) 5, drawSquare (20,20) 10] > > you are not expected that this problem can be solved with one line of code? :) My reply: you are not building a list of objects. You are not organizing a loop whose body iterates over a list and executes functionality. 2nd proposal of Bulat: > for more complex tasks - declare interface as a structure: > > data ShapeInterface = Shape { draw :: IO (), > moveTo :: Point -> IO (), > calcArea :: Float > } > > > and return this structures from "constructor" functions: > > circle x y r = Shape { draw = drawCircle center r, > moveTo newCenter = ...., > calcArea = pi*r*r > } > where center = Point x y > > square x y size = Shape { draw = ...., > moveTo newCenter = ...., > calcArea = size*szie > } > > figures = [circle 1 2 3, square 4 5 6, circle 7 8 9] The tragedy here is that this stops to work once circles and squares do have different interfaces. You solution does not scale. Subtyping allows for interface extension, and the actual benchmark exploits this, but your code avoids it. Anyway the solution is trivial: ex. quantification, you didn't propose that. Cheers, Ralf (back to Cobol) > -----Original Message----- > From: Bulat Ziganshin [mailto:bulatz@HotPOP.com] > Sent: Thursday, June 23, 2005 11:37 PM > To: Ralf Lammel > Cc: Pal-Kristian Engstad; haskell-cafe(a)haskell.org > Subject: Re: [Haskell-cafe] RE: Re[4]: [Haskell] Dynamic binding > > Hello Ralf, > > Thursday, June 23, 2005, 11:40:13 PM, you wrote: > > RL> a) building (i) a list of data is fundamentally different > RL> from building (ii) a list of anticipated results of each datum. > RL> I would be surprised to hear that this counts as a valid technique. > RL> BTW, you can do the *same* in a lazy OO language. (No lazy OO language > RL> at hand -- well lazyness can be simulated.) > > sorry, "valid" technique is technique that work :) i use in my own > program all the three ways i mentioned to solve problems of different > complexity > > afair, you are relatively new to Haskell (relatively to my 1-year > experience :) and, i think, you are not share FP thinking style. when > programming in Haskell, i think in terms "what thing i will need in > this point of program?". if i need, for example, a possibility to check > string against regular expression, then i will pass a function which > does this check, not original RE. if i need a possibility to > draw a shape, i will pass action which draws this shape. if i need > several functions, i just combine them in a tuple > > there is one interesting example in my program. i have a list of > wildcards and list of filenames and for each filename i need to know > number of first wildcard to which this filename matched. in early > stages of my program development i just passed list of wildcards to > file-finding routine (as [Wildcard]). then, i changed list of wildcards > to list of functions which check match against each wildcard > ([Filename->Bool]). and after that, i changed this to one function which > just finds first True answer (Filename->Int). it was also more > effective to compute this function only one time (it was something > compiled > on moment of computing and worked as fast as hand-written analyzer for > given set of wildcards) > > as you see, i slowly migrated from traditional way of solving this > problem to perfectly functional way and it was required several months > > RL> a) building (i) a list of data is fundamentally different > RL> from building (ii) a list of anticipated results of each datum. > > i think that you don't have "Haskell brain" ;) and therefore don't > "trust" functions, which are passed as parameters, collected in lists, > saved in data structures and so on. you are prefer to "put hands on" > some data, preferably an object, which can be manipulated with any > method declared in his interface. i'm right? ;) > > FP encourage another way - passing functions which will then be applied to > some additional arguments, as in my program, where file-finding > function absolutely don't need list of wildcards. it just need to map > filename to wildcard number, so a Filename->Int parameter is just > enough > > in the draw example, each elment in a list was an action (having type > IO() ), so i don't create list of anticipated results, i created list > of actions which can be performed, for example, by sequence_ > > > RL> Anyway, even if people end up coding as you propose, > RL> it won't work in general. Think of mutation methods that > RL> change the state but preserve the type. Then your list will > RL> still be heterogonous. NO? > > my second example was just of this type. it uses IORefs to hold > current state, but this IORefs don't need to appear in interface > > see method moveTo, which changes state variable center, and method > draw, which uses this variable > > >> this state is just don't need to appear in interface definition :) > >> circle x y r > > RL> You are not talking about state but constructor arguments. > > "interface definition" is a structure ShapeInterface, which have only > fields for exposed object methods. so it supports any figures in > universe :) > > RL> In OO, mutable state tends to leak to the interface, > RL> perhaps not as public fields, perhaps not even as public > > only in C++ and other languages which need to calculate object size :) > declaration of _non-public_ fields in _interface_ is something strange > ;) > > >> this state is just don't need to appear in interface definition :) > >> > >> if you need to maintain mutable state, this is also not a problem: > >> > >> data ShapeInterface = Shape { draw :: IO (), > >> moveTo :: (Int,Int) -> IO (), > >> calcArea :: Float > >> } > >> circle x y r = do > >> center <- ref (x,y) > >> return Shape { draw = val center >>= drawCircle r > >> , moveTo = (center=:) > >> , calcArea = pi*r*r > >> } > >> main = do > >> figures <- sequence [circle 1 2 3, square 4 5 6, circle 7 8 9] > >> mapM_ draw figures > >> mapM_ (moveTo (0,0)) figures > >> mapM_ draw figures > >> > >> ref=newIORef > >> val=readIORef > >> (=:)=writeIORef > > > > -- > Best regards, > Bulat mailto:bulatz@HotPOP.com > >

1 0

Re: [Haskell] Dynamic binding
by Andrew Ward 24 Jun '05

24 Jun '05

Jan-Willem Maessen wrote: > > On Jun 22, 2005, at 9:38 PM, Andrew Ward wrote: > >> Pal-Kristian Engstad wrote: >> >>> On Wednesday 22 June 2005 05:38 pm, Andrew Ward wrote: >>> >>>> What would be the normal way for a Haskell programmer to handle the >>>> typical shape example in beginner OO tutorials? >>>> >>> >>> By not doing OO. You have to ask yourself, what is the purpose >>> and/or benefit of using OO? In C++, OO is _useful_ because you >>> restrict the problems of mutable data (by enclosing it in C++ classes). >>> >>> ML type languages have other methods of doing things, and guess >>> what, OO is not that needed for these languages. Sum-types, >>> pattern-matching and data constructors make half of the need for OO >>> go away. Higher order functions and make it even less needed. For >>> the rest, there's always work-arounds. >>> >>> PKE. >>> >> To handle the problem of drawing all shapes, in c++, I would have a >> list of shape pointers: >> >> struct shape{ virtual void draw(...);}; >> struct circle : public shape {...}; >> struct square : public shape {...}; >> std::list<shape *> shapes; >> for(std::list<shape *>::iterator it = shapes.begin();it != >> shapes.end();++it) >> { (*it)->draw(...); } >> >> This general pattern of dynamic binding I use over and over again. >> Could you give me some example code of this type of thing handled in >> Haskell's way? Assuming that the number of classes deriving from >> shape might get quite large. > > > It seems to me that if this is the specific problem being addressed, a > list of higher-order functions is exactly the right solution in any > ML-like language, and this is why there have been several responses to > that effect. > > I do think it's fair to say "consider changing the way you think" to > OO programmers trying to learn Haskell. If we were on an OOP mailing > list, I could ask for days how to simulate pattern matching and > algebraic types---and get a nonsensical runaround involving the > visitor pattern and huge swaths of unreadable code. > > Ralf, I think it's incumbent on you, having said several times "that > isn't solving the problem", to more clearly explain what problem you > think exists and cannot be solved gracefully (I suspect it has to do > with extensible down-casting---which is indeed hard in Haskell, but > many reasonable people might consider irrelevant or even overtly bad). > > Andrew, if this isn't the problem you're actually trying to solve, can > you explain why a simple list of functions doesn't help you? > I think I will need to learn a little more Haskell before I can appreciate all the different responses. However I will try to answer your question. Assuming I have a list of shapes somewhere in my program. The list would be heterogeneous, or at least contain data constructed using various different type constructors. The list would also be changing all the time, for example in a drawing program. So, using the suggestion of a list of drawing functions, would this not mean I would have to alter the list of drawing functions each time I alter the list of shapes? It does not seem an extensible solution. When it comes to adding new types or new functionality for existing types would it not be easy to miss updating a part of the program source that needed updating? The example I have found the simplest is the one given by Lennart, however this to me seems equivalent to the way people use switch statements in C to mimic dynamic binding. As I said before, I will have to learn more haskell and investigate OOHaskell properly. Thanks for all your responses. > -Jan-Willem Maessen > > >> Andrew Ward. >> >> >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell > > >

2 1

RE: Re[4]: [Haskell] Dynamic binding
by Ralf Lammel 24 Jun '05

24 Jun '05

Bulat, a) building (i) a list of data is fundamentally different from building (ii) a list of anticipated results of each datum. I would be surprised to hear that this counts as a valid technique. BTW, you can do the *same* in a lazy OO language. (No lazy OO language at hand -- well lazyness can be simulated.) Anyway, even if people end up coding as you propose, it won't work in general. Think of mutation methods that change the state but preserve the type. Then your list will still be heterogonous. NO? b) You wrote: > this state is just don't need to appear in interface definition :) > circle x y r You are not talking about state but constructor arguments. Please have a look here: http://www.angelfire.com/tx4/cus/shapes/cpp.html Circle Interface (Circle.h) class Circle: public Shape { public: Circle(int newx, int newy, int newradius); int getRadius(); void setRadius(int newradius); void draw(); private: int radius; }; [See getRadius and setRadius) In OO, mutable state tends to leak to the interface, perhaps not as public fields, perhaps not even as public proxy properties (but in the shapes example, it *does*), but then still as sublcass-specific interface member. Anyway, I am happy to add your and Lennart's proposals as appendices to the OOHaskell saga. And finally, Bulat, I agree with your point that > original exercise was about OO way to solve some problem. i want > to say that in Haskell it's better in most cases to use another, > functional way Thanks, Ralf (returning to his VB problem) > -----Original Message----- > From: Bulat Ziganshin [mailto:bulatz@HotPOP.com] > Sent: Thursday, June 23, 2005 4:55 AM > To: Ralf Lammel > Cc: Andrew Ward; Pal-Kristian Engstad; haskell-cafe(a)haskell.org > Subject: Re[4]: [Haskell] Dynamic binding > > Hello Ralf, > > Thursday, June 23, 2005, 11:36:20 AM, you wrote: > > >> just create list of draw functions itself: > >> > >> [drawCircle (10,10) 5, drawSquare (20,20) 10] > > RL> No! the exercise is about lists of shapes > RL> not lists of results of drawing shapes. > RL> This is clearly a major difference. > > in cases where you need to call only one function on created objects, > you can just insert in list calls to this functions (not their results! i > suppose > that drawXXX functions has "... -> IO ()" type) > > in cases where you need to call several functions for this object, you > can insert in list tuple or structure for each object, as i do in next > example. original exercise was about OO way to solve some problem. i want > to say that in Haskell it's better in most cases to use another, > functional way > > RL> Bulat wrote: > > >> for more complex tasks - declare interface as a structure: > >> > >> data ShapeInterface = Shape { draw :: IO (), > >> moveTo :: Point -> IO (), > >> calcArea :: Float > >> } > > RL> No! You miss the point that the different shapes > RL> differ regarding state types. > RL> You don't have a chance when you use one datatype. > > this state is just don't need to appear in interface definition :) > > see for example: > > data ShapeInterface = Shape { draw :: IO (), > calcArea :: Float > } > > circle x y r = Shape { draw = drawCircle x y r, > calcArea = pi*r*r > } > > square x y size = Shape { draw = drawSquare x y size, > calcArea = size*szie > } > > figures = [circle 1 2 3, square 4 5 6, circle 7 8 9] > > > > > > if you need to maintain mutable state, this is also not a problem: > > data ShapeInterface = Shape { draw :: IO (), > moveTo :: (Int,Int) -> IO (), > calcArea :: Float > } > circle x y r = do > center <- ref (x,y) > return Shape { draw = val center >>= drawCircle r > , moveTo = (center=:) > , calcArea = pi*r*r > } > main = do > figures <- sequence [circle 1 2 3, square 4 5 6, circle 7 8 9] > mapM_ draw figures > mapM_ (moveTo (0,0)) figures > mapM_ draw figures > > ref=newIORef > val=readIORef > (=:)=writeIORef > > > RL> haskell-cafe? > > as you wish :) > > -- > Best regards, > Bulat mailto:bulatz@HotPOP.com > >

2 1

Re[4]: [Haskell] Dynamic binding
by Bulat Ziganshin 23 Jun '05

23 Jun '05

Hello Ralf, Thursday, June 23, 2005, 11:36:20 AM, you wrote: >> just create list of draw functions itself: >> >> [drawCircle (10,10) 5, drawSquare (20,20) 10] RL> No! the exercise is about lists of shapes RL> not lists of results of drawing shapes. RL> This is clearly a major difference. in cases where you need to call only one function on created objects, you can just insert in list calls to this functions (not their results! i suppose that drawXXX functions has "... -> IO ()" type) in cases where you need to call several functions for this object, you can insert in list tuple or structure for each object, as i do in next example. original exercise was about OO way to solve some problem. i want to say that in Haskell it's better in most cases to use another, functional way RL> Bulat wrote: >> for more complex tasks - declare interface as a structure: >> >> data ShapeInterface = Shape { draw :: IO (), >> moveTo :: Point -> IO (), >> calcArea :: Float >> } RL> No! You miss the point that the different shapes RL> differ regarding state types. RL> You don't have a chance when you use one datatype. this state is just don't need to appear in interface definition :) see for example: data ShapeInterface = Shape { draw :: IO (), calcArea :: Float } circle x y r = Shape { draw = drawCircle x y r, calcArea = pi*r*r } square x y size = Shape { draw = drawSquare x y size, calcArea = size*szie } figures = [circle 1 2 3, square 4 5 6, circle 7 8 9] if you need to maintain mutable state, this is also not a problem: data ShapeInterface = Shape { draw :: IO (), moveTo :: (Int,Int) -> IO (), calcArea :: Float } circle x y r = do center <- ref (x,y) return Shape { draw = val center >>= drawCircle r , moveTo = (center=:) , calcArea = pi*r*r } main = do figures <- sequence [circle 1 2 3, square 4 5 6, circle 7 8 9] mapM_ draw figures mapM_ (moveTo (0,0)) figures mapM_ draw figures ref=newIORef val=readIORef (=:)=writeIORef RL> haskell-cafe? as you wish :) -- Best regards, Bulat mailto:bulatz@HotPOP.com

2 1