From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id C84CC7EE0C for ; Wed, 28 Nov 2012 18:26:23 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.210.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.210.182 as permitted sender) identity=mailfrom; client-ip=209.85.210.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ia0-f182.google.com) identity=helo; client-ip=209.85.210.182; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-ia0-f182.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsoBAMRItlDRVdK2m2dsb2JhbABFwA4IFg4BAQEBAQgJCwkUJ4IeAQEFJxkBGx4DDAYQDS4iAREBBQEcBhOHfAEDD6A5jDOCeoUEChknDVmIdQEFDIwzhEEDlgGJSoUaFimEEg X-IronPort-AV: E=Sophos;i="4.84,179,1355094000"; d="scan'208";a="164112846" Received: from mail-ia0-f182.google.com ([209.85.210.182]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Nov 2012 18:26:22 +0100 Received: by mail-ia0-f182.google.com with SMTP id x2so17571325iad.27 for ; Wed, 28 Nov 2012 09:26:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=31EK7OSLMefr29u14UUYDTzqyL6ZXUDlaMrGD4+vpJU=; b=KIBblbRld0bpVWydvVkLmZbJ4AkhdJv7BH17WHMxAq6PFjpLUu3nA5CvbrpIzHrs87 7GK9jARulv7ytvguhjXzMOC/wkav3Ed1/DBQun6rIphinUyAJWw5d9Oo2vCEZg9T02ZQ FFS4Q2JkXOZUpkoBrjy1U2qN+TkZmnmpRT6ngBzO8nqphTFWoe7m6+nZKxivfY+GAm4b QG488TZxf1/TdcFIwmJgcU3v9oRrah05lBjxIMBZNVcWbKJoJQcYycSgTYhhT0fQ90PW MGMVs9iacRECAh9tuAMdesqwy8ZvEZueWdFUd4bEfoEEi4T8mQAiAx+HfeE4e+GEmKC7 rFVA== Received: by 10.50.202.73 with SMTP id kg9mr22691616igc.51.1354123581816; Wed, 28 Nov 2012 09:26:21 -0800 (PST) MIME-Version: 1.0 Received: by 10.50.184.199 with HTTP; Wed, 28 Nov 2012 09:25:41 -0800 (PST) In-Reply-To: References: <50B595A4.50402@wwayneb.com> From: Gabriel Scherer Date: Wed, 28 Nov 2012 18:25:41 +0100 Message-ID: To: caml users Content-Type: text/plain; charset=ISO-8859-1 Subject: [Caml-list] List.fold_left vs. Hashtbl.fold (Sorry for duplicate send.) There are two exported way to fold over lists: fold_left : ('acc -> 'e -> 'acc) -> ('acc -> 'e list -> 'acc) fold_right : ('e -> 'acc -> 'acc) -> ('e list -> 'acc -> 'acc) The _left and _right suffixes indicate whether the "accumulator" argument (the partial result of what has been folded so far) is passed as the left or the right parameter of the function argument: ('acc -> 'e -> 'acc) for left, ('e -> 'acc -> 'acc) for right. The return type of fold then lifts this argument type from processing an element to processing the whole list: the initial 'acc value for is passed "on the left" for fold_left (before the list argument), "on the right" for fold_right (after the list argument). That's for the type. Regarding the implementation, fold_left applies the argument function starting from "the left" (the beginning) of the list first, while fold_right begins "on the right" (at the end): for some infix operator (++) : fold_left (++) init [x; y; z] is ((init ++ x) ++ y) ++ z fold_right (++) [x; y; z] init is (x ++ (y ++ (z ++ init))) (The evaluation "begins" in the innermost nested parentheses) Those two iterations techniques are available for linear data structures (those that essentially look like lists). For more general algebraic datatypes there is a canonical "folding" method, that happens to coincide with fold_right on lists. The reason why fold_right is "canonical" is that it turns the list x :: (y :: (z :: [])) into (x ++ (y ++ (z ++ init))) replacing each constructor with a passed-in operator. This means that fold_left may not exist for arbitrary data structure (think of binary trees), while fold_right is rather universal. Other folding functions in the standard library (in Set and Map in particular, but in Hashtbl as well) have therefore taken inspiration from the fold_right structure, rather than fold_left. On Wed, Nov 28, 2012 at 5:40 AM, William Smith wrote: > > Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd > parameter being the initial value... just the opposite of List.fold_left.