Friday, August 16, 2013

Tricking Haskell into being dynamic

Day 1. What do outsiders think of this language? Speaking for myself, I've always heard it has a strict type system that people learn to love. Today I want to use a simple example to bend the rules and get to the bottom of it.

I began Learn You a Haskell, and started typing in mundane stuff.

(Note that I am displaying code in embedded Gists, which may not appear correctly in RSS. Let me know if it's a problem.)

The language of course gently steps in and protects me. Comparing Nums and a list of Chars is nonsense. Yet...what if we wanted Haskell to evaluate this comparison and return false? I'm fully aware this is a bad idea, but it might teach us about how Haskell's type system really works.

So let's unwind how the type error above originates. What does the operator == expect?


This is really the crux of the problem, it grabs onto a type (which incidentally must be an instance of the Eq type class) and expects it for both arguments. I guess we have to give up, because a number and a string simply cannot be simultaneously substituted for a in the type signature above unless we can somehow make a new type which tricks Haskell. That would be magical, wouldn't it? Something like


Luckily most types are instances of Show, and provide a show function to represent themselves as strings. Turns out this is what the repl does when it prints values back. So we could compare Show instances by comparing their string representation.


Maybe this is good enough. But maybe we can put it inside a magical type and partially obscure the implementation. We could make different data constructors and write all kinds of messy combinations for implementing equality tests.


I'm sorry to inflict that code on you. Let's erase it from our minds using existential types. In quest of the Magic recipe, I jumped on #haskell and things got crazy. It's filled with friendly and alarmingly smart people.

Here's what I learned. If we leave the Haskell98 standard behind, we can open up a trap door in GHCI by starting it with the -XExistentialQuantification
option. This enables existential type extensions.

We can define a constructor for Magic which accepts anything that can be shown, then define equality by comparing string values.

The last one is false because show 5 is "5" whereas show "5" is "\"5\"". Nonetheless it's what we wanted.

This really is my first day learning Haskell, so please comment and set me straight if I'm doing things wrong. Also, what is a more realistic use of forall?

13 comments:

  1. Note that wrapping the type in the `Magic` constructor is (almost) exactly identical to wrapping the type in `show`, at least for the use cases you were interested in:

    >>> Magic 5 == Magic "the gathering"
    False
    >>> show 5 == show "the gathering"
    False

    However, there are other cases where the existential quantification is useful and cannot be trivially be replaced by a function.

    ReplyDelete
    Replies
    1. Yeah as I was writing about Magic I got the feeling that it wasn't an improvement. Can you tell me more about the best uses of existential quantification?

      Delete
    2. Existential quantification works well when the behavior you want to encapsulate cannot be easily packaged into a single function or record of partially-applied functions. I can't think of an example off the top of my head, but there is a well-known post that described the typical scenario where you want to avoid the existential type classes:

      http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-typeclass/

      Basically, any time you can get away with a record of partially applied functions it is usually beneficial to do so, but sometimes you can't and that's when you need ExistentialQuantification.

      Also, keep in mind that you can also use existential quantification to abstract away type variables that are not constrained by a type class. For example, check out this Stack Overflow answer from today that uses it to abstract away the internal accumulator of a fold:

      http://stackoverflow.com/a/18289075/1026598

      Delete
    3. Another advantage of using `show` rather than `Magic` is that Magic is only good for comparison(unless you manually extend it to do other things), whereas show lets you do anything you can do with strings.

      Delete
  2. " Also, what is a more realistic use of forall?"

    For example, I was simulating a card game. I wanted different players to have different strategies, and for that they need to have states that may have different types. So you do something like:

    data Player a = forall state. Player Cards state (Strategy state)
    data Strategy s = (s -> MyCards -> CardsPlayedSinceMyLastMove -> (MyMove, s) )

    Where Cards, MyCards, CardsPlayedSinceMyLastMove and MyMove are appropiate types. So Player holds the cards, an arbitrary state, and a strategy that uses the state and other information to make a move and modify the state.

    This can't be done without existential quantification, AFAIK.

    ReplyDelete
    Replies
    1. You could just store the strategy partially applied to the state already...

      Delete
    2. To elaborate on what Singpolyma is suggesting, you could have:

      data Player = P Cards Strategy

      data Strategy = S (Cards -> CardsPlayed -> (Move, Strategy))

      A function which constructs a strategy would then take any extra state it might need as a parameter, and update that state by applying itself recursively to new values when producing the Strategy in its result.

      Delete
  3. You can also get fully-Dynamic behaviour by using the Data.Dynamic module

    ReplyDelete
  4. You should try writing a (==) that takes arguments of of different types, returns False if they are not the same type, and uses regular comparison otherwise.

    Not that I would ever recommend using such a function, but it's a lot better than comparing strings. :)

    ReplyDelete
    Replies
    1. That's what I wanted to do initially and couldn't figure out how. The definition of Eq seems to prevent it. Can you give me a hint? Do I use Data.Dynamic like Singpolyma suggests?

      Delete
    2. This comment has been removed by the author.

      Delete
    3. Although in time you’ll find that you simply won’t need dynamic types at all, Data.Dynamic is likely to be the best approach for doing this sort of thing, as many things are already implemented.

      If you want to take a slightly lower level approach to get a handle of how things work, check out the Typeable typeclass — you can write the comparison function Lennart suggested using `Data.Typeable.cast`.

      Delete
  5. Define a new operator (===) for heterogenous equality. You can never use the Prelude (==) because of its type.

    ReplyDelete