Best way to implement ad-hoc polymorphism in Haskell?

Question

I have a polymorphic function like:

convert :: (Show a) => a -> String
convert = " [label=" ++ (show a) ++ "]"

But sometimes I want to pass it a Data.Map and do some more fancy key value conversion. I know I can't pattern match here because Data.Map is an abstract data type (according to this similar SO question), but I have been unsuccessful using guards to this end, and I'm not sure if ViewPatterns would help here (and would rather avoid them for portability).

This is more what I want:

import qualified Data.Map as M

convert :: (Show a) => a -> String
convert a 
    | M.size \=0 = processMap2FancyKVString a -- Heres a Data.Map
    | otherwise = " [label=" ++ (show a) ++ "]" -- Probably a string

But this doesn't work because M.size can't take anything other than a Data.Map.

Specifically, I am trying to modify the sl utility function in the Functional Graph Library in order to handle coloring and other attributes of edges in GraphViz output.

Update

I wish I could accept all three answers by TomMD, Antal S-Z, and luqui to this question as they all understood what I really was asking. I would say:

• Antal S-Z gave the most 'elegant' solution as applied to the FGL but would also require the most rewriting and rethinking to implement in personal problem.
• TomMD gave a great answer that lies somewhere between Antal S-Z's and luqui's in terms of applicability vs. correctness. It also is direct and to the point which I appreciate greatly and why I chose his answer.
• luqui gave the best 'get it working quickly' answer which I will probably be using in practice (as I'm a grad student, and this is just some throwaway code to test some ideas). The reason I didn't accept was because TomMD's answer will probably help other people in more general situations better.

With that said, they are all excellent answers and the above classification is a gross simplification. I've also updated the question title to better represent my question (Thanks Thanks again for broadening my horizons everyone!

Answer 1

What you just explained is you want a function that behaves differently based on the type of the input. While you could use a data wrapper, thus closing the function for all time:

data Convertable k a = ConvMap (Map k a) | ConvOther a
convert (ConvMap m) = ...
convert (ConvOther o) = ...

A better way is to use type classes, thus leaving the convert function open and extensible while preventing users from inputting non-sensical combinations (ex: ConvOther M.empty).

class (Show a) => Convertable a where
    convert :: a -> String

instance Convertable (M.Map k a) where
    convert m = processMap2FancyKVString m

newtype ConvWrapper a = CW a
instance Convertable (ConvWrapper a) where
    convert (CW a) = " [label=" ++ (show a) ++ "]"

In this manner you can have the instances you want used for each different data type and every time a new specialization is needed you can extend the definition of convert simply by adding another instance Convertable NewDataType where ....

Some people might frown at the newtype wrapper and suggest an instance like:

instance Convertable a where
    convert ...

But this will require the strongly discouraged overlapping and undecidable instances extensions for very little programmer convenience.

Answer 2

Your problem isn't actually the same as in that question. In the question you linked to, Derek Thurn had a function which he knew took a Set a, but couldn't pattern-match. In your case, you're writing a function which will take any a which has an instance of Show; you can't tell what type you're looking at at runtime, and can only rely on the functions which are available to any Showable type. If you want to have a function do different things for different data types, this is known as ad-hoc polymorphism, and is supported in Haskell with type classes like Show. (This is as opposed to parametric polymorphism, which is when you write a function like head (x:_) = x which has type head :: [a] -> a; the unconstrained universal a is what makes that parametric instead.) So to do what you want, you'll have to create your own type class, and instantiate it when you need it. However, it's a little more complicated than usual, because you want to make everything that's part of Show implicitly part of your new type class. This requires some potentially dangerous and probably unnecessarily powerful GHC extensions. Instead, why not simplify things? You can probably figure out the subset of types which you actually need to print in this manner. Once you do that, you can write the code as follows:

{-# LANGUAGE TypeSynonymInstances #-}

module GraphvizTypeclass where

import qualified Data.Map as M
import Data.Map (Map)

import Data.List (intercalate) -- For output formatting

surround :: String -> String -> String -> String
surround before after = (before ++) . (++ after)

squareBrackets :: String -> String
squareBrackets = surround "[" "]"

quoted :: String -> String
quoted = let replace '"' = "\\\""
             replace c   = [c]
         in surround "\"" "\"" . concatMap replace

class GraphvizLabel a where
  toGVItem  :: a -> String
  toGVLabel :: a -> String
  toGVLabel = squareBrackets . ("label=" ++) . toGVItem

-- We only need to print Strings, Ints, Chars, and Maps.

instance GraphvizLabel String where
  toGVItem = quoted

instance GraphvizLabel Int where
  toGVItem = quoted . show

instance GraphvizLabel Char where
  toGVItem = toGVItem . (: []) -- Custom behavior: no single quotes.

instance (GraphvizLabel k, GraphvizLabel v) => GraphvizLabel (Map k v) where
  toGVItem  = let kvfn k v = ((toGVItem k ++ "=" ++ toGVItem v) :)
              in intercalate "," . M.foldWithKey kvfn []
  toGVLabel = squareBrackets . toGVItem

In this setup, everything which we can output to Graphviz is an instance of GraphvizLabel; the toGVItem function quotes things, and toGVLabel puts the whole thing in square brackets for immediate use. (I might have screwed some of the formatting you want up, but that part's just an example.) You then declare what's an instance of GraphvizLabel, and how to turn it into an item. The TypeSynonymInstances flag just lets us write instance GraphvizLabel String instead of instance GraphvizLabel [Char]; it's harmless.

Now, if you really need everything with a Show instance to be an instance of GraphvizLabel as well, there is a way. If you don't really need this, then don't use this code! If you do need to do this, you have to bring to bear the scarily-named UndecidableInstances and OverlappingInstances language extensions (and the less scarily named FlexibleInstances). The reason for this is that you have to assert that everything which is Showable is a GraphvizLabel—but this is hard for the compiler to tell. For instance, if you use this code and write toGVLabel [1,2,3] at the GHCi prompt, you'll get an error, since 1 has type Num a => a, and Char might be an instance of Num! You have to explicitly specify toGVLabel ([1,2,3] :: [Int]) to get it to work. Again, this is probably unnecessarily heavy machinery to bring to bear on your problem. Instead, if you can limit the things you think will be converted to labels, which is very likely, you can just specify those things instead! But if you really want Showability to imply GraphvizLabelability, this is what you need:

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances
,          UndecidableInstances, OverlappingInstances #-}

-- Leave the module declaration, imports, formatting code, and class declaration
-- the same.

instance GraphvizLabel String where
  toGVItem = quoted

instance Show a => GraphvizLabel a where
  toGVItem = quoted . show

instance (GraphvizLabel k, GraphvizLabel v) => GraphvizLabel (Map k v) where
  toGVItem  = let kvfn k v = ((toGVItem k ++ "=" ++ toGVItem v) :)
              in intercalate "," . M.foldWithKey kvfn []
  toGVLabel = squareBrackets . toGVItem

Notice that your specific cases (GraphvizLabel String and GraphvizLabel (Map k v)) stay the same; you've just collapsed the Int and Char cases into the GraphvizLabel a case. Remember, UndecidableInstances means exactly what it says: the compiler cannot tell if instances are checkable or will instead make the typechecker loop! In this case, I am reasonably sure that everything here is in fact decidable (but if anybody notices where I'm wrong, please let me know). Nevertheless, using UndecidableInstances should always be approached with caution.

Answer 3

You may not be asking the right thing. I'm going to assume that you either have a graph whose nodes are all Maps or you have a graph whose nodes are all something else. If you need a graph where Maps and non-maps coexist, then there is more to your problem (but this solution will still help). See the end of my answer in that case.

The cleanest answer here is simply to use different convert functions for different types, and have any type that depends on convert take it as an argument (a higher order function).

So in GraphViz (avoiding redesigning this crappy code) I would modify the graphviz function to look like:

graphvizWithLabeler :: (a -> String) -> ... -> String
graphvizWithLabeler labeler ... =
   ...
   where sa = labeler a

And then have graphviz trivially delegate to it:

graphviz = graphvizWithLabeler sl

Then graphviz continues to work as before, and you have graphvizWithLabeler when you need the more powerful version.

So for graphs whose nodes are Maps, use graphvizWithLabeler processMap2FancyKVString, otherwise use graphviz. This decision can be postponed as long as possible by taking relevant things as higher order functions or typeclass methods.

If you need to have Maps and other things coexisting in the same graph, then you need to find a single type inhabited by everything a node could be. This is similar to TomMD's suggestion. For example:

data NodeType
    = MapNode (Map.Map Foo Bar)
    | IntNode Int

Parameterized to the level of genericity you need, of course. Then your labeler function should decide what to do in each of those cases.

A key point to remember is that Haskell has no downcasting. A function of type foo :: a -> a has no way of knowing anything about what was passed to it (within reason, cool your jets pedants). So the function you were trying to write is impossible to express in Haskell. But as you can see, there are other ways to get the job done, and they turn out to be more modular.

Did that tell you what you needed to know to accomplish what you wanted?