CODEWITHSUNDEEP
haskellpattern-matchinglambda-calculus
Rob
Rob

Reputation: 73

Pattern matching implementing Lambda calculus in Haskell

I want to write a function that will collect the variable names that have been used in a lambda calculus term, both as a Variable and in a Lambda abstraction.

For example in the code I would get the following output:

  *Main> used example
         ["a","b","x","y"]

I want to return them in an ordered list. I think I could achieve this using pattern matching and wild cards, is this possible?

import Data.Char
import Data.List

type Var = String

data Term =
    Variable Var
  | Lambda   Var  Term
  | Apply    Term Term

example :: Term
example = Lambda "a" (Lambda "x" (Apply (Apply (Lambda "y" (Variable "a"))
                                               (Variable "x"))
                                        (Variable "b")))

-- I'll use this function to merge two ordered lists together:

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
    | x == y    = x : merge xs ys
    | x <= y    = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

used :: Term -> [Var]
used [] = []
used Variable_ = _
used Lambda_ = _
used Apply_ = _

This is clearly not correct.

How do I collect the variable names and add them to a list? If pattern matching and wild cards are not correct, please can you suggest how I could go about this?

Upvotes: 1

Views: 915

Answers (1)

Kyle Parsons
Kyle Parsons

Reputation: 1525

So used is a function Term -> [Var]. And so to write used in a pattern matching style, we'll need to make a case for each of the different ways to be a Term. Looking at the definition of Term we see there are 3 ways to be a Term: by being a variable, a lambda, or an apply. In particular being an empty list ([]) is not a way to be a Term, so that case should be removed.

Next lets look at the syntax of pattern matching. It should look like the following:

used :: Term -> [Var]
used (Variable var) = ...
used (Lambda var term) = ...
used (Apply term1 term2) = ...

Note the parenthesis around each set of data constructor and arguments. Also note that variables in Haskell must start with lowercase characters. Finally note that we haven't actually written any of the bodies of the cases for used. The above is not actually valid Haskell.

Let's go over how to fill in all the right hand sides of these cases. While we do so let's keep in mind that used is meant to return an ordered list of Var without repeats. Most of that isn't captured in the type of used.

The Variable case:

used (Variable var) = ...

So the right hand side here has to be a list of Var. Checking the declaration of Term and the Variable case, we see that var must be a Var. Thus, really the only option for the implementation is:

used (Varable var) = [var]

The Lambda case

used (Lambda var term) = ...

So again checking the type declaration of Term we see that var is a Var and term is a Term. Maybe that's why we used those variable names ;). So some variables appear in var and some variables appear in term. If we knew all of those variables we could put those results together with merge. For var we can do the same thing as in the Variable case. For term we need a way to turn a Term into a variable or a list of variables. Luckily we have such a way. It's the function we're currently defining: used! So we can write this case as:

used (Lambda var term) = merge [var] (used term)

It might look a bit silly to use merge to merge a singleton list into another list, but we need to keep the result ordered and merge is the hammer we have so we turned this problem into a nail.

The Apply case

This case will go quite quickly using the same idea as above. We have

used (Apply term1 term2) = ...

term1 and term2 are Term's. We'll extract the variables from each of them using used and merge them together using merge.

used (Apply term1 term2) = merge (used term1) (used term2)

Overall this gives the implementation of used:

used :: Term -> [Var]
used (Variable var) = [var]
used (Lambda var term) = merge [var] (used term)
used (Apply term1 term2) = merge (used term1) (used term2)

with

  *Main> used example
         ["a","b","x","y"]

as desired.

Upvotes: 3

Related Questions