Haskell Antipattern: Existential Typeclass

I have observed pattern of design emerging in various Haskell libraries, for example vty-ui, GlomeTrace, and XMonad. Here is an excerpt from vty-ui’s interface. The snippet is long but simple, and I need all of it to demonstrate my point.

class Widget w where
    render :: DisplayRegion -> w -> Image
    growHorizontal :: w -> Bool
    growVertical :: w -> Bool
    primaryAttribute :: w -> Attr
    withAttribute :: w -> Attr -> w
mkImage :: Widget a => Vty -> a -> IO Image
data AnyWidget = forall w. Widget w => AnyWidget w
data Text
data Box
data Fill
instance Widget AnyWidget
instance Widget Text
instance Widget Box
instance Widget Fill
text :: Attr -> String -> Text
hBox :: (Widget a, Widget b) => a -> b -> Box
vBox :: (Widget a, Widget b) => a -> b -> Box
hFill :: Attr -> Char -> Int -> Fill
vFill :: Attr -> Char -> Fill

This module models the concept of a GUI widget. It defines a class with a basis of operations on Widgets, and then instantiates a few data types into the class. To facilitate passing around arbitrary widgets instead of specific instances, it provides an AnyWidget class. This Any* class is the tell-tale sign of this antipattern.

When I was using the above interface, I found myself immediately wrapping the results of text, hbox, and the other combinators in AnyWidget. By throwing away the information of exactly what instance of Widget it was I lost nothing, all the same operations were available to me. Astute readers might notice that withAttribute is an exception, because it has a w to the left and to the right of an arrow, so if I pass it a Box, I know I will get a Box back. But I cannot use that knowledge for anything else, so it doesn’t buy me anything.

There is a simpler and more direct way to encode the same thing. Here is the interface I would have written to this library:

data Widget = Widget {
    render :: DisplayRegion -> Image,
    growHorizontal :: Bool,
    growVertical :: Bool,
    primaryAttribute :: Attr,
    withAttribute :: Attr -> Widget
}
mkImage :: Vty -> Widget -> IO Image
text :: Attr -> String -> Widget
hBox :: Widget -> Widget -> Widget
vBox :: Widget -> Widget -> Box
hFill :: Attr -> Char -> Int -> Widget
vFill :: Attr -> Char -> Widget

I know just from looking at the types that all the code in the module could be converted to this style. Every operation has the exact same assumptions as in the old version, and all the extra guarantees that the old one provided were useless because they were never used as assumptions. Plus, you don’t have to wrap every call to a combinator with AnyWidget. By exposing the constructor for the Widget type, it gives users the same opportunity to make custom Widgets as the class interface gave.

You might be thinking, “but what if somebody else made a widget type which did use the additional assumptions that the separated data types provided, for example,

data Window
instance Widget Window
window :: Widget w => (Int,Int) -> w -> Window
windowSize :: Window -> (Int,Int)
adjustSize :: (Int,Int) -> Window -> Window

“Haven’t we just excluded this possibility from the interface?” Turns out that we have not; just replace the instance with a function:

toWidget :: Window -> Widget

See how this is going? Classes become data types, instances become functions. I’m just manually “expanding” what GHC does for you. Of course, the expansion is smaller than the original.

I advocate a direct programming style in Haskell. Advanced type system features have their place, but plain old functions go a long, long way. Functions are the masters of reuse: when you use an advanced feature, you need a yet more advanced feature to abstract over it (think: classes < existential types < universally quantified constraints < unknown). But all you need to abstract over a function is another function.

About these ads

