code optimization

Question

I must write a function "to_string" wich receives this datatype

datatype prop = Atom of string | Not of prop | And of prop*prop | Or of prop*prop;

and returns a string.

Example

show And(Atom("saturday"),Atom("night")) = "(saturday & night)"

My function is working but I have 2 problems.

1. the interpreter tells me -> Warning: match nonexhaustive
2. I think i can write the function with locals functions for all the types (Not, And, Or) and avoid duplicate code but I don't know how.

there is my code

datatype prop = Atom of string | Not of prop | And of prop*prop | Or of prop*prop;

fun show(Atom(alpha)) = alpha
    | show(Not(Atom(alpha))) = "(- "^alpha^" )"

    | show(Or(Atom(alpha),Atom(beta)))  = "( "^alpha^" | "^beta^" )"
    | show(Not(Or(Atom(alpha),Atom(beta)))) = "(- ( "^alpha^" | "^beta^" ))"
    | show(Or(Not(Atom(alpha)),Atom(beta)))  = "( (-"^alpha^") | "^beta^" )"
    | show(Or(Atom(alpha),Not(Atom(beta))))  = "( "^alpha^" | (-"^beta^") )"
    | show(Or(Not(Atom(alpha)),Not(Atom(beta))))  = "( (-"^alpha^") | (-"^beta^") )"


    | show(And(Atom(alpha),Atom(beta))) = "( "^alpha^" & "^beta^" )"
    | show(Not(And(Atom(alpha),Atom(beta)))) = "(- ( "^alpha^" & "^beta^" ))"
    | show(And(Not(Atom(alpha)),Atom(beta))) = "( (-"^alpha^") & "^beta^" )"
    | show(And(Atom(alpha),Not(Atom(beta)))) = "( "^alpha^" & (-"^beta^") )"
    | show(And(Not(Atom(alpha)),Not(Atom(beta))))  = "( (-"^alpha^") & (-"^beta^") )";

Thanks a lot for your help.

Answer 1

The general rule is as follows: if you have a recursive data type, you should use a recursive function to transform it.

Your match expression is not exhaustive because there are a lot of variants you can't handle - i.e. And(And(Atom("a"), Atom("b")), Atom("c")).

You should rewrite the function with recursive calls to itself - i.e. replace Not(Atom(alpha)) match with Not(expr):

show(Not(expr)) = "(- " ^ show(expr) ^ " )"

I'm sure you can figure out the rest (you'll have two recursive calls for and/or).