Opened 3 years ago

Closed 3 months ago

Last modified 3 months ago

#5144 closed feature request (fixed)

Pattern synonyms

Reported by: simonpj Owned by: cactus
Priority: normal Milestone: 7.8.1
Component: Compiler Version:
Keywords: Cc: lennart.augustsson@…, illissius@…, bgamari@…, cgibbard@…, gergo@…, tkn.akio@…, hvr@…, maoe@…, hackage.haskell.org@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: Blocked By:
Blocking: #8581, #8582, #8583, #8584 Related Tickets:

Description

Lennart would like pattern synonyms. Something like

pattern con var1 … varN = pat

where ‘pattern` is a new keyword.

  • Perhaps there should be a way to give a type as well, so the con could be (con :: type).
  • The rhs is type checked as a usual pattern, i.e., in the global environment.
  • The pat should bind exactly var1 .. varN.
  • Recursive pattern synonyms are not allowed.

With con in scope it can be used like any other constructor in a pattern, and the semantics is simply by expansion.

It would have been very nice if con could be used in expressions as well, but I don’t see how that could work with view patterns.
Perhaps view patterns could be extended to make them bidirectional.

My rationale for wanting pattern synonyms is that I sometimes have pattern matching with a lot of complex repetition in them.
I’ve even resorted to using CPP in the past, and that just shows that Haskell is lacking some abstraction mechanism.

If pattern synonyms could be made to work in the presence of view pattern it would offer a mechanism for normal pattern matching on abstract types, since the abstract type could export some pattern synonyms and you’d not be able to tell of those were real constructors or not.

I’ve not tried implementing this, but I think SHE has something like it.

Change History (48)

comment:1 Changed 3 years ago by simonmar

Conor has lobbied for adding these, and I'd like them too. Allowing pattern matching on abstract types would be a killer feature.

comment:2 Changed 3 years ago by simonmar

I've been thinking about how to design this extension to get the most
bang for the buck. Here's a slightly different proposal that I think
has some nice properties, and is still quite simple.

Pattern synonyms define new varids rather than conids.
For example, we could add this to Data.Sequence:

pattern empty    = t | Nothing2 <- viewLTree t
pattern x  <| xs = t | Just (x,xs) <- viewLTree t
pattern xs |> x  = t | Just (x,xs) <- viewRTree t

which would subsume all the existing ViewL/ViewR stuff. Note that
the pattern right hand side may include a pattern guard (or view
patterns).

The big win here is that you can use the same varid as an existing
function function, so you get to define both constructors and
destructors, and they look identical. Furthermore you get pattern
matching (view-style) on abstract types.

You could do this with conids instead of varids if there was also some
way to define the expression form - that's the tricky part, which is
why I thought varids would be a better choice. Also varid patterns
give you a clue that something magic is going on, but in a nicer way
than view patterns.

Not many changes to Haddock etc. would be required (I think if we used
conids it would be a bit trickier: should they be indistinguishable
from ordinary datatypes or not?)

A design question is whether the pattern should be required to have
the same type as the function, if both exist. There could be all
sorts of hairy issues there. If they aren't the same, can you give a
type signature to a pattern?

This extension to pattern synonyms covers all the use cases of view
patterns in which there is a single identifier to the left of the
arrow (which is about 90% of the examples in ViewPatterns). Perhaps
there's some way to extend this to allow passing arguments from the
pattern site too... it's just a syntax question (but a gnarly one). So while with view
patterns you can define an n+k pattern, with pattern synonyms it has
to be restricted to a particular k:

pattern oneplus n = m | m > 0, let n = m - 1

f 0           = ...
f (oneplus n) = ...

I do think for the cases where pattern synonyms apply, the syntax is
much nicer than view patterns. In particular, there's no need for
intermediate Maybes or tuples, which the view pattern proposal
suggests to make implicit.

Another one:

pattern x `and` y = it | x <- it, y <- it

(this was called both in ViewPatterns).

In conclusion: I'm not sure whether this is the right thing, but from
certain angles it looks very attractive. Thoughts?

comment:3 follow-up: Changed 3 years ago by igloo

I'm not sure I follow exactly what you're proposing. What does

pattern x `and` y = it | x <- it, y <- it

mean exactly? And how would you use it? Could you use it to require an argument matches both (Just x, _) and (_, True), or am I on completely the wrong track?

comment:4 in reply to: ↑ 3 Changed 3 years ago by simonmar

Replying to igloo:

Lennart is going to put up a wiki page describing the proposed extension soon, and we plan to work on it at CamHac?.

comment:5 Changed 3 years ago by Lennart

comment:6 Changed 2 years ago by illissius

  • Cc illissius@… added

It occurs to me that for great symmetry you could call these data synonyms (data synonyms : data constructors :: type synonyms : type constructors). Unfortunately the 'data' keyword is taken.. :-)

comment:7 Changed 18 months ago by bgamari

  • Cc bgamari@… added
  • Type changed from bug to feature request
  • Version 7.0.3 deleted

Any news on this? It would be very nice to have these.

comment:8 Changed 18 months ago by cgibbard

  • Cc cgibbard@… added

comment:9 Changed 18 months ago by simonpj

  • Difficulty set to Unknown

I'm afraid not. I'm deep under water with other stuff (including GHC stuff), and this feature is relatively ambitious, both on the design side and implementation. It might make a good intern project!

Simon

comment:10 follow-up: Changed 9 months ago by cactus

I've started working on this, and I have the simplest case (pattern-only synonyms) almost working, with most of the groundwork done for simple bidirectional pattern synonyms as well.

What's the correct protocol in this case? Should I mark myself as the owner on this ticket until I have my patches ready for submission for review? Or only after an initial working version is accepted?

comment:11 Changed 9 months ago by cactus

  • Cc gergo@… added

comment:12 in reply to: ↑ 10 Changed 9 months ago by simonmar

Replying to cactus:

Great to hear that you're working on this! Just out of interest, are you implementing ViewPatternsAlternative too? Pattern synonyms become rather powerful when you can use pattern guards inside them, which is what ViewPatternsAlternative lets you do.

What's the correct protocol in this case? Should I mark myself as the owner on this ticket until I have my patches ready for submission for review? Or only after an initial working version is accepted?

You can assign the ticket to yourself if you're working on it, yes.

comment:13 Changed 9 months ago by cactus

  • Owner set to cactus

comment:14 Changed 8 months ago by akio

  • Cc tkn.akio@… added

comment:15 Changed 8 months ago by cactus

Progress update:

Code is in the pattern-synonyms branch at https://github.com/gergoerdi/ghc.git Until I am ready to submit for initial review, I will do all kinds of funky rebasing and history rewriting, so use it for read-only snapshots as of now.

Using the names from the wiki link, pattern-only pattern synonyms and simple pattern synonyms now (mostly) work. There's a bug in the typing of pattern-synonyms-as-expressions, so e.g. with the following program:

{-# LANGUAGE PatternSynonyms #-}
pattern One x = [x]

singleton :: a -> [a]
singleton x = One x

I get an error that the type of One is too rigid; I expect this to be easy to fix:

    Couldn't match type ‛t0’ with ‛a’
      because type variable ‛a’ would escape its scope
    This (rigid, skolem) type variable is bound by
      the type signature for singleton :: a -> [a]
      at /tmp/PatSyn.hs:18:14-21
    Expected type: [a]
      Actual type: [t0]

The one big missing feature is exporting pattern synonyms. First of all, since pattern synonyms are in the namespace of constructors, not types, we need special syntax to export them; I propose the following:

module M (pattern P) where

pattern P x = _:_:x:_

(note that you can have a type called P as well, but you'd get a clash if you had a constructor with that name).

To be honest, I have no idea yet how to actually implement exporting, since I haven't looked at that part of GHC yet -- any pointers are appreciated.

After I've fixed the bug mentioned and implemented exporting, I'll do a formal submission of my (clean-up) patch for review.

After that baseline, the 'bidirectional pattern synonyms' proposal from the wiki page should fit right into it as well. I have no opinion yet how difficult adding associated patsyns will be, I'll need to do more research first.

comment:16 Changed 8 months ago by cactus

Progress update: the following module demonstrates all the features implemented so far:

{-# LANGUAGE PatternSynonyms #-}
module PatSyn where

-- The example from the wiki page
data Type = App String [Type] deriving Show
pattern Arrow t1 t2 = App "->" [t1, t2]
pattern Int = App "Int" []

collectArgs :: Type -> [Type]
collectArgs (Arrow t1 t2) = t1 : collectArgs t2
collectArgs _ = []

isInt Int = True
isInt _ = False

arrows :: [Type] -> Type -> Type
arrows = flip $ foldr Arrow

-- Simple pattern synonyms
pattern Nil = []
pattern Cons x xs = x:xs

zip' :: [a] -> [b] -> [(a, b)]
zip' (Cons x xs) (Cons y ys) = Cons (x, y) (zip' xs ys)
zip' Nil         _           = Nil
zip' _           Nil         = Nil

pattern One x = [x]

one :: [a] -> Maybe a
one (One x) = Just x
one _ = Nothing

singleton :: a -> [a]
singleton x = One x

-- Pattern only synonyms
pattern Third x = _:_:x:_

third :: [a] -> Maybe a
third (Third x) = Just x
third _         = Nothing

-- This causes a type error:
invalid x = Third x

-- PatSyn.hs:30:13:
--     Third used in an expression, but it's a non-bidirectional pattern synonym
--     In the expression: Third x
--     In an equation for ‛invalid’: invalid x = Third x
-- Failed, modules loaded: none.

The following module also works, but demonstrates the clunkiness caused by the lack of infix pattern synonyms:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}
import qualified Data.Sequence as Seq

pattern Empty = (Seq.viewl -> Seq.EmptyL)
pattern Cons x xs = (Seq.viewl -> x Seq.:< xs)
pattern Snoc xs x = (Seq.viewr -> xs Seq.:> x)

zipZag :: Seq.Seq a -> Seq.Seq b -> Seq.Seq (a, b)
zipZag (Cons x xs) (Snoc ys y) = (x, y) Seq.<| zipZag xs ys
zipZag _           _           = Seq.empty

Of course, implementing infix pattern synonyms should be easy.

Still missing: exporting of pattern synonyms.

comment:17 Changed 8 months ago by hvr

  • Cc hvr@… added

comment:18 Changed 8 months ago by cactus

I've implemented infix notation as well, so now you can write this:

{-# LANGUAGE ViewPatterns, PatternSynonyms #-}
import qualified Data.Sequence as Seq

pattern Empty = (Seq.viewl -> Seq.EmptyL)
pattern x :< xs = (Seq.viewl -> x Seq.:< xs)
pattern xs :> x = (Seq.viewr -> xs Seq.:> x)

zipZag :: Seq.Seq a -> Seq.Seq b -> Seq.Seq (a, b)
zipZag (x :< xs) (ys :> y) = (x, y) Seq.<| zipZag xs ys
zipZag _         _         = Seq.empty

comment:19 Changed 8 months ago by illissius

Fabulous! Köszönöm!

Deplorable syntax bikeshedding:

Perhaps, instead of pattern, data alias? I feel that would be more accurate and descriptive for many cases (when the synonym can also be used on the RHS), though possibly less so for others (pattern-only synonyms). It might also avoid having to reserve a keyword. (As with TypeFamilies, as far as I can tell, "family" is not a keyword. I don't think it's possible to avoid the keyword with a new top-level entity like pattern, but maybe I'm mistaken?)

comment:20 Changed 8 months ago by cactus

Exports now work with the following syntax:

module Foo (pattern P) where

pattern P x y = (x, y, 42)

This exports P both as a pattern and as an expression (if it's bidirectional, like in the case here)

The extra pattern keyword is needed because pattern names live in the constructor namespace, so it's perfectly valid to have

data P  = C
pattern P = ()

(due to entirely non-interesting reasons, the implementation of exporting is not yet pushed to https://github.com/gergoerdi/ghc/tree/pattern-synonyms)

Remaining work to do:

  • Sort out recursive pattern definitions. Currently these are rejected implicitly by an internal GHC error, not exactly ideal... also, non-recursive usages of pattern synonyms mentioning each other don't work, but I see no reason why we wouldn't want to allow it:
pattern P1 = P2
pattern P2 = ()
  • The typechecker for pattern synonym definitions is wrong: it returns monomorphic types (e.g. for pattern Head x = x:_, it infers type t -> [t] instead of forall a. a -> [a]. This is worked around by a horrible hack when typechecking pattern synonym usages in patterns. Richard Eisenberg and Simon Peyton Jones have already offered to help with this.

comment:21 Changed 8 months ago by simonmar

We need to think about the import/export situation. One of the goals of pattern synonyms is to abstract constructors, so that a library can change a data type representation while allowing clients to continue to use pattern matching. Clearly we can't use the T(P1,P2,..) syntax for exporting patterns (what is T?), but perhaps we can use the pattern syntax for exporting constructors. I haven't thought about this very hard.

When a pattern is imported, can it be used in an expression? Does the client know whether it can be used in an expression or not?

What do the Haddock docs for pattern synonyms look like?

comment:22 Changed 8 months ago by cactus

If your question is whether there's a syntactic way to see if a given pattern synonym import can be used as an expression, then no, not at the moment. So if you do something like

import M(pattern P)

x = P

then the only error you will get if P is not bidirectional is from the type checker:

/tmp/hs/M2.hs:5:5:
    P used in an expression, but it's a non-bidirectional pattern synonym
    In the expression: P
    In an equation for ‛x’: x = P

comment:23 follow-up: Changed 8 months ago by simonpj

We must treat data constructors uniformly with pattern synonyms. For example, it should definitely be OK to have

module M( pattern P, foo, bar ) where
  -- The "pattern P" exports data constructor P

   data T = P | Q

   foo :: T
   foo = P

   bar :: T -> Int
   bar P = 1
   bar Q = 2

module A where
import M
-- T is not in scope
w1 = bar P   -- Uses P as an expression
w2 = case foo of
       P -> 1   -- Uses P as a pattern

We have at various times discussed how to allow a module to export a data constructor that can be used as a pattern but not as a constructor (in expressions), because the data type is abstract and you should only use a smart constructor. With pattern synonyms you can (almost) do that:

module M( T, pattern AbsP, pattern Q ) where
  data T = P Int | Q
  pattern AbsP = P

But I really wanted AbsP to be uni-directional and according to the current spec PatternSynonyms it is "implicitly bidirectional". I suggest we allow the user to control whether a pattern synonym is bidirectional or not. I'm not sure what syntax to use for that. We want to be able to say

  • Uni-directional pattern synonym
  • Bi-directional pattern synonym
  • Bi-directional pattern synonym with explicit user code for the reverse direction

comment:24 follow-up: Changed 8 months ago by igloo

I haven't followed the design, but I would expect exporting "pattern P" to either be an error ("P is a data constructor, not a pattern") or to export P in a way that allows it only to be used as a pattern, not an expression.

comment:25 in reply to: ↑ 23 ; follow-up: Changed 8 months ago by cactus

Replying to simonpj:

I suggest we allow the user to control whether a pattern synonym is bidirectional or not. I'm not sure what syntax to use for that. We want to be able to say

  • Uni-directional pattern synonym
  • Bi-directional pattern synonym
  • Bi-directional pattern synonym with explicit user code for the reverse direction

Once a syntax for this is decided, this is trivial to add to my current implementation.

We have at various times discussed how to allow a module to export a data constructor that can be used as a pattern but not as a constructor (in expressions), because the data type is abstract and you should only use a smart constructor. With pattern synonyms you can (almost) do that

What if you could just export pattern P (where P is the name of the data constructor) without having to define AbsP? Would that be taking things too far?

Last edited 8 months ago by cactus (previous) (diff)

comment:26 in reply to: ↑ 24 Changed 8 months ago by simonpj

Replying to igloo:

I haven't followed the design, but I would expect exporting "pattern P" to either be an error ("P is a data constructor, not a pattern") or to export P in a way that allows it only to be used as a pattern, not an expression.

Well in the design here PatternSynonyms, pattern P exports P for use both in patterns and expressions. By all means suggest alternative designs; that's what this thread is all about.

comment:27 in reply to: ↑ 25 Changed 8 months ago by simonpj

Replying to cactus:

We have at various times discussed how to allow a module to export a data constructor that can be used as a pattern but not as a constructor (in expressions), because the data type is abstract and you should only use a smart constructor. With pattern synonyms you can (almost) do that

What if you could just export pattern P (where P is the name of the data constructor) without having to define AbsP? Would that be taking things too far?

That would treat pattern synonyms and data constructors differently, which I am keen to avoid. Under what you propose:

  • If P is a data constructor then pattern P would export P uni-directionally (pattern only)
  • If P is a (bi-directonal) pattern synonym then pattern P would export P bi-directionally.

I don't like that... a data constructor is precisely a (degenerate) bidirectional pattern.

I suppose you could put the directionality in the export list:

module M(
  pattern P,    -- Uni-directional
  constructor Q   -- Bidirectional
 ) where

pattern P x = [x]
pattern Q y = [y,y]

But I don't want to go this way. If you export P you get all of what P is. Otherwise we'll get into exporting it unidirectionally from one module, bidirectionally from another, then importing both of those, and combining the directinoality of those imports. Too complicated.

Maybe datacon P, or view P, rather than pattern P would address Ian's worry?

comment:28 Changed 8 months ago by igloo

Ah, I see, I had expected that something defined with "pattern" (e.g. pattern Arrow t1 t2 = App "->" [t1, t2]) could only be used as a pattern. I think a different keyword, e.g. "synonym" (or perhaps "view", as Simon suggested) would be better in that case.

comment:29 Changed 8 months ago by cactus

I realize I was wrong on my last comment: let's not even discuss exporting data constructors as pattern-only here, otherwise this ticket will lose focus.

So let's just come up with some syntax to discern unidirectional vs. bidirectional pattern synonym definitions.

comment:30 Changed 8 months ago by cactus

Interestingly, Lennart's initial proposal (http://ghc.haskell.org/trac/ghc/wiki/PatternSynonyms?version=2) already used different notation for pattern-only synonyms:

pattern Conid varid1 ... varidn ~ pat

How about using this syntax?

Last edited 8 months ago by cactus (previous) (diff)

comment:31 Changed 8 months ago by maoe

  • Cc maoe@… added

comment:32 Changed 8 months ago by liyang

  • Cc hackage.haskell.org@… added

comment:33 Changed 7 months ago by cactus

Based on discussions with SPJ, I've updated the PatternSynonyms proposal and redesigned the implementation to postpone the instantiation of pattern synonyms until the desugarer. See the updated implementation at https://github.com/gergoerdi/ghc/tree/pattern-synonyms

Basically, the old implementation was pretty much unsalvageable for patterns mentioning non-Haskell98 data constructors. The new one works nicely with unconstrained and constrained existential types.

On the features front, I've added explicit syntax for unidirectional vs. bidirectional patterns. The tentative syntax is:

pattern Head x -> (x:_) -- pattern-only synonym
pattern Single x = [x] -- bidirectional synonym

So now you can rewrite the second one as

pattern Single x -> [x]

and it will not introduce a new virtual constructor to be used in expressions.

comment:34 Changed 6 months ago by cactus

Added PatternSynonyms/Implementation page describing internals of the code

comment:35 Changed 5 months ago by cactus

  • Blocking 8581 added

comment:36 Changed 5 months ago by cactus

  • Blocking 8582 added

comment:37 Changed 5 months ago by cactus

  • Blocking 8583 added

comment:38 Changed 5 months ago by cactus

  • Blocking 8584 added

comment:39 Changed 5 months ago by cactus

I've added separate tickets to the features from the PatternSynonyms page that are not going to be implemented in the initial version (which is now code-complete and just needs some docs and some comments here and there).

comment:40 Changed 4 months ago by cactus

I've added test cases to the pattern-synonym branch of https://github.com/gergoerdi/ghc-testsuite.git

comment:41 Changed 3 months ago by cactus

  • Milestone changed from _|_ to 7.8.1
  • Status changed from new to patch

Code is now past initial review and is ready in the wip/pattern-synonyms branch on the GHC Git repo.

comment:42 Changed 3 months ago by thoughtpolice

  • Resolution set to fixed
  • Status changed from patch to closed

This is now merged.

comment:43 Changed 3 months ago by monoidal

Reminder: we still need documentation and release notes entry.

comment:44 Changed 3 months ago by cactus

What documentation is needed beside the new section in docs/users_guide/glasgow_exts? Also, can you point me in the direction of the release notes? I'd like to add a note not just mentioning pattern synonyms but also explaining that it is a preview that will need feedback from actual usage and which has more features planned.

comment:45 Changed 3 months ago by monoidal

Just a section in docs/users_guide/glasgow_exts should be enough. Release notes are in docs/users_guide/7.8.1-notes.xml; Austin added the entry for pattern synonyms, you might expand it.

comment:46 Changed 3 months ago by cactus

OK, will fix 7.8.1-notes.xml. Just to avoid any misunderstandings, I've already added a section to glasgow_exts.xml.

comment:47 Changed 3 months ago by thoughtpolice

Thanks Gergo!

comment:48 Changed 3 months ago by cactus

The source of the confusion over the docs was that I forgot to push my commit that added the section to glasgow_exts. Now I've pushed a commit that adds both that and cleans up the release notes.

Note: See TracTickets for help on using tickets.