31 thoughts on “Haskell Antipattern: Existential Typeclass

  1. In the case of XMonad, I think much of the type class usage is simply because it needs to be able to Show/Read its whole state on restarts. Thus the much-used trick of replacing a function with a showable data type and a type class.

  2. you do have a difference with the class, which might be either a feature or a limitation.
    While the record fields can close over arbitrary runtime data, the implementation of the typeclass methods is known at compile time (unless you use a weird trick like the reflection package).
    Operationally this means that you can create the code once and it’s more likely to get inlined.
    At an high level it gives some coherency guarantees, the type system ensures that all the e.g. Box’es are going to behave in the same way.

    In this particular case the record approach is probably more appropriate, though.

  3. It’s quite close TypeCase pattern (Oliveria and Gibbons, Haskell Workshop 2005). All the examples presented in that paper use functors as the class parameter, though I can’t deduce from a quick re-reading if having the param a functor is essential to a TypeCase being a TypeCase.

    TypeCase is also the pattern used by Jacques Carette, Oleg Kiselyov and Chung-chieh Shan for their tagless interpreters.

  4. Hmm, on re-reading the TypeCase paper (the first author was Bruno Oliveira by the way, I made a typo above), I’m not sure the anti-pattern is that close to the TypeCase pattern.

    Certainly in the existential anti-pattern version, the Widget class seems somewhat type-indexed by the Text, Box and Fill cases but I don’t think their actual use corresponds to a TypeCase. Your record version is clearly unrelated to the smart-datatype translation of TypeCase that uses GADTs.

    Feel free to delete both my messages, apologies for the blognoise.

  5. Hi,

    I’m the author of vty-ui. I’m glad to hear that someone is looking at my code! :) I appreciate the thoughtful post.

    I’m curious: you say, “Plus, you don’t have to wrap every call to a combinator with AnyWidget.” But that’s not true: the only intended use for AnyWidget is type unification for lists. Maybe that’s what you’re actually referring to, though (i.e., in a Widget instance). But AnyWidget should almost never be necessary in, say, an application’s usage of combinators when constructing the user interface.

  6. qelt: Huh, that’s interesting. I guess the alternative is to provide Layout { …, serialize :: String, deserialize :: Layout }. XMonad uses a witness to read again, so that is the role that the record plays in deserialize. But that is not saving very much work, because plumbing into readable/showable things is kind of a pain.

    Saizan: I don’t know if I buy it. Once you wrap it up in an existential type, GHC has lost the information to inline. On the flip side, whenever the precise instanc was known, the function that generated the record would be known and could just as well be inlined.

  7. Jonathan: something I always keep in mind when I am designing libraries (which, incidentally, I am desperately trying to convince my boss of at the moment): the purpose of code is to be abstracted over. Very seldom are you writing a library in which people will only be constructing literals with your primitives. Once the code reaches a certain complexity, those literals will be factored out into functions that generate and transform them.

    And that is exactly the situation I was in with vty-ui. I am not constructing literals. Instead I am composing interactive UIs together out of smaller pieces, using a “UI” applicative functor, which commonly returns a widget. So the common case is I have two UIs a and b passed as arguments, and am writing expressions like liftA2 (<++>) a b.

    It is weird to categorize UIs on the type of their outermost Widget. I never care. All I care about is that it is some widget; i.e. I can compose it with something else and render it.


    type Editor = UI AnyWidget
    lambda :: Editor
    app :: Editor
    over :: Editor -> Editor -> Editor

    is simpler and more encapsulated than


    type Editor a = UI a
    lambda :: Editor Text
    app :: Editor Box
    over :: (Widget a, Widget b) => Editor a -> Editor b -> Editor Box

    See the issue? There is too much information in the type. Text has as much to do with the specification of a lambda editor as Box or Fill does — nothing. If I vary that detail, nobody should be the wiser, so it doesn’t belong in the type.

  8. Luke,

    That use case makes sense. Fully agreed on the complexity point. And certainly, AnyWidget is a convenient thing to use there. :) My point was merely that you only need to use AnyWidget at the outermost layer, not each time you use a combinator. But you knew that.

    Despite the difference in design, I do sincerely hope that vty-ui *does* give you the composability that you want; that is one of my motivations for writing the library. If you end up writing any widgets or making any changes that you can contribute, please don’t hesitate to darcs-send them to me!

  9. Jonathan: Yeah, don’t get the wrong impression. vty-ui is a nice composable, pure interface to console graphics, and it has been pleasant to use. This particular design choice makes it a bit awkward, but of course there is no loss of power, so I can just wrap it up into what I want it to look like and go from there. Thanks for writing it. :-)

  10. Composable! Pure! Great. I’m glad you’re getting value out of it.

    When I get time I’ll resume work on the development branch. I’m experimenting with an “edit” widget, but that’s an entirely different can of worms because it requires some event loop design choices and takes vty-ui into the framework world. I’m not sure I like it yet, but it’s interesting.

    I’ve also refactored the rendering model in the development branch to accommodate storing the location and size of specific widgets during rendering, since in some cases that information is required.

  11. Saizan: Isn’t the record basically just what using type-classes will get expanded to, before GHC inlines it? Doesn’t it mean that this would be just as likely to get inlined as well?

  12. “I advocate a direct programming style in Haskell. Advanced type system features have their place, but plain old functions go a long, long way.”

    Hear Hear! “Advanced” usually means “Confusing and maybe even Confused”.

    I very much liked your simplified widget type, with its recursion branching over
    the new attribute in withAttribute.

  13. Yair :
    Saizan: Isn’t the record basically just what using type-classes will get expanded to, before GHC inlines it? Doesn’t it mean that this would be just as likely to get inlined as well?

    My point was what you get via the typeclass mechanism is a dictionary constructed in a much more controlled way than what using a dictionary directly allows.
    And these constraints are well known to GHC, so it can take advantage of them.
    You can by accident use the record type in the same controlled way the typeclass would do, but that has to be rediscovered by GHC indipendently via other optimization passes before it can exploit what’s already known with the typeclass.
    is GHC smart enough yet? that i don’t know :)

    However more importantly what GHC exploits for operational purpouses are properties that are also useful for reasoning about the code, which, again, have to be rederived by looking at how these dictionaries are constructed and threaded around if you use the record type directly.

    So throwing away an existential for a record is an operation you’ve to pay for, you have to judge if the benefits are worth the price.

  14. To be clear, in “throwing away an existential for a record” i meant to refer to an existential with a typeclass context vs. a record of the methods like here, both terms are more general than that.

  15. I agree with Luke, down with the proliferation of misused type classes! I’ve just encountered this in HDBC as well, namely the IConnection type class.

    In a sense, these abstractions are more like objects than like abstract data types when viewed in the light of this paper. Ironically, ordinary functions and records are better suited to that than type classes.

    I think this antipattern is so widespread that it merits a Monad.Reader article.

  16. The translation to records seems to fail if you use even a slightly nontrivial example:

    data MyWidget = MyWidget { menu :: Menu … }
    setMenu :: Menu -> MyWidget -> MyWidget

    There’s no way to implement setMenu on the Widget record, so there’s no translation of:

    setMenu myMenu (withAttribute myWidget fooAttribute)

    … because in the translated world, withAttribute requires the MyWidget to be *irreversibly* flattened down to a Widget.

    Two ways to fix this spring to mind:

    1) add a typeclass for withAttribute (which is where we started), or
    2) add a type parameter to Widget to allow it to carry knowledge of the type of widget:

    data Widget a = Widget { extraBitsWidget :: a, … }
    data MyWidget a = MyWidget { extraBitsMyWidget :: a, setMenu :: Menu -> Widget (MyWidget a) }

    Note that setMenu must produce a Widget not just a MyWidget, since it could want to (say) use growVertically to make room for the menu. But this is now non-composable, due to the necessity of the ‘Widget’ in the return type of setMenu. With the ‘data’ form I could write:

    data MenuWidget baseWidget = { … }

    but if I try the same thing using a record:

    data MenuWidget baseWidget a = { …, setMenu :: Menu -> baseWidget (MenuWidget baseWidget a) }

    … I need a typeclass in order to be able to apply ‘growVertically’ within setMenu.

    It seems to me, then, that the technique described in the article does not in fact cover as many use cases as the typeclass approach. It’s not clear to me how to fix it so that it does. Therefore, I don’t accept that the argument for the ‘existential typeclass’ being an anti-pattern has been convincingly made (yet).

    Viewed from another perspective, the key difference between record-of-functions and type-with-typeclass is that TwT carries more compile-time information, and thus more properties can be checked at compile time, so more correct programs can be admitted and more incorrect programs can be rejected. Perhaps it’s the record-of-functions which we should consider to be an antipattern?

  17. If this is an anti-pattern, what is the pattern to deal with (ad-hoc) polymorphic collections? I know this is a really OO way of thinking about it, so help me out: I imagine having an interface (for rendering, say) and wanting to have a single generic collection of renderable widgets that don’t necessarily share a type. The specific widgets may not even exist at the time the render’s caller is written. I don’t want to make a special collection type that knows about render or anything like that.

    Python:

    for widget in widgets:
    widget.render(drawingContext)

    Java:

    interface Renderable { void render(DrawingContext d); }
    List widgets = new ArrayList();

    for (Renderable r : widgets) {
    r.render(drawingContext);
    }

    What’s the idiomatic Haskell equivalent?

  18. Aran, this is another perfect example of what the post was addressing. There is no difference between “some object, where the only thing we know about it is that it has a draw method” and a simple draw method itself. We have no way of getting any more information about it, so why not just throw out that information in the first place. Using the technique in the post, we can factor:

    class Renderable a where
    render :: a -> IO ()

    data AnyRenderable = forall a. Renderable a => AnyRenderable a

    Into:

    data Renderable = Renderable { render :: IO () }

    The ability to do this is unique to Haskell, because Haskell does not allow downcasting. Thus, when you have an AnyRenderable object, it is absolutely assured that you cannot get anything from that but its render method (modulo unsafeCoerce: I don’t believe in magic). So although the former may look more extensible to people from an OO background, it is really just a notational difference — and it doesn’t necessarily save any notation either.

    I’m currently thinking about how to characterize when it is okay to apply this transformation, since zygoloid pointed out that some expressivity is in fact lost in the example in the post (I don’t consider the expressivity lost to be essential in this case — might as well throw it away — but it is important to know the consequences). At the very least you can always do it when the class looks like an OO object; i.e. when you have:

    class Foo a where
    method1 :: a -> type1
    method2 :: a -> type2

    data AnyFoo = forall a. Foo a => AnyFoo a

    Where the “typen” do not contain a. You can factor that into:

    data Foo = Foo { method1 :: type1, method2 :: type2, … }

    Without loss of expressivity. Things get more complicated when multiple a’s appear in the method signatures, though. So complicated that an existential over such a class is a very confusing thing to think about, so you probably did it wrong anyway. But that’s just my opinion.

  19. I’m not sure whether zygoloid’s example is actually valid. It’s probably best if you rename the new Widget record to AnyWidget because that’s exactly what it is. Or, for the recent Foo example, the record should be

    data AnyFoo = AnyFoo { method1 :: type1, method2 :: type2, … }

    which comes with a universal function

    embed :: Foo a => a -> AnyFoo

    The question is whether you still need the class Foo or not.

    I think what zygoloid’s example says is that you may want different types with additional operations besides those in the class Foo and then you obviously can’t replace them with a AnyFoo record. Of course, as soon as you make say a heterogenous list of AnyFoo, the additional operations disappear, and it boils down to the question of whether you are actually using the additional operations elsewhere.

  20. So, if I’m understanding right, to be really explicit, this approach would be idiomatic Haskell:

    data Button = Button {…}
    renderButton :: Button -> Canvas -> Canvas
    renderButton = …
    b = Button …

    data TextBox = TextBox {…}
    renderTextBox :: TextBox -> Canvas -> Canvas
    renderTextBox = …
    tb = TextBox …

    …more widget types and definitions…
    c = Canvas …
    allWidgets :: [Canvas -> Canvas]
    allWidgets = [renderButton b, renderTextBox tb, ...]
    render = foldr ($) c allWidgets

    and if I wanted, I would do the following, but it is unnecessary:

    type AnyWidget = Canvas -> Canvas

  21. Aran, yes! Well I don’t know about “idiomatic Haskell”, since this post was geared toward Haskellers whose ways I am trying to change, but that is exactly how I would do it. I would probably hide the widget constructors and only expose the abstract data types, but that is orthogonal to the discussion at hand.

  22. Nice article! I’m just a Haskell lamer. But I came to the same conclusion when programmed with gtk2hs. First I tried to mimic OO encapsulation with existential type classes. After few unsuccessful tries I sticked with data type and function as you did. Even if it look so Type classes are something totally different to OO interfaces..

  23. This discussion is pretty interesting. I’m the author of the “Data Abstraction, Revisited” paper. I also happen to be a fairly avid Haskell programmer. It seems to me that the more object-oriented organization is fairly nice in this case. Not having the “field access o.f”, or “dot notation” does make using the code less pretty. Have you all come to a conclusion on the right way to do things?

    PS: I particularly like the comment that “There is no difference between ‘some object, where the only thing we know about it is that it has a draw method’ and a simple draw method itself. “

  24. One needs just to define an operator for “dot access”:

    infixl 4 ^.
    a ^. b = b a

    — Example:
    data Alpha = Alpha { beta :: Beta
    , gamma :: Alpha
    }

    data Beta = Beta { alpha :: Alpha }

    data Gamma = Gamma { gAlpha :: Alpha}

    test x = x ^. gAlpha ^. beta ^. alpha

  25. Luke,

    I’m replying to “Aran, this is another perfect example of what the post was addressing. There is no difference between “some object, where the only thing we know about it is that it has a method” and a simple draw method itself. ”

    Unfortunately, while these two schemas are equivalently expressive, there are definitely differences between them. In particular, “some object” might be serializable or have other useful properties.

    Consider a case where we are quantifying over the values in a type safe library — something over which we have no control. Something along the lines of

    type family Properties a :: *
    type family Contents a :: *

    data Widget a = Widget { widgetProperties :: Properties a
    , widgetContents :: Contents a }

    The point of this construct is that we can’t mix up “Window Properties” with “Button Properties”, and similarly for Contents, as we might with:

    data Widget = Widget { widgetProperties :: Properties, widgetContents :: Contents }

    The former construct allows us to write type safe DSLs which we know cannot be misused. Since these are all data, we can serialize them (for example). And the widget “sort” is /open/. We can always add new sorts of widgets without affecting previously written code.

    Now, as a user of such a DSL, I need to be able to actually use the widgets composed of these DSL terms. To me, such a composition must necessarily be a “heterogeneous” collection — a list or set or tree of terms. They are all Widgets, but different kinds of Widgets.

    I can use ExistentialTypes or fork the library and refactor the DSL. But either one trades away type safety, either at the level of unification or at the level of writing DSL terms. It seems to me that keeping that complexity (using ExistentialTypes) in one place is a much better alternative, given the constraint that the DSL terms must be data (i.e., cannot contain functions)

    I would be happy to hear suggestions, since I stumbled on your post while looking for a solution to this very problem. I would rather not have to use ExistentialTypes so that I can derive a bunch of complicated classes instead of writing them by hand.

    Unfortunately, I don’t think there are any easy answers. Open data types are hard to implement. Data types a la carte offers a solution, but none of the libraries I have data terms.

  26. Luke, technically there is a difference between the data Renderable and Renderable class — a Renderable’s (a -> IO ()) can contain any code whatsoever, whereas an AnyRenderable can _only_ contain code that’s been put into a Renderable instance. This can be useful for security where the ability to define instances is restricted. Granted, the point you were making was that most people’s uses of this are actually equivalent, but it’s interesting to note this restriction use-case. You could change it to Renderable { render :: a -> R () } where R is some restricted monad, but that only restricts what one is able to do in the monad, whereas a Renderable instance tells you “if there is a valid AnyRenderable value, then its implementation can only be one of the instances of Renderable, which I can find by inspection, restrict by namespaces, etc.”

  27. Alex, the idea is to not to replace the underlying object with the functions, but rather to strip it down to the functions as it goes into the container. There are still coherency issues as others have mentioned, but I don’t think this is a problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s