Help with indexing into new recursive datatype

Help with indexing into new recursive datatype

Post by Jon Harro » Sun, 08 Apr 2007 08:40:08



There are many problems here. Firstly, I'm going to assume that you want a
type that unifies arbitrary-dimensionality arrays into a single type.

ML already has multidimensional arrays but their dimensionality must be
resolved at compile time.

Also, I'm going to use OCaml and not SML.

Your sum type contained only one constructor, which makes it superfluous:

# type 'a array = Array of (int * 'a list)

to avoid confusion with the built-in "array" type, I'm going to call the new
type "t". If you remove the superfluous constructor you get:

# type 'a t = int * 'a list;;

However, this is also pointless because this type can be completely inferred
and, therefore, there is no need to declare it explicitly. Regardless, you
can then write examples like:

# let v : 'a t = 3, [1; 2; 3];;
val v : int t = (3, [1; 2; 3])
# let m : 'a t t = 3, [3, [1; 2; 3];
3, [4; 5; 6];
3, [7; 8; 9]];;
val m : int t t = (3, [(3, [1; 2; 3]); (3, [4; 5; 6]); (3, [7; 8; 9])])

Note that "int t t" is a kind of "'a t".

Now you can write your index function (I'll call it "get", like Array.get)
as:

# let rec get = function
| [1], (_, h::_) -> h
| [i], (d, _::t) -> get([([i], (d, t))
| 1::i, (d, h::_) -> get(i(i, (d, h))
| i::is, (d, _::t) -> get (is, (d, t))
| _ -> invalid_arg "get";;
val get : int list * ('a * ('b list as 'b)) -> 'b = <fun>

Note that this does not use the declared type "'a t" but it does rely upon
OCaml's recursive types.

This also highlights the fact that your "outermost dimensionality"
variable "d" is largely pointless too.

I suspect you really wanted to define a type that allows nested arrays.
Perhaps something like this would be better:

# type 'a t = Elt of 'a | Array of 'a t array;;
type 'a t = Elt of 'a | Array of 'a t array

Define some constructors:

# let aux f a = Array(Array.map f a);;
val aux : ('a -> 'b t) -> 'a array -> 'b t = <fun>
# let array1 a = aux (fun x -> Elt x) a;;
val array1 : 'a array -> 'a t = <fun>
# let array2 a = aux array1 a;;
val array2 : 'a array array -> 'a t = <fun>

Example nested arrays:

# let v = array1 [|1; 2; 3|];;
val v : int t = Array [|Elt 1; Elt 2; Elt 3|]
# let m = array2 [|[|1; 2; 3|]; [|4; 5; 6|]; [|7; 8; 9|]|];;
val m : int t =
Array
[|Array [|Elt 1; Elt 2; Elt 3|]; Array [|Elt 4; Elt 5; Elt 6|];
Array [|Elt 7; Elt 8; Elt 9|]|]

Element extraction:

# let rec get is x = match is, x with
| [], Elt x -> x
| i::is, Array a -> get is a.(i)
| _ -> invalid_arg "get";;
val get : int list -> 'a t -> 'a = <fun>

For example:

# get [1; 2] m;;
- : int = 6

PS: comp.lang.ml is basically dead so I'm forwarding this to c.l.functional.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.yqcomputer.com/
 
 
 

1. Help with indexing into new recursive datatype

2. recursive type vs recursive datatype in SML


I have some code that uses this datatype declaration:

datatype ('k, 'v) node = NODE of 'v option * ('k * ('k, 'v) node) list

and it compiles and works. I originally tried to write the code based on
this type declaration:

type ('k, 'v) node = 'v option * ('k * ('k, 'v) node) list

It produced this error

[opening busted_tree.sml]
busted_tree.sml:21.47-22.39 Error: operator and operand don't agree
[circularity]
operator domain: 'Z * 'Z list * ('Z * ('Y option * 'X list)) list
operand: 'Z * 'Z list * 'X list
in expression:
doBranches (key,rest,branches)

The thing is, as far as I can tell, 'X list *is*

('Z * ('Y option * 'X list)) list

based on the type declaration.

Is there a fundamental difference between a type declaration and a
datatype declaration in SML regarding recursive type declarations?

Thanks for any enlightenment...

-thant

3. New approach to ye olde cross-datatype indexing problem

4. parallel recursive build (was: Recursive vs non-recursive makefiles)

5. Thanks to all who advised me on recursive datatypes

6. Scalar datatypes & recursive types

7. Correction: new procedure for converting a new recursive polynomial set into matrices

8. new procedure for converting a new recursive polynomial set into matrices

9. Optimizer not using index on raw datatype column

10. TLC / Simulink Datatype Index List?

11. Using Indexes for DATETIME datatype

12. Alter column datatype in trans replication that has index...

13. Error P1023 datatype bit is not allowed to have index (SQL2K SP3)

14. indexing documents with datalink datatype

15. Full-text indexing image datatypes (characters vs numbers)