Haskell: "Qualified name in binding position" error with Map.empty

Question

I'm trying to create a pattern synonym for a newtype with an empty map.

{-# Language PatternSynonyms #-}

import qualified Data.Map as Map

newtype StoreEnv = StoreEnv (Map.Map Int String)
   deriving (Eq, Show)

pattern EmptyStore :: StoreEnv
pattern EmptyStore = StoreEnv Map.empty

I got an error saying "Qualified name in binding position: Map.empty" when compiling this. I believe that "Map.empty" should belong to the type "Map.Map Int String" that I declare in the newtype.

My question is whether there is a way to alias an empty map correctly.

I would appreciate any feedback.

Answer 1

Background

So you cannot pattern match against maps like you would do with list then.

That's right. Data.Map.Map is an abstract data type, meaning that its representation is hidden. In Haskell that means its constructors aren't exported. You can't write code which inspects the balanced binary search tree inside the Map (and you wouldn't want to anyway) - you have to go through its public interface, using the module's exported functions to create, query and manipulate Maps.

Pattern synonyms exist to bridge the gap between ADT programming and the convenient syntax of pattern matching on the left of an equation. You can define some smart patterns as part of your module's API without necessarily coupling the implementation of your ADT to those patterns.

Your problem

You're getting that error because syntactically the right-hand side of a pattern synonym has to be a pattern, not an expression. A pattern is (usually) the name of a value constructor applied to some variable binders - that is, in a definition like

getBar (Foo bar baz) = bar

the bar and baz on the left-hand side define variables which will be in scope on the right. They are fresh bindings, not references to any bar or baz variables which may exist in some outer scope.

So I think that as well as the syntactic mistake (Map.empty is not a valid name for a local variable, which is why you're getting that error) you've also made a logical one - you wouldn't have been able to refer to Map.empty in that position anyway.

The fix

As I suggested in my comment, you can patch up your code by using an explicitly bidirectional pattern synonym. This is a neat feature which lets you give a pattern synonym a different meaning depending on whether it's being used as a pattern (ie in pattern context) or as a value constructor (ie in expression context).

pattern EmptyStore <- StoreEnv (Map.null -> True)
    where EmptyStore = StoreEnv Map.empty

In the first line I'm defining what EmptyStore means when used as a pattern. The Map.null -> True syntax is called a view pattern - it means "apply the function Map.null to this piece of the pattern, and match its result with True". So EmptyStore matches a StoreEnv when the Map inside the StoreEnv is empty.

The second line defines what EmptyStore does when used as an expression. It says that the expression EmptyStore is a synonym for the expression StoreEnv Map.empty - "create an empty Map and wrap it in a StoreEnv".

The un-fix

However I submit that a pattern synonym API for Map doesn't really make sense. To be usable you should really define a complete set of patterns, so that users have a way to deconstruct any type of Map. The empty case is easy to handle, because there's only one empty Map, but what does it mean to pattern match on a non-empty Map? Maps aren't meant to be ordered containers - there's no "first-and-rest" like there is with [], so this doesn't make sense:

pattern Cons k v rest <- {- what goes here? -}
    where Cons k v rest = insert k v rest

You might instead try to define a pattern which matches when a particular key is present in the map:

pattern Contains k v <- (lookup k -> Just v)

but this is not valid Haskell (k is being referred to, when it should be being bound). Even if you could come up with a clever way to express it, such a set of patterns would necessarily be incomplete because you can't write clauses for every possible key.

In other words, I don't think you should be trying to define pattern synonyms for this datatype. Stick with ordinary functions!