[Caml-list] Doing the transition from imperative to functional (and some other Q)

[Caml-list] Doing the transition from imperative to functional (and some other Q)

[Christian Schaller]

Hello,

While trying to implement a kind of CRC algorithm used for Expert
Witness (http://www.asrdata.com/SMART/whitepaper.html) I was facing a
very challenging task to implement the algorithm at the bottom of above
link in OCaml.

Well, my first try was just 1:1 translation, so I ended up with:

let crc buffer buffer_size prev_key =
  let b = ref (prev_key land 0xffff) in
  let d = ref ((prev_key lsr 16) land 0xffff) in
  for i = 0 to buffer_size - 1 do
    b := !b + int_of_char buffer.[i];
    d := !d + !b;
    if i <> 0 && ((i mod 0x15b0 = 0) || (i = buffer_size - 1)) then
    begin
      b := !b mod 0xfff1;
      d := !d mod 0xfff1;
    end
  done;
  !d lsl 16 lor !b

After I decided that there has to be a functional way for this, too,
(hate typing all those ! and := )I came up with the following version:

let crc2 buffer prev_key =
  let buffer_size = List.length buffer in
  let b = prev_key land 0xffff in
  let d = (prev_key lsr 16) land 0xffff in
  let calc (i, b,d) ch =
    let b = b + int_of_char ch in
    let d = d + b in
    if i <> 0 && ((i mod 0x15b0 = 0) || (i = buffer_size - 1)) then
      (i+1, b mod 0xfff1, d mod 0xfff1)
    else (i+1, b,d) in
  let _, b,d = List.fold_left calc (0, b,d) buffer in
  d lsl 16 lor b

Though I like the power of fold, I have the feeling that the
expressiveness suffers somewhat.  Maybe there's some more elegant
version of it?  Any comments?

Now comes the funny part.  Actually, right now I'm not sure how to
represent the buffer variable internally.  As you can see, in the first
part I chose string, because of the .[] operator.  However, I cannot use
string, because this data type doesn't have any fold function.  Right
now I do not want to make a decision about the data type used, except
that I know that it must be a sequence of characters.

Though I am a strong believer in static typing, above versions
disappoint me heavily because of type restrictions.  Is there any way to
write above version on arbitrary sequences like Arrays, Lists, Strings?

Actually, I would have preferred the buffer data type because I can use
that one for fast reading of a file.  However, I cannot fold over a
buffer :(

Any enlightening hints?

TIA,
  Chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Doing the transition from imperative to functional (and some other Q)

[Yamagata Yoriyuki]

From: "Christian Schaller" <Christian.Schaller@siemens.com>
Subject: [Caml-list] Doing the transition from imperative to functional (and some other Q)
Date: Wed, 4 Feb 2004 17:09:30 +0100

> After I decided that there has to be a functional way for this, too,
> (hate typing all those ! and := )I came up with the following version:

Using (tail) recursion is the way.  Here is a code for 31-bits CRC.
(Not exactly same to yours, but it would give you an idea.)

(* CRC-hash, algorithm comes from addnode.c/pathalias *)
(* 31-bits CRC-polynomial, by Andrew Appel*)
let poly = 0x48000000

let crc_tbl = Array.init 128 (fun i ->
  let rec loop j sum =
    if j < 0 then sum else
    if i land (1 lsl j) <> 0 then
      loop (j - 1) (sum lxor (poly lsr j))
    else
      loop (j - 1) sum in
  loop (7 - 1) 0)

let string_hash v =
  let rec loop i sum =
    if i < 0 then sum else
    let a = Char.code v.[i] in
    let sum = sum lsr 7 lxor crc_tbl.(sum lxor a land 0x7f) in
    loop (i - 1) sum in
  loop (String.length v - 1) 0

> Though I am a strong believer in static typing, above versions
> disappoint me heavily because of type restrictions.  Is there any way to
> write above version on arbitrary sequences like Arrays, Lists,
> Strings?

You could use Functor, but it would be too heavy weight.
 
> Actually, I would have preferred the buffer data type because I can use
> that one for fast reading of a file.  However, I cannot fold over a
> buffer :(

You don't need to load the whole file.  Read the file one character by
one, and updates the sum.

--
Yamagata Yoriyuki

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Doing the transition from imperative to functional (and some other Q)

[Nicolas Cannasse]

> Now comes the funny part.  Actually, right now I'm not sure how to
> represent the buffer variable internally.  As you can see, in the first
> part I chose string, because of the .[] operator.  However, I cannot use
> string, because this data type doesn't have any fold function.  Right
> now I do not want to make a decision about the data type used, except
> that I know that it must be a sequence of characters.
>
> Though I am a strong believer in static typing, above versions
> disappoint me heavily because of type restrictions.  Is there any way to
> write above version on arbitrary sequences like Arrays, Lists, Strings?
>
> Actually, I would have preferred the buffer data type because I can use
> that one for fast reading of a file.  However, I cannot fold over a
> buffer :(
>
> Any enlightening hints?

You should have a look at ExtLib Enum module that enable you to apply fold's
and others functionals operations on any underlying data structure (string,
array, list, .... ).

http://ocaml-lib.sf.net

Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners