1
$\begingroup$

Nomenclature

The term expressive in the question shall bear the same meaning as in the following sentence:

A Turing Machine is as expressive as Lambda Calculus.

Introduction

While learning Haskell, I had noticed that there are 2 ways to achieve the same effect, namely Pattern Matching and Case Expression. For example,

-- Pattern Matching
not True  = False
not False = True

-- Case Expression
not x = case x of True  -> False
                  False -> True

I am also fully aware that Pattern Matching is actually a form of syntax sugar that will be compiled into Case Expression.

Therefore, we can be very sure that every Pattern Matching expression can be converted to Case Expression.

Question

So, this is my question: Is the following statement true?

Every Case Expression can be re-written using Pattern Matching.

Regardless of the truthiness of the statement above, I would be glad if you could provide a formal proof to support your answer.

P/S

The motivation that drove me to seek answer for this question is because I'm currently designing my own language, which I wish to have as less feature as possible, but not too minimal like Lambda Calculus which only have 3 features.

$\endgroup$
  • $\begingroup$ Pattern matching at the function head is compiled, more or less, to case expressions in the function body. Further, your use of case expressions involves pattern matching; pattern matching vs case expressions is a bit of an apples-to-oranges comparison. $\endgroup$ – pdexter Nov 20 '18 at 8:17
  • $\begingroup$ Note that Haskell-specific questions are off-topic here. However, pattern matching is a concept general enough that this question can be made on-topic, removing the Haskell-specific parts. $\endgroup$ – chi Nov 20 '18 at 10:04
  • 1
    $\begingroup$ You definitely don't want the meaning of "expressive" that makes Turing machines and the untyped lambda calculus equally "expressive". Haskell without pattern matching or Haskell without case statements are both Turing-complete and so would be equally as "expressive" by that meaning. Haskell without either is Turing-complete. It is very rare that you want to compare programming languages based on what functions they can compute. See On the expressive power of programming languages by Matthias Felleisen for an alternative. $\endgroup$ – Derek Elkins Nov 20 '18 at 21:15
4
$\begingroup$

The expression

case e of
  p1 -> e1
  p2 -> 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 -> 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  -> False
          False -> True

cab be rewritten as

let f True  = False
    f False = True
 in f x
$\endgroup$
  • $\begingroup$ Apologies I don’t really understand how this answers my question ? Do you mind to be more concise ? For example provide your stance upon the statement I thrown out? $\endgroup$ – Wong Jia Hau Nov 20 '18 at 10:46
  • $\begingroup$ @WongJiaHau See the last edit for an example. $\endgroup$ – chi Nov 20 '18 at 10:50
  • $\begingroup$ Thanks, but does that mean any other Case Expression can be rewritten eith pattern matching ? For example, how would you write the definition of fmap using only Pattern Matching? $\endgroup$ – Wong Jia Hau Nov 20 '18 at 13:09
  • $\begingroup$ @WongJiaHau Above I showed how to translate any case into a let expression. You should be able to apply it to any case expression. $\endgroup$ – chi Nov 20 '18 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.