Custom datatype and function in SML

Question

i have datatype expression defined.

datatype 'a expression = Not of 'a expression
                    | Or of 'a expression list
                    | And of 'a expression list
                    | Eq of 'a expression list
                    | Imp of 'a expression * 'a expression
                    | Var of 'a
                    | True | False;

And i need to implement function of this type

getVars (= ''a expression -> ''a list) goal of this function is to return all Var values in list.

Here is an example of function return.

- getVars (Eq [Var "A", Var "B", Imp (Var "D", Not (Var "Q")), Var "D", Var "B"]); val it = ["A","B","D","Q"] : string list

I have no idea how to implement that. Give me some advice plz.

Answer 1

Since you have provided no attempt, here is a template to get you started:

fun getVars expr =
    case expr of
         Not subExpr  => ...
       | Or  subExprs => ...
       | And subExprs => ...
       | ...

Try and provide a bigger attempt to get more specific feedback.

Answer 2

Here is my attempt of solution for this case.

fun getVars expr =
    case expr of
       Var i => i (*Only those i's are in output list*)
    |  Not j => getVars(j) (*j is expression so i can use recursion*)
    |  Or k => map (fn x => getVars(x)) k (*there i need to loop over list and do recursion over every element in list, couse elements are expressions*)
    |  And k => map (fn x => getVars(x)) k (*same*)
    |  Eq k => map (fn x => getVars(x)) k  (*same*)
    |  Imp k => (*problem for me couse its not list*)
(*And i need to put solution for True and False too...*);

But this code doesn't output list, only elements, becouse i don't know how to add elements to list if there is a case of no elements added it should return [].

getVars True = [];
getVars Eq [Var 1, Var 2] = [1,2];
getVars Or [Var "te", Var "st"] = ["te", "st"];
getVars And [True, False] = [];
getVars And [Var "st", Var "st"] = ["st"]; (*This one is interesting*)

There is more input and output examples.