Hacker News Reader

Comment by dllthomas | Hacker News Reader

Two points here regarding Haskell. First, a function with typeclass constraints is less polymorphic (in that it will operate on fewer types) than polymorphic function without typeclass constraints. Of course, [the fully polymorphic version is] also more limited in how it interacts with the corresponding values.

Second, parametric polymorphism in Haskell is statically resolved. You can have polymorphic functions, but any given container still contains a single type. You can still do dynamic polymorphism in Haskell (by storing a list of records of functions, rather than storing data directly) but it doesn't typically involve type classes.

View on HN

The second point brings up an issue that confused me when I was first learning Haskell; maybe I can help others that are similarly confused. Coming from OO languages, the lack of heterogeneous containers seems painful in Haskell - after all, in OO languages you use containers of superclass or interface pointers all the time. Haskell has a different approach to handling the same problems, though, and it turns out there are several ways you can create (or eliminate the need for) heterogeneous containers.

The idiomatic way you'd create a "heterogeneous container" is to store a single algebraic datatype with different constructors, rather than try to store different types at all. This doesn't actually give you a heterogeneous container, of course, but it works perfectly in most cases, because in most cases the set of things you need to store in the container is closed. You really only need a truly heterogeneous container when you need the ability for someone else to come along and extend that set. Concretely, if you're writing a ray tracing application, you know all the possible shapes you may need to handle, and this approach is perfect.

On the other hand, if you're writing a ray tracing library and you want the library user to be able to define new shapes, you may want to consider another approach. The idiomatic approach here was already mentioned by dllthomas: this is a functional programming language, so use functions! Specifically, use a record of functions, with each function in the record serving the same role as a method in OO. The functions can have private data by closing over it.

Haskell has a couple of other options available, as well.

You can use existential types, but they don't really buy you anything over the record of functions approach other than perhaps looking superficially more like how you'd do things in an OO language. With this approach you define a typeclass and make all the types you want to store instances of it. The container then stores instances of the typeclass, rather than a concrete type.

You can also use Data.Dynamic to create dynamic values, which will allow you to store a truly unconstrained mix of types in the same container. Since you have to cast the dynamic values back to their real type before using them, though, this isn't a great solution - you end up with code that looks similar to chains of 'instanceof' in Java or 'dynamic_cast' in C++.

> The idiomatic approach here was already mentioned by dllthomas: this is a functional programming language, so use functions! Specifically, use a record of functions, with each function in the record serving the same role as a method in OO. The functions can have private data by closing over it.

This is also how one does OO programming in C: just roll your own v-table using a struct of function pointers. You don't get to close over an environment in that case, so you have to be careful to pass everything in.

There are similarities, to be sure. One difference is that state is more often closed over than passed around explicitly.

records of fuctions vs typeclasses: In general, you use a class when you want a different type for each different behavior, and there's only one sane behavior choice for each type.

You can use GADTs for this. For example:

  data Showable where
    Showable :: Show a => a -> Showable

This allows you to create a polymorphic container like [Showable 5, Showable "hello"] where the polymorphic type is constrained to be a member of the Show typeclass.

Note that GADTs are a bit overkill for this. All you really need is ExistentialQuantification. GADTs are ExistentialQuantification + TypeEqualities.

You can have polymorphic functions, but any given container still contains a single type.

This is the case for all typed programming languages, not just Haskell. So-called dynamic languages like Python, Ruby or Javascript are merely static languages with but a single type[0].

[0] http://existentialtype.wordpress.com/2011/03/19/dynamic-lang...

In C++, if I have a

    std::list<Parent *>

then some of those pointers may actually point at a Child. The client code doesn't care. This is an important kind of polymorphism.

In Haskell, you can't reasonably express this with typeclasses, which surprises folks new to Haskell. You can still express it (as I mentioned), it just takes a different form (and precisely which form is best can vary with other considerations).

In Haskell you don't need to express this with type classes as it is trivially covered by sum types. Type classes are mostly syntactic sugar providing for ad-hoc polymorphism. The real power is provided by the underlying algebraic data types.

Sum types only cover this trivially when the type is closed or when those adding new subtypes can be expected to modify all uses of the type. It's still not the same thing.

The need for an open sum tends to be vanishingly rare in my experience.

It occurs moderately frequently in libraries where a user should be able to define domain specific types along with how the library should treat those types. A classic example would be a raytracer where the user might be adding new kinds of scene elements. It probably shouldn't occur in application code.

For what it's worth, I do think people underestimate the applicability of closed sum types.

I'm aware of the raytracer library example. The solution to that is to not use types to represent shapes. Instead, classify shapes by primitive types (triangles, quads, bezier curves, NURBS, etc.) and use a closed sum for those. It's far less common for a user to want to create a new primitive type and you can always use an escape hatch in the closed sum that allows the user to define their own primitive along with a function to draw it in terms of one of the other primitives.

