Back to Questions
1.2k
views4
comments
Union type with "tag" value
f#

Hi, I was trying to do something like

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

type pf =
    | Bot
    | Top
    | Var of int
    | Neg of pf
    | Cnj of pf * pf
    | Dsj of pf * pf
    | Imp of pf * pf
    with
        val mutable _cnfVar : ref int;
        
        member f.CnfVar
            with get () = !f._cnfVar
            and  set (v) = f._cnfVar := v;
    end
    ;;

i.e., I want that every value/object of type «pf» have an associated int value. Of course, since I am asking for help, this code does not work. I got an «error: This member is not permitted in an augmentation.».

I could use a hash table to associate each pf with an int, but since I will have a few hundred thousands of these pf, I would like to avoid the hash table if possible.

Is there any way to create a new field in an union type? (Or any other way to get the same result without a memory/performance penalty?)

Thanks in advance.

.

Why don't you use a type that contains the int value and a pf value? Or simply a pair...

type PfWithInt = { pfv:pf; v:int }

Antonio

By on 12/19/2007 3:01 AM ()

Hi Antonio,

Thanks for the answer, but what I want is not that simple. The type pf is tree-like recursive one, and I need each node to be associated with a tag. Actually what I ultimately intend is to construct elements of type pf as a DAG (direct acyclic graph) and the tag would be a kind of signal for not processing the same sub-graph more than once.

Of course I can redefine pf.

1
2
3
4
5
6
7
8
9
10
11

type pf =
    | Bot
    | Top
    | Var of int
    | Neg of pfi
    | Cnj of pfi * pfi
    | Dsj of pfi * pfi
and pfi = {
    mutable var: int ref;
    fml: pf;
};;

But then I would have to wrap and unwrap the "real" pf values every time I need to work only with then, and not with the tags, like in pattern matching for example. That is the solution I am working with (just because I couldn't think about anything better) but I think it makes the code less readable.

Instead of writing function like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

let rec procPf f =
    match f with
    | Bot -> bot_case ()
    | Top -> top_case ()
    | Var n -> var_case n
    | Cnj (f1,f2) -> cnj_case (procPf f1, procPf f2)
    | Dsj (f1,f2) -> dsj_case (procPf f1, procPf f2)
    | Neg Bot -> top_case ()


    | Neg Top -> bot_case ()
    | Neg (Var n) -> nvar_case n
    | Neg (Neg f1) -> procPf f1
    | Neg (Cnj (f1,f2)) -> dsj_case (procPf (Neg f1), procPf (Neg f2))
    | Neg (Dsj (f1,f2)) -> cnj_case (procPf (Neg f1), procPf (Neg f2))
;;

I now have to write it like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

let rec procPf f =


    match f with


    | Bot -> bot_case ()


    | Top -> top_case ()


    | Var n -> var_case n


    | Cnj (f1,f2) -> cnj_case (procPf f1.fml, procPf f2.fml)


    | Dsj (f1,f2) -> dsj_case (procPf f1.fml, procPf f2.fml)


    | Neg {fml=Bot} -> top_case ()


    | Neg {fml=Top} -> bot_case ()


    | Neg {fml=(Var n)} -> nvar_case n


    | Neg {fml=(Neg f1)} -> procPf f1.fml


    | Neg {fml=(Cnj (f1,f2))} -> dsj_case (procPf (Neg f1.fml), procPf (Neg f2.fml))


    | Neg {fml=(Dsj (f1,f2))} -> cnj_case (procPf (Neg f1.fml), procPf (Neg f2.fml))


;;

It is an acceptable solution (in my opinion), but I still think that the first version was easier to read, so If there is a way to add extra field to union values, I would prefer to use it and keep the patterns as easier to read as possible.

Thanks again.

By on 12/20/2007 12:44 AM ()

Hi,

This sounds like a very interesting problem. You are right in that the first version is easier to read.

I think that it is a prime candidate for using active patterns. If you're not aware of them, active patterns provide a "view" of a data structure to facilitate decomposition for pattern matching. I translated your code to use this feature. I replaced the struct pfi with a class for reasons you will see later on. Here is the code I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

type pf' =
  | Bot
  | Top
  | Var of int
  | Neg of pf
  | Cnj of pf * pf
  | Dsj of pf * pf
  | Imp of pf * pf
and pf =
  val mutable var: int
  val fml: pf'
  new(x: pf') = { var = 0; fml = x }
  new(x: pf', y: int) = { var = y; fml = x }

let (|Bot|Top|Var|Neg|Cnj|Dsj|Imp|) (p: pf) =
  match p.fml with
  | Bot -> Bot
  | Top -> Top
  | Var n -> Var n
  | Neg n -> Neg n
  | Cnj (n, o) -> Cnj (n, o)
  | Dsj (n, o) -> Dsj (n, o)
  | Imp (n, o) -> Imp (n, o)

let rec procPf (f: pf) =
  match f with
  | Bot -> bot_case () 
  | Top -> top_case ()
  | Var n -> var_case n
  | Cnj (f1,f2) -> cnj_case (procPf f1, procPf f2)
  | Dsj (f1,f2) -> dsj_case (procPf f1, procPf f2)
  | Neg Bot -> top_case ()
  | Neg Top -> bot_case ()
  | Neg (Var n) -> nvar_case n
  | Neg (Neg f1) -> procPf f1
  | Neg (Cnj (f1,f2)) -> dsj_case (procPf (new pf (Neg f1)),
                                   procPf (new pf (Neg f2)))
  | Neg (Dsj (f1,f2)) -> cnj_case (procPf (new pf (Neg f1)),
                                   procPf (new pf (Neg f2)))

A few things of note here. First, if you are using a mutable variable to hold your int, it doesn't really need to be a ref. Obviously, it can be, but I took that part out mainly because it was giving me headaches during class initialization.

Second, the matching code for procPf is nearly identical to yours, except for the last 2 matches. This also highlights the limitation of active patterns vs. union types. Active patterns, as far as I know, can only be used for decomposition, not construction. So, I use new to create new pf values that can be passed to procPf for recursive evaluation. I tested the code using the following placeholders, and it seems to work okay.

1
2
3
4
5
6

let bot_case _ = true
let top_case _ = false
let var_case x = (x % 2) = 0
let cnj_case (x, y) = x = y
let dsj_case (x, y) = x <> y
let nvar_case x = (x % 2) <> 0

EDIT: You could just keep pfi a record with a static member named new or init or something like that to improve code readability.

Hope this helps,

z.

By on 12/20/2007 3:10 AM ()

Hi zakaluka,

Thanks a lot for the answer. Helped a lot. I think it is just the kind of thing I was looking for. I will take a closer look at active patterns.

Thanks again.

By on 12/20/2007 6:32 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper