This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Doing the transition from imperative to functional (and some other Q)
• Christian Schaller
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Christian Schaller Subject: [Caml-list] Doing the transition from imperative to functional (and some other Q)
```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

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

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

```