From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA18191; Wed, 4 Feb 2004 18:40:37 +0100 (MET)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA19556 for <caml-list@pauillac.inria.fr>; Wed, 4 Feb 2004 18:40:36 +0100 (MET)
Received: from smtp.mbg.ocn.ne.jp (mbg.ocn.ne.jp [210.190.142.181])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i14HeZv12294
	for <caml-list@inria.fr>; Wed, 4 Feb 2004 18:40:35 +0100 (MET)
Received: from localhost (p2205-adsau14hon-acca.tokyo.ocn.ne.jp [220.111.162.205])
	by smtp.mbg.ocn.ne.jp (Postfix) with ESMTP
	id 94F2A673A; Thu,  5 Feb 2004 02:40:33 +0900 (JST)
Date: Thu, 05 Feb 2004 02:36:33 +0900 (JST)
Message-Id: <20040205.023633.26267951.yoriyuki@mbg.ocn.ne.jp>
To: Christian.Schaller@siemens.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Doing the transition from imperative to functional
 (and some other Q)
From: Yamagata Yoriyuki <yoriyuki@mbg.ocn.ne.jp>
In-Reply-To: <A1364BC6814D92479D4EED572D6F6FD8069587@uranus.certw2k.net>
References: <A1364BC6814D92479D4EED572D6F6FD8069587@uranus.certw2k.net>
X-Mailer: Mew version 2.2 on Emacs 21.2 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; caml-list:01 yamagata:01 yoriyuki:01 yoriyuki:01 schaller:01 schaller:01 caml-list:01 2004:99 recursion:01 -bits:01 -bits:01 lxor:01 hash:01 char:01 lxor:01 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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