Thursday, April 03, 2014

A small Haskell extension

The extension

In Haskell you can give a type to an expression by writing expr ::  type.  To an untrained eye the :: looks just like an infix operator, even if it is described as a special syntactical construct in the Haskell report.  But let's think about it as an infix operator for a moment.

For an infix operator you you can for a section, i.e., a use of the operator with one operand left out.  For instance (* 2) leaves out the first operand, and Haskell defines this to be the same as (\ x -> x * 2).  Regarding :: as an operator we should be able to write (:: type) and it should have the obvious meaning (\ x -> x :: type).

I suggest, and I plan sending the haskell-prime mailing list, Haskell should adopt this small extension.

Why?

First, the extension is very light weight and has almost no extra intellectual weight for anyone learning Haskell.  I'd argue it makes the language simpler because it allows :: to be treated more like an infix operator.  But without use cases this would probably not be enough of an argument.

Example 1

We want to make a function, canonDouble, that takes a string representing a Double and changes it to the standard Haskell string representing this Double.  E.g. canonDouble "0.1e1" == "1.0".  A first attempt might look like this:

  canonDouble :: String -> String
  canonDouble = show . read         -- WRONG!

This is, of course, wrong since the compiler cannot guess that the type between read and show should be a Double.  We can convey this type information in different ways, e.g.:

  canonDouble :: String -> String
  canonDouble = show . asDouble . read
    where asDouble :: Double -> Double
          asDouble x = x

This is somewhat clumsy.  Using my proposed extension we can instead write:

  canonDouble :: String -> String
  canonDouble = show . (:: Double) . read

This has the obvious meaning, and succinctly describes what we want.

Example 2

In ghc 7.8 there is a new, better implementation of Data.Typeable.  It used to be (before ghc 7.8) that to get a TypeRep for some type you would have to have a value of that type.  E.g., typeOf True gives the TypeRep for the Bool type.  If we don't have a value handy of the type, then we will have to make one, e.g., by using undefined.  So we could write typeOf (undefined :: Bool).

This way of using undefined is rather ugly, and relies on non-strictness to work.  Ghc 7.8 add a new, cleaner way of doing it.

  typeRep :: proxy a -> TypeRep

The typeRep function does not need an actual value, but just a proxy for the value.  A common proxy is the Proxy type from Data.Proxy:

  data Proxy a = Proxy

Using this type we can now get the TypeRep of a Bool by writing typeRep (Proxy :: Proxy Bool).  Note that in the type signature of typeRep the proxy is a type variable.  This means we can use other values as proxies, e.g., typeRep ([] :: [Bool]).

We can in fact use anything as a proxy that has a structure that unifies with proxy a.  For instance, if we want a proxy for the type T we could use T -> T, which is the same as (->) T T.  The (->) T part makes of it is the proxy and the last T makes up the a.

The extension I propose provides an easy way to write a function of type T -> T, just write (:: T).  So to get a TypeRep for Bool we can simply write typeRep (:: Bool).  Doesn't that look (deceptively) simple?

In fact, my driving force for coming up with this language extension was to get an easy and natural way to write type proxies, and I think using (:: T) for a type proxy is a as easy and natural as it gets (even if the reason it works is rather peculiar).

Implementation

I've implemented the extension in one Haskell compiler and it was very easy to add and it works as expected.  Since it was so easy, I'll implement it for ghc as well, and the ghc maintainers can decide if the want to merge it.  I suggest this new feature is available using the language extension name SignatureSections.

Extensions

Does it make sense to do a left section of ::?  I.e., does (expr ::) make sense?  In current Haskell that does not make sense, since it would be an expression that lacks an argument that is a type.  Haskell doesn't currently allow explicit type arguments, but if it ever will this could be considered.

With the definition that (:: T) is the same as (\ x -> x :: T) any use of quantified or qualified types as T will give a type error.  E.g., (:: [a]), which is (\ x -> x :: [a],  is a type error.  You could imagine a different desugaring of (:: T), namely (id :: T -> T).  Now (:: [a]) desugars to (id :: [a] -> [a]) which is type correct.  In general, we have to keep quantifiers and qualifiers at the top, i.e., (:: forall a . a) turns into (id :: forall a . a -> a).

Personally, I'm not convinced this more complex desugaring is worth the extra effort.

Labels:

5 Comments:

Blogger J. Maessen said...

I like this. The show . read example sprang immediately to mind, as did the question about polymorphism. Do you imagine that something like scoped type variables would permit the use of type variables within a signature, since those variables would be locally monomorphic?

Friday, April 4, 2014 at 1:13:00 PM GMT+1  
Blogger augustss said...

Scoped type variables are definitely allowed.

Friday, April 4, 2014 at 2:33:00 PM GMT+1  
Blogger Sean Leather said...

You start describing :: as a potential infix operator, but, in the end, you restrict the feature to a section. So, you're not really suggesting that :: be an infix operator in general, right? It might be a good idea, but I suspect it would break a lot of code (unless you add another precedence level just for it).

The succinctness of (:: Double) is attractive, but the implicit (\x -> x :: Double) is unintuitive (at first blush) because it means the signature section really means Double -> Double. In an annotation (using : for typing ::),

:: : (e : expr) -> (t : type) -> (e : t)

but in a section

:: : (e : expr) -> (t : type) -> (e : t -> t)

So, basically, the signature section becomes a better asTypeOf. The overloading of :: just bothers me a bit.

Sunday, April 6, 2014 at 10:57:00 AM GMT+1  
Blogger augustss said...

All I meant was that :: looks like an operator, and taking a right section of it behaves like any other operator. I.e. (op a) means (\ x -> x op a), this holds for + as well as ::. I don't see what's unintuitive about that. All operator sections represent functions, so of course a :: section also represents a function.

Sunday, April 6, 2014 at 7:21:00 PM GMT+1  
Blogger Sean Leather said...

On second thought, I think my (approximation of the) typing of :: was wrong. This might be more accurate (where {x} means an implicit x):

:: : {e : expr} -> {t : type} -> (e : t) -> t -> (e : t)

In that respect, the :: section makes sense. Sorry for the temporary confusion.

Sunday, April 6, 2014 at 7:40:00 PM GMT+1  

Post a Comment

<< Home