generic Hashtbl.to_array

generic Hashtbl.to_array

[Christoph Bauer]

Hi,

what is the best way to write Hashtbl.to_array?

Hashtbl.to_array : ('a, 'b) Hashtbl.t -> ('a * 'b) array

The simples idea has the problem, that you don't have
a initial value to make the result array:

let to_array t =
  let a =  Array.init make (Hashtbl.length t) ?init?  in
    ignore
      (Hashtbl.fold
         (fun k v i ->
            a.(i) <- (k, v); i + 1)
         t 0);
    a

The best solution I found is

let to_array t =
  let dummy =  Array.init 0 (fun _ -> raise Not_found) in
    fst
      (Hashtbl.fold
         (fun k v (a, i) ->
            if i = 0 then  
              let a = Array.make (Hashtbl.length t) (k, v) in
                (a, 0)
            else (a.(i) <- (k, v); (a, i + 1)))
         t (dummy, 0))

Is there a better one?

Thanks,
Christoph Bauer

Re: [Caml-list] generic Hashtbl.to_array

[Erick Tryzelaar]

Christoph Bauer wrote:
> Hi,
>
> what is the best way to write Hashtbl.to_array?
>
> Hashtbl.to_array : ('a, 'b) Hashtbl.t -> ('a * 'b) array
>
> The simples idea has the problem, that you don't have
> a initial value to make the result array:

The easiest is to use a temporary list:

# let x = Hashtbl.create 2;;
val x : ('_a, '_b) Hashtbl.t = <abstr>
# Hashtbl.add x 5 3;;
- : unit = ()
# Hashtbl.add x 7 2;;
- : unit = ()
# Array.of_list (Hashtbl.fold (fun a b c -> (a, b) :: c) x []);;
- : (int * int) array = [|(7, 2); (5, 3)|]


You could also try inverting the Hashtbl fold into an iterator+closure 
and pass the closure into the Array.init function, but I'm not sure how 
complicated/efficient that would be.

I suppose it just depends on how efficient you need it to be. If it's 
just some simple stuff, I'd just use the intermediary list.

-e

Re: [Caml-list] generic Hashtbl.to_array

[Damien Doligez]

Hello,

On 2006-07-25, at 10:29, Christoph Bauer wrote:

> The simples idea has the problem, that you don't have
> a initial value to make the result array:

You can get it from the hash table itself:

let to_array t =
   let init = ref None in
   begin try Hashtbl.iter (fun k v -> init := Some (k,v); raise Exit) t
   with Exit -> ()
   end;
   match !init with
   | None -> [| |]
   | Some i ->
     let a = Array.make (Hashtbl.length t) i in
     ignore (Hashtbl.fold (fun k v i -> a.(i) <- (k, v); i + 1) t 0);
     a
;;

-- Damien

generic Hashtbl.to_array

[oleg]

I wonder about the following solution. At least it traverses the
hashtable exactly once (and it does not ignore the result of the
fold).


let to_array9 t =
  let Some (a,_) =
    Hashtbl.fold (fun k v seed ->
      match seed with
	Some (a,i) -> a.(i) <- (k,v); Some (a,i+1)
      | None -> let a =  Array.make (Hashtbl.length t) (k,v) in
                Some (a,1))
      t None
  in a
;;