I have been playing with creating a fully typed DSEL in Haskell using GADTs and such for a fully type-safe AST, and it seems that doing a correctly typed compiler requires constructs such as maps from Haskell types to both types and values (typed environments) and such that can be understood by the Haskell type system. C++ has the Boost.Fusion library with constructs like these (type->value maps, vectors of typed values, etc.). Data.Tuple takes care of sequences, but are there Haskell versions of things like Boost.Fusion maps?
Asked
Active
Viewed 464 times
10
Jeremiah Willcock
- 30,161
- 7
- 76
- 78
-
What was the reason for the downvote? – Jeremiah Willcock Nov 29 '11 at 17:27
-
When you describe a "compiler" what representation are you compiling from/to? If you have the GADT, are you really writing the interpreter for it, or a function from the GADT to, e.g., C code? – sclv Nov 29 '11 at 17:47
-
Either -- the same issues will come up in anything that translates the typed AST to anything else or runs it. – Jeremiah Willcock Nov 29 '11 at 18:20
-
yea why the downvotes? seems like a fine question to me.. – Claudiu Nov 29 '11 at 18:39
-
Just out of curiosity -- this is perhaps not the forum, but I don't think the issue comes up as much as you'd imagine? However, take a look at this: http://okmij.org/ftp/tagless-final/index.html#tc-GADT – sclv Nov 29 '11 at 19:04
4 Answers
10
Look at the dependent-map package. I haven't used it myself, but it seems to do what you're asking for. If you need to really use type (and type-only) equality then you may need to agree on a default value or use a TypeRep as the key instead.
Nathan Howell
- 4,627
- 1
- 22
- 30
4
First, the all-too-obvious answer is that you can easily write a "type->value map" using Typeable (part of base library):
import Data.Typeable
import Data.Map
type TypeMap a = Map TypeRep a
insertT :: Typeable k => k -> a -> Map k a -> Map k a
insertT v = insert (typeOf k)
lookupT :: Typeable k => k -> a -> Map k a -> Map k a
lookupT v = lookup (typeOf k)
Now you can use code like insertT (undefined :: Int) 5 to insert elements by type.
But looking at Fusion, this doesn't really look like what you might be after. It seems it allows you to build code working on arbitrary data structures? That is something that in Haskell is known as "Scrap your Boilerplate" generic programming. See the papers or hackage for details, but it allows you to write code that processes arbitrary data structures and picks out values of given types.
A few other things that I saw of Fusion could probably be emulated using libraries such as HList or possibly fclabels. But it's really hard to say more without a look at what you actually need.
Peter Wortmann
- 2,272
- 14
- 14
-
Your `TypeMap` will work but requires an `unsafeCoerce` to convince the compiler that the type on the right side matches the `TypeRep` on the left (or `Data.Dynamic`). HList looks interesting as well; fclabels looks more like it provides zippers. I don't need reflection/data-generic programming over arbitrary data types, so I don't think SYB would help. – Jeremiah Willcock Nov 29 '11 at 18:22
-
Well, I wasn't sure whether or not you wanted the value in question to have its index type. If you want that, you probably either should use `HList` (if you know the keys of your map statically) or a similar map construction using `Dynamic` in the values to get around `unsafeCoerce`. – Peter Wortmann Nov 30 '11 at 14:58
1
-
No, since the elements need to have different types, and here the keys are types. I would like something that does a mapping like `(Int->5, Float->"foo")` in a value (not a type class that gives a global mapping). I know how to write it by hand (I think), but I was wondering if somebody did it already. – Jeremiah Willcock Nov 29 '11 at 17:15
-
@NathanHowell: Could you please post this as an answer? I'll check it out, but it looks from the documentation like it's what I'm asking for. – Jeremiah Willcock Nov 29 '11 at 17:31