"ocamler" way?

being somewhat new to functional languages i'm just doing alot of looking at
code snippets to wrap my head around the ocaml way of doing things. i've been
using the great language shootout's page (http://shootout.alioth.debian.org/)
since i can compare snippets with languages i already understand. looking at
this snippet

(*
* $Id: hash.ocaml,v 1.1.1.1 2004/05/19 18:09:55 bfulgham Exp $
* http://www.bagley.org/~doug/shootout/
* with help from Markus Mottl
*)

let hexdigits = [| '0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9';
'a'; 'b'; 'c'; 'd'; 'e'; 'f'; |]

let buf = String.create 32

let rec hexstring_of_int idx len = function
| n when n <= 0 -> String.sub buf idx len
| n ->
let new_idx = idx - 1 in
buf.[new_idx] <- hexdigits.(n land 15);
hexstring_of_int new_idx (len + 1) (n lsr 4);;

let n = if Array.length Sys.argv > 1 then int_of_string Sys.argv.(1) else 1 in
let hx = Hashtbl.create n and c = ref 0 in
for i = 1 to n do Hashtbl.add hx (hexstring_of_int 32 0 i) true done;
for i = n downto 1 do if Hashtbl.mem hx (string_of_int i) then incr c done;
Printf.printf "%d\n" !c


raised some questions:

* is 'n' in hexstring_of_int the same 'n' from

let n = if Array.length Sys.argv > 1 then int_of_string Sys.argv.(1) else 1 in

can someone give me a walk though of the hexstring_of_int method? clearly it
formats ints as hex numbers but... ;-) on that topic - why wouldn't one
simply use sprintf to generate these strings?

kind regards.


-a
--
================================================== =============================
| EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
| PHONE :: 303.497.6469
| A flower falls, even though we love it;
| and a weed grows, even though we do not love it.
| --Dogen
================================================== =============================

Ara.T.Howard schrob:
[...]

> (*
> * $Id: hash.ocaml,v 1.1.1.1 2004/05/19 18:09:55 bfulgham Exp $
> * http://www.bagley.org/~doug/shootout/
> * with help from Markus Mottl
> *)

> let hexdigits = [| '0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9';
> 'a'; 'b'; 'c'; 'd'; 'e'; 'f'; |]

> let buf = String.create 32

> let rec hexstring_of_int idx len = function
> | n when n <= 0 -> String.sub buf idx len
> | n ->
> let new_idx = idx - 1 in
> buf.[new_idx] <- hexdigits.(n land 15);
> hexstring_of_int new_idx (len + 1) (n lsr 4);;

> let n = if Array.length Sys.argv > 1 then int_of_string Sys.argv.(1) else 1 in
> let hx = Hashtbl.create n and c = ref 0 in
> for i = 1 to n do Hashtbl.add hx (hexstring_of_int 32 0 i) true done;
> for i = n downto 1 do if Hashtbl.mem hx (string_of_int i) then incr c done;
> Printf.printf "%d\n" !c


> raised some questions:

> * is 'n' in hexstring_of_int the same 'n' from

> let n = if Array.length Sys.argv > 1 then int_of_string Sys.argv.(1) else 1 in

> can someone give me a walk though of the hexstring_of_int method? clearly it
> formats ints as hex numbers but... ;-) on that topic - why wouldn't one
> simply use sprintf to generate these strings?

Ok, let's see:

let rec hexstring_of_int idx len = function
| n when n <= 0 -> (* A *)
| n -> (* B *)

That's equivalent to

let rec hexstring_of_int idx len n =
if n <= 0 then (* A *) else (* B *)

The n above is bound by the implicit match after "function" and
unrelated to any other n. In fact, "| n when n <= 0" and "| n" refer to
two different n's.

Hmm, that function looks weird. It uses the global "buf" as scratch
buffer, and the caller must remember to supply the length of "buf" as an
argument (that's the same "32" in String.create 32 and (hexstring_of_int
32 0 i)). Also it seems to be broken for 0 and negative arguments.

The following C code is roughly equivalent:

const char hexdigits[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
'9', 'a', 'b', 'c', 'd', 'e', 'f' };

char buf[33]; /* 32 chars plus the terminating '\0' */

const char *hexstring_of_int(int idx, int len, int n) {
if (n <= 0) {
return buf + idx; /* length is implicit; '\0' marks the spot */
}
buf[idx - 1] = hexdigits[n & 15];
return hexstring_of_int(idx - 1, len + 1, n >> 4);
}

Notes: This code doesn't make a copy of the buffer, and it doesn't need
"len"; on the other hand, C's strings require a terminating null byte.
n & 15 is another way of writing n % 16 (or n mod 16 in OCaml). n >> 4
(n lsr 4) is equivalent to n / 16.

We can rewrite this recursive function to use a loop:

const char *hexstring_of_int(int idx, int len, int n) {
while (n >= 0) {
buf[idx - 1] = hexdigits[n % 16];
--idx;
++len;
n /= 16;
}
return buf + idx;
}

In other words, this function writes into buf (backwards!), then returns
what it's written. The algorithm itself is pretty simple; let's use
hexstring_of_int(32, 0, 127) as an example:

n = 127 is greater than 0, so we compute n % 16 (that's 15), look it up
in hexdigits (that's 'f'), and write the result into buf[idx - 1]
(buf[31]). We continue with hexstring_of_int(idx - 1, len + 1, n / 16),
so now idx = 31, len = 1, n = 7.

n = 7 is greater than 0, so we compute n % 16 (7), look it up in
hexdigits ('7'), and write the result into buf[idx - 1] (buf[30]). We
continue with hexstring_of_int(idx - 1, len + 1, n / 16), so now idx =
30, len = 2, n = 0.

n = 0 is not greater than 0, so we return the len = 2 characters at
index idx = 30 of buf: "7f". We're done.

If I were to write this function myself, I'd do it like this:

let rec hexstring_of_int =
let hexdigits = "0123456789abcdef" in
function n ->
if n < 0 then
"-" ^ hexstring_of_int (-n)
else
(
if n / 16 <> 0 then hexstring_of_int (n / 16) else ""
) ^ String.sub hexdigits (n mod 16) 1
;;

Or if I had to use a buffer:

let hexstring_of_int =
let hexdigits = "0123456789abcdef" in
let buf = String.create 32 in
let rec fillbuf idx n =
if n < 0 then (
let idx_cur = fillbuf idx ~-n - 1 in
buf.[idx_cur] <- '-';
idx_cur
) else (
let idx_cur = idx - 1 in
buf.[idx_cur] <- hexdigits.[n mod 16];
if n / 16 <> 0 then
fillbuf idx_cur (n / 16)
else
idx_cur
)
in
function n ->
let pos = fillbuf (String.length buf) n in
String.sub buf pos (String.length buf - pos)
;;

This one uses a private function to make the user interface more sane.

I hope this helps you a bit.
Lukas
--
main(int v,char**c){c?main(atoi(c[--v]),0),
puts("")utchar((v/2&&main(v/2,0),48|v&1));}

On Thu, 29 Jul 2004, Lukas Mai wrote:
<snip>
> I hope this helps you a bit.

very much! i'll study and, i'm sure, have some more questions.

kind regards.

-a
--
================================================== =============================
| EMAIL :: Ara [dot] T [dot] Howard [at] noaa [dot] gov
| PHONE :: 303.497.6469
| A flower falls, even though we love it;
| and a weed grows, even though we do not love it.
| --Dogen
================================================== =============================