[Learning Mode] Discussion: building up to Pattern Matching

[kytrinyx]

@MatthijsBlom suggested the following concept graph, which is a good starting point for building up to a basic understanding of proper pattern matching in Haskell.

              |
   Simple Pattern Matching      
   /          |        \
Maybe      Either      ... (tuples, lists?)
   \          |        /
    Algebraic Data Types
      ("custom types")
              |
   Pattern Matching Proper
              |

I'd like to start the discussion by looking at some sample code that demonstrates the end point, Pattern Matching Proper. It doesn't have to relate to any exercise or story, rather it's a way to make sure that everyone involved understands where we're trying to get to.

@MatthijsBlom I know you've been thinking a lot about this over the past couple of weeks. Would you be willing to write a few (maybe 10 or so?) lines of code to illustrate Pattern Matching?

[MatthijsBlom]

The solution to Valentine's is feature-complete, so to speak. It matches on a custom ADT (Activity), matches on fields (e.g. Korean), uses binding patterns (not sure this is the right terminology) (kilometers), and it uses guards. All this is very normal Haskell.

Here are a few variations of a translation of the F# exemplar solution. (The variation is in syntax alone.)

Show code

{-# LANGUAGE LambdaCase #-}
-- The above enables a well-established language extension

module ValentinesDay (rateActivity) where

data Approval = Yes | No | Maybe

data Cuisine = Korean | Turkish

data Genre = Crime | Horror | Romance | Thriller

data Activity = BoardGame | Chill | Movie Genre | Restaurant Cuisine | Walk Integer

-- How I would write it, but requires LambdaCase extension
rateActivity :: Activity -> Approval
rateActivity = \case
  Restaurant Korean -> Yes
  Restaurant Turkish -> Maybe
  Movie Romance -> Yes
  Walk kilometers
    | kilometers < 3 -> Yes
    | kilometers < 5 -> Maybe
  _ -> No

-- Without LambdaCase
rateActivity' :: Activity -> Approval
rateActivity' activity =
  case activity of
    Restaurant Korean -> Yes
    Restaurant Turkish -> Maybe
    Movie Romance -> Yes
    Walk kilometers
      | kilometers < 3 -> Yes
      | kilometers < 5 -> Maybe
    _ -> No

-- Using function definition syntactic sugar
rateActivity'' :: Activity -> Approval
rateActivity'' (Restaurant Korean) = Yes
rateActivity'' (Restaurant Turkish) = Maybe
rateActivity'' (Movie Romance) = Yes
rateActivity'' (Walk kilometers)
  | kilometers < 3 = Yes
  | kilometers < 5 = Maybe
rateActivity'' _ = No

[kytrinyx]

This is really nice.

My gut feeling is that the middle solution is just right at this point in the concept tree.

I do like the clean approach of the first one, but I think that we should probably wait to introduce language extensions. Similarly I think it's worth deferring the function definition syntactic sugar until later in the concept tree.

[MatthijsBlom]

My gut feeling is that the middle solution is just right at this point in the concept tree.

I agree. The third one is not any more complicated (depending on their introduction to the language, a beginner might even find it simpler), but it is noisier.

I think that we should probably wait to introduce language extensions

While I agree on this, a warning: the language extensions are very diverse, and so are their appropriateness, need, and difficulty level. Intuitions from other languages about them do not necessarily transfer. To paraphrase Alexis King: the question is less «is introducing language extensions a good idea?» and more «is using this language extension a good idea?».

I think it's worth deferring the function definition syntactic sugar until later in the concept tree.

Many Haskell tutorials start out with the sweet version and introduce case expressions only later. (Case in point: LYAH has them at the bottom of the page on pattern matching.)

I think it's safe to introduce them together. Wouldn't know when to do it otherwise either: PM2 is already kinda heavy, and I do not feel like this syntactic sugar deserves its own concept node.

[kytrinyx]

The third one is not any more complicated [...] but it is noisier.

Yes, that's my sense, exactly. The three actually feel really similar to me in terms of difficulty, but I think the middle example strikes a good balance.

To paraphrase Alexis King: the question is less «is introducing language extensions a good idea?» and more «is using this language extension a good idea?».

Yepp, that makes sense.

Cool. So, if @ErikSchierboom also agrees that the middle example is the way to go, I think we'd be good to kick off work on the Valentine's Day exercise itself.

@MatthijsBlom Have you given any thought yet to how you'd introduce Algebraic Data Types?

[MatthijsBlom]

I think we'd be good to kick off work on the Valentine's Day exercise itself.

It looks like a straightforward translation of F#'s instructions.md would be good.

@MatthijsBlom Have you given any thought yet to how you'd introduce Algebraic Data Types?

Working on it right now. (On that whole graph section actually.)

[MatthijsBlom]

It occurs to me that Maybe, Either, tuples, … do not actually depend on Simple Pattern Matching.

[ErikSchierboom]

It occurs to me that Maybe, Either, tuples, … do not actually depend on Simple Pattern Matching.

So your saying you wouldn't use pattern matching when working with them?

[ErikSchierboom]

Cool. So, if @ErikSchierboom also agrees that the middle example is the way to go, I think we'd be good to kick off work on the Valentine's Day exercise itself.

I agree!

[ErikSchierboom]

The solution to Valentine's is feature-complete, so to speak. It matches on a custom ADT (Activity), matches on fields (e.g. Korean), uses binding patterns (not sure this is the right terminology) (kilometers), and it uses guards. All this is very normal Haskell.

Which of these concepts will be prerequisites and which of these concepts will be newly introduced concepts?

[kytrinyx]

@MatthijsBlom Do you have some snippets of code as starting points for discussion for some of the earlier concepts in the graph here (First Maybe, Either, ADTs, but also any of the "etc" concepts that you have on the right hand side as well, if you've been thinking about that).

[MatthijsBlom]

So your saying you wouldn't use pattern matching when working with them?

I would regularly, but a beginner need not immediately. The utility functions in their respective modules are sufficient for everything, if in a slightly different way. Seems fine practice in composing functions.

...But that's not really what that was about: Maybe, Either, and (,) will not be matched against until Pattern Matching Proper. Everything else about them does not depend on pattern matching on literals, which is what Simple Pattern Matching is about.

I tried to say that the graph might look like this instead:

   Simple Pattern Matching      
                   |    
Maybe      Either  |   ... (tuples, lists?)
   \          |    |   /
    Algebraic Data Types

Which of these concepts will be prerequisites and which of these concepts will be newly introduced concepts?

Guards are part of Simple Pattern Matching; the rest will be introduced in Pattern Matching Proper.

@MatthijsBlom Do you have some snippets of code as starting points for discussion for some of the earlier concepts in the graph

Not yet, but these are the kinds of signatures I'm thinking of:

• binarySearch :: Array -> Value -> Maybe Index
• compile :: Code -> Either CompileError Program

ADTs: the data type declarations in Valentine's Day contain most of this. The only thing that is really missing is polymorphism: data Maybe a = Nothing | Just a (the lowercase a, a type variable).

Tuples are plumbing, so I do not expect appealing code. However, the likes of zip :: [a] -> [b] -> [(a, b)] and lookup :: Eq a => a -> [(a, b)] -> Maybe b use them.

Looks like lists will get their own node early on. I haven't checked this, but I imagine that lots of material from other tracks on lists can be reused. (Expecially Purescript, Elm.)

[ErikSchierboom]

Do you have some snippets of code as starting points for discussion for some of the earlier concepts in the graph

As a quite rusty Haskell programmer, code samples would be great, yes. I must admit that things don't readily "click" in my mind currently, but I'm sure I'll get there. I think the code samples will be invaluable.

[MatthijsBlom]

This is taking way longer than expected, and @pwadsworth is being productive in my absence, so I tried to write down my thoughts here below.

Pattern Matching & Data Type Declarations

Here is an attempt at a somewhat thorough outline of things related to pattern matching and data types in Haskell. Explanations are omitted, as are obviously 'advanced' concepts like GADTs. Some such concepts however are included, simply because it was easier for me to include than to omit them.

Pattern Matching syntax

case expressions:

f x =
  case x of
    pattern -> expression

Function definition syntactic sugar (compiles to case)

f pattern = expression

Patterns

(Please disregard GitHub's broken highlighting of pattern.)

x = case someExpression of
  -- Wildcard pattern
  _ -> expression
  
  -- Binding pattern
  name -> expression

  -- Regular constructor pattern
  Constructor pat ter ns -> expression

  -- (Named) "as" pattern
  name@pattern -> expression

  -- Special syntax reused as pattern syntax
  5         -> expression  -- integers
  -3.7      -> expression  -- fractional numbers
  "Hello!"  -> expression  -- strings
  [x, y, z] -> expression  -- lists
  (x, y)    -> expression  -- tuples

  -- Bang pattern
  !pattern -> expression

  -- Irrefutable pattern
  ~pattern -> expression

  -- Guards
  pattern | booleanExpression      -> expression  -- boolean guard
          | pattern <- expression  -> expression  -- pattern guard
          | let name = expression  -> expression  -- local binding
          | guard, guard, guard    -> expression  -- sequence of guards

Data type declarations

-- "data declaration"
data TypeConstructor typeParameters =
    DataConstructor  fi El Ds
  | DataConstructor' Fi eld S

-- "newtype declaration"
newtype TypeConstructor typeParameters =
  DataConstructor Field

-- "type declaration"
type TypeConstructor typeParameters = someType

-- deriving clause
data T a b c = C a b c deriving (classes)
newtype N a b c = N a b c deriving (classes)

Of note:

• Otherwise synonymous with data, newtype declares un-lifted types.
• type does not provide type-safety. (To the contrary, in practice!)

Records

TBA

Right now I do not feel need to fill in this section. See below for reasoning.

Note: while they look as similar to each other as some other constructs shared between the languages, the records of Haskell and Elm are not to be confused: they are different beasts.

Examples of data types and how to work with them

• Sum types: Bool, Maybe, Either
• Product types: tuples ((,), (,,), etc.)
• Sum+product type: lists ([])

Each of these except Bool are parametric types, i.e. not themselves concrete types.

Maybe, [], (,), etc. are type constructors.

False, Just, [], (:), (,), etc. are data constructors

Note: sadly tuples and lists are not great examples, because their syntax is special on many levels (syntactic sugar + weird names of both type and data constructors).

Each of these types can be worked with, even without (explicit) pattern matching, using the utility functions available from dedicated standard library modules.

---

What to teach when

For reference the above list condensed

(Unordered)

• case expressions
• function definition syntactic sugar
• Wildcard patterns
• Binding patterns
• Regular constructor patterns
• (Named) "as" patterns 😢
• Special syntax reused as pattern syntax
• Bang patterns 🛑
• Irrefutable patterns 🛑
• boolean guards
• pattern guards 🛑
• local binding guards 🛑
• guard sequences 🛑
• data declarations
• type variables + parametric types
• type constructors
• data constructors
• newtype declarations 😢
• type declarations / type synonyms 😢
• deriving 😢
• All things records 🛑

I propose we do not teach

• Strictness-related stuff, i.e. bang patterns and irrefutable patterns. Not in the concept nodes introducing pattern matching, anyway. Strictness might deserve its own node (later).
• Records have historically been not nice to work with. An appreciable number of language extensions have been created to improve ergonomics. It would be a shame to introduce a student to records but not to at least some of the relevant extensions. But this would be too much to include in the nodes introducing data types and pattern matching. Therefore I say: if we do records, let's give them their own node. Records are just syntactic sugar; we do not really lose anything by skipping over them.
• All types of guards except boolean guards, as they are kinda obscure and we do not need them anyway.

I have marked these with 🛑 in the condensed list above.

In addition, I wouldn't be too sad if we skip

• "As" patterns as they are neither conceptually very interesting nor very common.
• newtype declarations as they are conceptually (almost) redundant. Seems cheap to include them though.
• type declarations / type synonyms as they are conceptually anti-interesting, not that common, and potentially confusing. Reasons to include them anyway: cheap, and the very common String is (very noticeably) a type synonym.
• deriving clauses because type classes have not been introduced yet. They are very common though, so it would be nice if we could at least say something about them.

I have marked these 😢 in the condensed list above.

Now, assuming the concept graph proposed earlier, …

Which graph? This one.

   Simple Pattern Matching      
                  |
 Maybe   Either   |   ... (tuples, lists?)     ("Example nodes")
    \      |      |    /
    Algebraic Data Types
      ("custom types")
              |
   Pattern Matching Proper

…I was thinking

Concept	Node
case expressions	Simple PM
Wildcard patterns	Simple PM
Special syntax reused as pattern syntax	Simple PM
function definition syntactic sugar	Simple PM or PM Proper1
Binding patterns	Simple PM or PM Proper2
boolean guards	Simple PM3 or PM Proper2
type variables + parametric types	example nodes + ADTs
data constructors	example nodes + ADTs
type constructors	example nodes + ADTs
data declarations	ADTs
newtype declarations	ADTs
type declarations / type synonyms	ADTs
deriving	ADTs
Regular constructor patterns	PM Proper
"As" patterns	PM Proper

---

I realize these ideas conflict with ongoing work. What do you think about the above, @pwadsworth?

If it helps, I can produce some design.mds. I think I finally understand why those exist; it wasn't obvious to me before.

Footnotes

1. Consider delaying introduction of function definition pattern matching syntactic sugar, because beginners often get stuck in the habit of using the sugar, whereas the first instinct should be to reach for case. ↩

2. One generally guards on bindings, so we should introduce binding patterns no later than we introduce guards. ↩ ↩²

3. Beginners often reach for series of (==) comparison guards instead of case. If introduction of guards is postponed, there is no danger of this: in more general settings (i.e. those in PM Proper), (==) guards fail to be applicable. ↩