recursion - Recursing Binary Decision Diagrams in SML -

in 1 of classes @ university, learning functional programming through sml/nj.

i have been given assignment requires perform number of operations on binary decision diagrams. (conjunction, disjunction, not, etc.)

based on truth table

i have following function defined

fun ifthenelse(p,q,r) =    if p q else r; 

then, have bdd (robdd) datatype declared such

datatype robdd = true                | false                | ifthenelse of string * robdd * robdd; 

so far straightforward. i'm getting lost on operating on bdd's, instance, creating robdd represents conjunction of 2 robdd's.

my function declaration far looks this

infix bddand; fun op bddand(first:robdd,second:robdd) =     ... 

it called 2 robdd's, this

val conjunction = ifthenelse("p", true, false) bddand ifthenelse("q", true, false); 

from here, i'm not sure start. professor has given hint:

of course, true bddand anyrobdd anyrobdd. ordering: if you’re asked compute (ifthenelse(p, ϕ, ψ) bddand ifthenelse(q, χ, θ)) proposition letter @ root of resultant robdd either p or q – whichever less. you’ll need 3 cases: p < q, p = q, , p > q. having determined root, recurse down branches

the first part makes sense, i'm left 2 questions.

1. how determine root of robdd?

if it's true or false, doesn't have one, right? there should special case being given boolean? if given more fleshed out robdd, ifthenelse("p", true, false), how gain access p, in robdd structure? note first argument of ifthenelse letter.

2. how recurse through robdd's?

i understand basics of recursive functions in sml, i'm confused on how within robdd structure, compared say, lists. i'm guessing need build sort of curried functions operate on each argument in robdd, i'm not sure how structure it.

apologies long winded question, i'm having hard time understanding how operate on robdd structure. explanation helpful, thank you!

edit:

after syntax , renaming, bddand function looks this

infix bddand; fun op bddand (true, second) = second   | op bddand (first, true) = first   | op bddand (false, _) = false   | op bddand (_, false) = false   | op bddand ((left (ifthenelse (prop1, true1, else1))), (right (ifthenelse (prop2, true2, else2)))) =          if prop1 < prop2            ifthenelse (prop1, true1 bddand right, else1 bddand right)         else if prop1 > prop2           ifthenelse (prop2, true2 bddand left, else2 bddand left)         else           ifthenelse (prop1, true1 bddand right, else1 bddand left); 

pattern matching starting point.

the cases involving true , false simple:

fun op bddand (true, second) = second      | bddand (first, true) = first      | bddand (false, _) = false      | bddand (_, false) = false 

the last 1 more interesting:

 | bddand (ifthenelse (v1, t1, e1)) (ifthenelse (v2, t2, e2)) = ... what? ... 

as professor hinted, need consider 3 cases v1 , v2:

if v1 < v2 ... else if v1 > v2 ... else ... 

looking @ first one, v1 < v2, should pick v1 "root".

it's not difficult convince that

(ifthenelse p t1 e1) bddand (ifthenelse q t2 e2) 

is equivalent to

ifthenelse p (t1 bddand (ifthenelse q t2 e2)) (e1 bddand (ifthenelse q t2 e2)) 

that is, create 1 "tree" 2 recursing both branches of ifthenelse chose, bringing other tree along.
recursion terminate since bddand applied smaller , smaller arguments, , result ordered long input ordered (which assume allowed assume).

matching code above,

 | bddand (left (ifthenelse (v1, t1, e1))) (right (ifthenelse (v2, t2, e2))) =          if v1 < v2 ifthenelse (v1, t1 bddand right, e1 bddand right)         else ... 

(using as-patterns make easier refer parameters wholes.)

the remaining 2 cases left exercise.