This thread got silly a while back. I'm abandoning it.

I don't know what you consider reasonable, but you can express this in Haskell with type classes and existential types:

   data P = forall a . Parent a => P a
   type PList = [P]

where Parent is a type class.

You have to be a bit more explicit when using a Child in the position of a Parent when adding to the list and you have to use (fully polymorphic!) pattern matches to extract elements from the list, but personally I consider this a good thing as it's more explicit.

Aside: Existential types is what OOP interfaces are -- and interfaces are often encoded as such in language semantics; see e.g. Types and Programming Languages (Pierce).

EDIT: Typos in code -- unfortunately my Haskell is a little rusty :(.

Yes, "Haskell can't reasonably express this with just typeclasses" is probably what I should have said. With the right extensions, Haskell can do anything, but it's not always going to be a good idea...

What's with the weasel words? Existential types aren't even remotely controverisial or dangerous.

> Of course, it's also more limited in how it interacts with the corresponding values.

This is backwards. Polymorphic values without constraints admit almost no operations at all - you can "copy" them, that's it. This is true to the point that (save diverging) given f :: a -> a, f can only have one meaning.

Invariance of sequence elements is also far less problematic in ML-family languages because they have sums.

"It" here being the fully polymorphic version. Rereading, it does seem misleading (or at best ambiguous) so I've expanded the pronoun.

I see. Sorry, I should have interpreted that more generously.

You're forgiven - certainly calling out the lack of clarity was important!

I haven't really explored this area of Haskell, but I think there are certain cases where this is possible. For example, I think there might be a way to have a list of tuples of `forall a. [(a -> b, a)]`, where a's type can vary, but applying the first element of the tuple to the second will always produce a `b`. I'm not sure if this is actually the case but it seems (theoretically) possible, and certainly would be convenient. More experienced Haskellers feel free to chime in...

Yeah, that's certainly possible. It's also largely frowned upon because it's usually over complex. For instance, in your example

    [exists a . (a -> b, a)]

is literally completely equivalent to

[b]

as the types ensure there is no other thing that can be done with those pairs.

The convenience factor is thus almost never the case. There are some nice theoretical properties and a great embedding of OO in Haskell via existential typing [0], but it should rarely be used.

[0] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf

OK, since I didn't give a very good example, let me try to show a better one. Let's imagine you're writing a testing library. You have a series of tests; each one of them takes in an input, a function to run on the input, and an expected output.

    data Test i o = Test String i (i -> o) o

and then say your testing function is something like

    runTest :: Eq o => Test i o -> IO ()
    runTest (Test name input f output) = case f input of
        o | o == output -> putStrLn $ name ++ " passed"
          | otherwise   -> putStrLn $ name ++ " failed"

Then let's say you had a bunch of tests. For example, you want to test that addition works:

    test1 = Test "addition" (1, 2) (\a b -> a + b) 3

And you want to test string concatenation:

    test2 = Test "concat" ("hello", "world") (\a b -> a ++ b) "helloworld"

Then you could write your tests as

    doTests = runTest test1 >> runTest test2

Now if you have a lot of tests, it would be nice to put them in a list:

    doTests tests = forM_ tests runTest

However, this would require that every test have the same inputs and outputs. You couldn't do

    doTests [test1, test2]

Even though the resulting type is known (it will be an IO () regardless), and even though runTest will operate on each one, because test1 and test2 have different types, you can't put them all in a list.

I think that `forall` and similar allow you to get around this restriction somehow, but I don't really know how that works.

I mean, I agree such examples exist. I don't think this is yet a truly good example, though. The real advantage to existential types like this are in creation of multiple variants---again I recommend reading Jeremy Gibbons' paper.

But, for completeness, here's how you could write your type

    {-# LANGUAGE ExistentialQuantification #-}
    data Test = forall i o . Test i (i -> o) (o -> o -> Bool) o

Although, note, this is exactly equivalent to `Bool`, although in two ways—if we knew the comparator function was commutative then there'd be just one way to convert to `Bool`.

    testBool :: Test -> Bool
    testBool (Test i fun cmp o) = cmp (fun i) o

    testBool' :: Test -> Bool
    testBool' (Test i fun cmp o) = cmp o (fun i)

But in either case there are no other ways to "observe" the existentially quantified types since we've forgotten absolutely everything besides `Bool`. More likely we would want to also, say, show the input.

    data Test = forall i o . (Eq o, Show i) =>
                Test i (i -> o) o

and this type is now equal to `(String, Bool)`.

    testOff :: Test -> (String, Bool)
    testOff (Test i fun o) = (show i, fun i == o)

So, in general, if you're using existential types you really want to either be using multiple variants or when you have such a combination of observables that it's not worth expressing them all directly.

Reply on news.ycombinator.com