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

["Christian Schaller" <Christian.Schaller@siemens.com>]

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