Question on Variant Types

Question on Variant Types

[Seth J. Fogarty]

[-- Attachment #1: Type: text/plain, Size: 1903 bytes --]

I have a situation in which I have two kinds of trees. The simplified
example is linked lists:

type foo = [`Nil | `Tree of foo]
type bar = [`Nil | `Leaf of int | `Tree of bar]

I have a tree with only shape, and a tree with some information. I want to
be able to distinguish between these.  Here I have functions to assert
types, but these annotations will be part of the signatures of functions
actually doing things in the real code. But I do want to have these static
checks on contests.

let f x : foo = x
let g x : bar = x
let a = `Tree (`Nil)
let b = `Tree (a)
let c = `Tree (f a)
let d = `Tree (`Leaf 1)

As is proper, I can run f on a, b, and c, but not on d. D is not a valid
foo.
But I cannot run g on c. This makes sense, as I have said 'a tree of bars
contains a bars.' But I want to somehow note that a tree of bars MIGHT
contain foo's. Is there any way to annotate this?

I cannot say

type bar = [`Nil | `Leaf of int | `Tree of [bar | foo]] as bar is not fully
defined.
I cannot say
type bar = [`Leaf of int | `Tree of bar | foo] because tree cannot have two
separate types.

The current, icky, non-variant type solution has the equivalent of
type 'a foo = Nil | Tree of foo | F of 'a
With special things filling in for 'a. But I end up putting EVERYTHING in 'a
because I don't have a way to statically guaranteeing that my "leaf foo"'s
are valid "leaf or branch foo's". So I have a weaker system than I want.

Any suggestions? Seems like variant types should work here. I COULD add type
annotations to functions, check them, and then remove the annotations so
that my types are never constrained. I think that might even work. But it
seems rather icky.

-- 
Seth Fogarty             sfogarty@[gmail.com|rice.edu|livejournal]
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

[-- Attachment #2: Type: text/html, Size: 2162 bytes --]

Re: [Caml-list] Question on Variant Types

[Jonathan Roewen]

> type foo = [`Nil | `Tree of foo]
> type bar = [`Nil | `Leaf of int | `Tree of bar]
>
> let f x : foo = x
> let g x : bar = x
> let a = `Tree (`Nil)
> let b = `Tree (a)
> let c = `Tree (f a)
> let d = `Tree (`Leaf 1)
>
> As is proper, I can run f on a, b, and c, but not on d. D is not a valid
> foo.
> But I cannot run g on c. This makes sense, as I have said 'a tree of bars
> contains a bars.' But I want to somehow note that a tree of bars MIGHT
> contain foo's. Is there any way to annotate this?

>From the ocaml reference docs:

# let bar_of_foo t = (t : foo :> bar);;
val bar_of_foo : foo -> bar = <fun>
# g (bar_of_foo c);;
- : bar = `Tree (`Tree `Nil)

Jonathan

Re: [Caml-list] Question on Variant Types

[Jonathan Roewen]

> # let bar_of_foo t = (t : foo :> bar);;
> val bar_of_foo : foo -> bar = <fun>
> # g (bar_of_foo c);;
> - : bar = `Tree (`Tree `Nil)

I should've added that without needing an intermediate function, you
can also do:
g (c : foo :> bar);;

>
> Jonathan
>

Re: [Caml-list] Question on Variant Types

[Seth J. Fogarty]

[-- Attachment #1: Type: text/plain, Size: 584 bytes --]

Followup question:
Given I have:
type foo = [`A | `B of int | `C of char]
type bar = [`B of int | `C  of char| `D]

and a function
let f (x : foo) : bar =
match x with
    `A -> `D
   |`B _
   |`C _ -> (x : bar)

Is there any way to properly coerce this using the restricted variant
information of x? Or do I have to duplicate code and reconstruct x?

-- 
Seth Fogarty             sfogarty@[gmail.com|rice.edu|livejournal]
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

[-- Attachment #2: Type: text/html, Size: 787 bytes --]

Re: [Caml-list] Question on Variant Types

[Jonathan Roewen]

> Followup question:
> Given I have:
> type foo = [`A | `B of int | `C of char]
> type bar = [`B of int | `C  of char| `D]
>
> and a function
> let f (x : foo) : bar =
> match x with
>     `A -> `D
>    |`B _
>    |`C _ -> (x : bar)
>
> Is there any way to properly coerce this using the restricted variant
> information of x? Or do I have to duplicate code and reconstruct x?

let f (x : foo) : bar = match x with
| `A -> `D
| `B _ | `C _ as x -> (x : bar)

Jonathan

Re: [Caml-list] Question on Variant Types

[Jonathan Roewen]

On 6/29/06, Seth J. Fogarty <sfogarty@gmail.com> wrote:
> If you have time, I have one more question I can't seem to solve. Which
> quite possibly has as simple an answer as the other two. You've been very
> helpful so far, and I don't want to impose, so feel free to let me know if
> you've not the time.
>
> type foo = [`A of int | `B | 'D of foo]
> type bar = [`A of int | `C of foo * bar | 'D of bar]
>
> let rec occurs i x =
>    match x with
>    |`A j -> i = j
>    |`C (foo, bar) -> (occurs i foo) or (occurs i bar)
>    |_ -> false
>
> I would like occurs to work on bars and foos. But as it is, occurs won't
> work on either, because it assigns the `C variant the type "`C of 'b * 'b".
> Even if I spell out `D and `B, I cannot get it to accept. Nor does:
>
> let rec occurs i (x : 'a) =
>    match x with
>    |`A j -> i = j
>    |`C ((foo : foo), (bar : bar)) ->
>        (occurs i (foo : foo :> 'a) or
>        (occurs i (bar : bar :> 'a)))
>    |_ -> false
>
> even compile.
>
> let rec occurs i x =
>    match x with
>    |`A j -> i = j
>    |(`C (foo, bar) : bar) -> (occurs i foo) or (occurs i bar)
>    |_ -> false
>
> has similar problems.
>
> Again, any assistance would be greatly appreciated, but is not necessary.


Only thing I could think of was:

# let rec occurs i = function
  | `A j -> i = j
  | `C (f,b) -> (occurs_foo i f) || (occurs_bar i b)
  | otherwise -> false
  and occurs_foo i = function
  | `A j -> i = j
  | otherwise -> false
  and occurs_bar i = function
  | `A j -> i = j
  | `C (f,b) -> (occurs_foo i f) || (occurs_bar i b)
  | otherwise -> false;;
val occurs :
  'a ->
  [> `A of 'a
   | `C of ([> `A of 'a ] as 'b) * ([> `A of 'a | `C of 'b * 'c ] as 'c) ] ->
  bool = <fun>
val occurs_foo : 'a -> [> `A of 'a ] -> bool = <fun>
val occurs_bar :
  'a -> ([> `A of 'a | `C of [> `A of 'a ] * 'b ] as 'b) -> bool = <fun>
# occurs 2 (`C ((`D (`B)), (`C (`A 3, (`D (`C (`A 4, `A 2)))))));;
- : bool = false

Basically specialising on the two types. There may be a way to coerce
them to not need it, but I'm not sure what it is.

Here are two other solutions:

# let rec occurs i x =
    let map = function
    | `A j -> `A j
    | `C (f,b) -> print_endline "C"; `C (f,b)
    | x -> `None
    in match map x with
    | `A j -> i = j
    | `None -> false
    | `C (f,b) -> (occurs i f) or (occurs i b);;
val occurs : 'a -> ([> `A of 'a | `C of 'b * 'b ] as 'b) -> bool = <fun>

--

# let occurs i x =
    let map = function
    | `A _ | `C (_,_) as x -> x | _ -> `None
    in
    let rec occurs = function
    | `A j -> i = j
    | `C (f,b) -> (occurs (map f)) or (occurs (map b))
    | `None -> false
    in occurs x;;
val occurs :
  'a ->
  [ `A of 'a
  | `C of
      ([> `A of 'a | `C of 'b * ([> `A of 'a | `C of 'b * 'c ] as 'c) ] as 'b) *

      'c
  | `None ] -> bool = <fun>

Pretty damn ugly! But it works... Perhaps someone more proficient with
variant types on the list can come up with a more reasonable solution
than my hack ;-)

Jonathan

Re: [Caml-list] Question on Variant Types

[Jacques Garrigue]

On 6/29/06, Seth J. Fogarty <sfogarty@gmail.com> wrote:
> If you have time, I have one more question I can't seem to solve. Which
> quite possibly has as simple an answer as the other two. You've been very
> helpful so far, and I don't want to impose, so feel free to let me know if
> you've not the time.
>
> type foo = [`A of int | `B | 'D of foo]
> type bar = [`A of int | `C of foo * bar | 'D of bar]
>
> let rec occurs i x =
>    match x with
>    |`A j -> i = j
>    |`C (foo, bar) -> (occurs i foo) or (occurs i bar)
>    |_ -> false
>
> I would like occurs to work on bars and foos. But as it is, occurs won't
> work on either, because it assigns the `C variant the type "`C of 'b * 'b".
> Even if I spell out `D and `B, I cannot get it to accept.

As long as foo and bar are two subtypes of a common type, you can
still solve the problem by defining that type and using subtyping:

type foobar = [`A of int | `B | `C of foobar * foobar | `D of foobar]
let occurs_foo i x = occurs i (x : foo :> foobar)
let occurs_bar i x = occurs i (x : bar :> foobar)

Jacques Garrigue

Another question on variant types and matching (was: Re: [Caml-list] Question on Variant Types)

[Richard Jones]

I have another question on variant types which seems to be related to
this, but perhaps the opposite way round.  How can I get the code
below to work?  (It's simplified greatly from a real problem I'm
having).

Rich.

----------------------------------------------------------------------
type colour = [ `Red | `Green | `Blue ]
type colour' = [ colour | `Default ]
type instructions = Set_foreground of colour' | Set_background of colour'

let default_fg : colour = `Red
let default_bg : colour = `Green

let process_instructions =
  List.fold_left (
    fun (fg, bg) ->
      function
      | Set_foreground `Default ->
	  let new_fg = default_fg in
	  (new_fg, bg)
      | Set_foreground new_fg ->
	  (new_fg, bg)
      | Set_background `Default ->
	  let new_bg = default_bg in
	  (fg, new_bg)
      | Set_background new_bg ->
	  (fg, new_bg)
  )

let string_of_colour = function
  | `Red -> "red"
  | `Green -> "green"
  | `Blue -> "blue"

let () =
  let instrs =
    [ Set_foreground `Blue; Set_background `Red; Set_foreground `Default ] in
  let fg, bg = `Green, `Blue in
  let fg, bg = process_instructions (fg, bg) instrs in
  print_endline ("fg = " ^ string_of_colour fg);
  print_endline ("bg = " ^ string_of_colour bg)
----------------------------------------------------------------------

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: Another question on variant types and matching (was: Re: [Caml-list] Question on Variant Types)

[Jonathan Roewen]

Hi,

You just need some type constraints so it knows you're starting with a
colour pair, not a colour' pair:

let process_instructions (initial:colour * colour) =
 List.fold_left (
   fun (fg, bg) ->
     function
     | Set_foreground `Default ->
         let new_fg = default_fg in
         (new_fg, bg)
     | Set_foreground (#colour as new_fg) ->
         (new_fg, bg)
     | Set_background `Default ->
         let new_bg = default_bg in
         (fg, new_bg)
     | Set_background (#colour as new_bg) ->
         (fg, new_bg)
 ) initial

Jonathan

On 6/30/06, Richard Jones <rich@annexia.org> wrote:
> I have another question on variant types which seems to be related to
> this, but perhaps the opposite way round.  How can I get the code
> below to work?  (It's simplified greatly from a real problem I'm
> having).
>
> Rich.
>
> ----------------------------------------------------------------------
> type colour = [ `Red | `Green | `Blue ]
> type colour' = [ colour | `Default ]
> type instructions = Set_foreground of colour' | Set_background of colour'
>
> let default_fg : colour = `Red
> let default_bg : colour = `Green
>
> let process_instructions =
>  List.fold_left (
>    fun (fg, bg) ->
>      function
>      | Set_foreground `Default ->
>          let new_fg = default_fg in
>          (new_fg, bg)
>      | Set_foreground new_fg ->
>          (new_fg, bg)
>      | Set_background `Default ->
>          let new_bg = default_bg in
>          (fg, new_bg)
>      | Set_background new_bg ->
>          (fg, new_bg)
>  )
>
> let string_of_colour = function
>  | `Red -> "red"
>  | `Green -> "green"
>  | `Blue -> "blue"
>
> let () =
>  let instrs =
>    [ Set_foreground `Blue; Set_background `Red; Set_foreground `Default ] in
>  let fg, bg = `Green, `Blue in
>  let fg, bg = process_instructions (fg, bg) instrs in
>  print_endline ("fg = " ^ string_of_colour fg);
>  print_endline ("bg = " ^ string_of_colour bg)
> ----------------------------------------------------------------------
>
> --
> Richard Jones, CTO Merjis Ltd.
> Merjis - web marketing and technology - http://merjis.com
> Team Notepad - intranets and extranets for business - http://team-notepad.com
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>