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.

Beebeebe

Well a pattern can not contain references to functions, since a pattern contains patterns: a pattern is a composition of variables and constructors. – Inwrap

Haskell has this pattern feature where you can alias a data value, just like you would alias a type.https://mcmap.net/q/1158862/-aliases-for-value-constructors – Beebeebe

@TienHo I am confident that Willem knows about that feature, and encourage you to read his comment again carefully. Also generalize "references to functions" -- it also applies to non-function values. – Phipps

"this pattern feature where you can alias a data value" No, you can alias patterns. StoreEnv Map.empty is not a pattern. – Gaston

Ok, that makes sense. Thanks for that clarification about pattern synonym. So you cannot pattern match against maps like you would do with list then. Is there a way to alias an empty map? – Beebeebe

@TienHo (I suggest you ask that in a separate question but) you can use a view pattern along with PatternSynonyms's ability to give separate definitions for the pattern and the value constructor: pattern EmptyStore <- StoreEnv (null -> True) where EmptyStore = StoreEnv Map.empty. – Oreopithecus

Thank you so much. That works perfectly! – Beebeebe

@WillemVanOnsem, actually, this error suggests a theoretically possible extension to the pattern language. A qualified name in a pattern could be taken to mean a value that needs to be matched with ==. That would generalize the special rule for numeric literals. – Moina

@BenjaminHodgson The question has now been edited. (Personally, I'm OK with the edit -- before that, the question was too vague.) Now, your comment could be an answer. – Secondguess

@Secondguess cool, thanks for the heads up. I'll write something up – Oreopithecus

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!

Oreopithecus

The last idea, patterns with input and output arguments, is similar to some tricks that can be played with Scala's extractor object / classes. It is indeed a bit weird :) – Secondguess

Thank you for this thorough answer! What I'm doing right now is just to create a wrapper function for Map.empty for my data type – Beebeebe

@TienHo So just use a function, not a pattern synonym: empty = StoreEnv Map.empty – Oreopithecus

I have one more question. As you mentioned in your post, pattern synonyms are useful for pattern matching on the left of an equation. Then what would be the standard approach to alias a value used on the right hand side? This value is more like a result than a matching pattern I guess. For instance, get _ = Foo 0, and I want to provide a convenient name for Foo 0 such as Empty. – Beebeebe

@TienHo The way to do that is as I suggested above. Define a top level constant fooZero = Foo 0. – Oreopithecus