I have this code:
type Variable = String
data Expr = T | Var Variable | And Expr Expr | Not Expr
The test case is as follows:
prop_v1 = v (Not (And (Var "y") T)) === ["y"]
What is the meaning of data Expr - is it just defining the types that can be input and their parameters? I.e. a Var takes a Variable, And takes two Expr's.
The datatype declaration for Expr gives rise, systematically, to a set of patterns which cover all possible things that a value of type Expr can be. Let's do the translation
data Expr -- any e :: Expr must be one of
= T -- T
| Var Variable -- (Var x) -- where x :: Variable
| And Expr Expr -- (And e1 e2) -- where e1 :: Expr, e2 :: Expr
| Not Expr -- (Not e1) -- where e1 :: Expr
You can see that the T, Var, And and Not that head up each data clause are constructors, and live in the value language; the rest of the things in each clause live in the type language, saying what type each component of an Expr must have. Each of the corresponding patterns consists of the constructor applied to pattern variables standing for components which have the given types. Basically, the patterns that show up on the left-hand side of a function are made by repeatedly refining pattern variables to the patterns that their values can possibly take, as indicated by their type.
Writing a function by pattern matching does not consist of saying what to do: it consists of saying what the output is for the possible cases of what the input is. You need to analyse the input into cases where you can easily say what the output must be. So, start with one general case...
v :: Expr -> [Variable]
v e = undefined
...and refine it. Ask "Can you tell what it is yet?". We can't tell what v e is without knowing more about e. So we'd better split e. We know that e :: Expr, so we know what patterns its value can match. Make four copies of your program line, and in each, replace e by one of the four possible pattern listed above.
v :: Expr -> [Variable]
v T = undefined
v (Var x) = undefined
v (And e1 e2) = undefined
v (Not e1) = undefined
Now, in each case, can you tell what the output is? The handy thing is that you can make use of recursive calls on components. Assume you already know what vars e1 and vars e2 are when you're trying to say what v (And e1 e2) must be. If you get the steps right, the program will be correct.
I find it's often helpful to think in terms of concrete examples. Take your test example.
v (Not (And (Var "y") T))
That's supposed to be ["y"], right? Which pattern does it match?
Not e1 -- with e1 = And (Var "y") T
What's
v e1
? Looking at it, it had better be
["y"]
In this example, what's v (Not e1) in terms of v e1? The very same. That might suggest a suitable expression to replace undefined in
v (Not e1) = undefined -- can you tell what this is now?
(Of course, a suggestive example is just a good start, not a guarantee of correctness.)
The takeaway messages: (1) build patterns by splitting pattern variables, figuring out the possible patterns by looking at the declaration of the type; (2) assume that recursive calls on components give you the right answer, then try to construct the right answer for the whole problem.
Shameless plug: shplit is a simple tool I built for my students, capturing message (1) mechanically.
data Expr defines a new data type, specifying "constructors" like Var which takes a Variable or And which takes two expressions.
You can match against an Expr using these constructors:
fn (Var name) = ...
fn (And exp1 exp2) = ...
...
Note that data Expr = ... only defines one type, Expr. Var, And...etc are all constructors of Expr, so a value like Var "blarg" will be of type Expr.
You should probably read the first couple chapters of Learn You a Haskell to learn the basics.
Also, how would I approach defining this function with pattern matching?
Excuse me, but this is the wrong question. This is like someone is asking "How would I approach matrix multiplication with array indexing?" (To which one could simply reply: Why, how do you do it without array indexing?)
You should ask "Given an Expr, how can I find all the variables that occur in it?" And then, the meaning of pattern matching unfolds itself automatically.
Your data type Expr is one possible representation of fairly simple boolean expressions. You have variables, a literal value T (that stands for true maybe - btw, are you sure you have not forgotten F?) and have that, if x is an Expression then so will be Not x and if x and y are expressions, then so will be And x y.
So, first, please describe precisely (not just: "I go from left to right and write down each variable name I find.") how to find all the variables in such an expression in your mothers language. For example: "If the expression is T, the list of variables occuring in that expression is empty." Be sure to cover all possible cases. Then come back and we will show you how to translate that into Haskell, but I am sure you will have noticed for yourself by then.
