CODEWITHSUNDEEP
ocaml
rgrinberg
rgrinberg

Reputation: 9878

How to write a functor over arrays and strings?

I would like to make my code generic over strings and arrays (any indexable type really) using the following signature:

module type Indexable = sig
  type 'a t
  val get : int -> 'a t -> 'a
end

module MyCode (I : Indexable) = struct ... end

But of course I cannot apply my signature to strings as follows:

module StrMyCode = MyCode(struct
  type 'a t = string
  let get i a = a.[i]
end)

Is there any way to fix this issue? Or perhaps a different aprroach? I know I can use arrays of characters in the worst case but I'd rather save my code from ugly casts and this is something that was on my mind before so I'd like to get a clear answer for this.

Upvotes: 3

Views: 272

Answers (3)

Tim Destan
Tim Destan

Reputation: 2028

If you declare the element type of the indexable as a separate type, you can do something like this:

module type Indexable = sig
  type t
  type elt
  val get : int -> t -> elt
end

module IndexableString : Indexable = struct
  type t = string
  type elt = char
  let get i a = a.[i]
end

module MyCode (I : Indexable) = struct
  (* My code implementation *)
end

module StrMyCode = MyCode(IndexableString)

For arrays, you can do more or less the same:

module ArrayIndexable = struct
    type elt = char
    type t = char array
    let get i a = a.(i)
end

Now, if you wish to retain some flexibility with arrays, you may change the above into a functor:

module ArrayIndexable (E : sig type e end) : Indexable with type elt = E.e =
struct
    type elt = e
    type t = elt array

    let get i a = a.(i)
end

It is more verbose than the polymorphic version you are looking for, but it let you encode both "indexable" types uniformly.

Upvotes: 2

Virgile
Virgile

Reputation: 10148

GADT can be used with the functorized approach:

module type Indexable = sig
  type 'a t
  val get: int -> 'a t -> 'a
end

module MyCode(I:Indexable) = struct
 let head x = I.get 0 x
end

Arrays can of course be made Indexable trivially:

module IndexableArray = struct
  type 'a t = 'a array
  let get i x = x.(i)
end

For string, you can just use a GADT with a single constructor. Note however, that you have to put some type annotation for get in order to force the polymorphic type (otherwise, the inferred type is int -> char t -> char):

module IndexableString = struct
  type 'a t = String: string -> char t
  let of_string s = String s
  let get: type a. int -> a t -> a =
    fun i s -> match s with String s -> s.[i]
end

Upvotes: 6

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66793

Here is something I made using GADTs. I'm just wrapping my head around them, so there may be something a little wrong here. But it seems to work as far as I can see (with OCaml 4):

type _ indexable =
    | A : 'a array -> 'a indexable
    | C : string -> char indexable

let index (type s) (x: s indexable) i : s =
    match x with
    | A a -> a.(i)
    | C s -> s.[i]

let main () =
    let x = A [| 1; 2 |] in
    let y = C "abc" in
    Printf.printf "%d\n" (index x 0);
    Printf.printf "%c\n" (index y 1)

If I load into the toplevel, I get this:

val index : 'a indexable -> int -> 'a = <fun>
val main : unit -> unit = <fun>
# main ();;
1
b
- : unit = ()
#

This might not be as general as what you're looking for.

Upvotes: 5

Related Questions