Is Pattern Matching as expressive as Case Expression in Haskell?
The expression

case e of
  p1 -&gt; e1
  p2 -&gt; e2
  ...


can be rewritten as

let k p1 = e1
    k p2 = e2
    ...
 in k e


where k is a fresh identifier.

This translation assumes that the language has some way to define a local function by pattern matching (e.g. let).



If local functions can not be defined, there's always the possibility of lifting the definition to the top level. Indeed, any local definition

let f x1 ... xk = e in e'


having free variables v1 .. vn can be rewritten written as

(\f -&gt; e') (globalF v1 ... vn)


provided that we also define a global function

globalF v1 ... vn x1 ... xk = e


Note that globalF has no free variables, by construction. I believe it is sometimes called a "supercombinator".

This naturally extends to the case where x1 ... xk are patterns, and we have multiple defining equations for f / globalF.



For example,

case x of True  -&gt; False
          False -&gt; True


cab be rewritten as

let f True  = False
    f False = True
 in f x