From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <bhurt@janestcapital.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id DCF95BC69
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 15:36:34 +0100 (CET)
Received: from smtp.janestcapital.com (www.janestcapital.com [66.155.124.107])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LEaXPB000926
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 15:36:34 +0100
Received: from [192.168.250.117] [209.213.205.130] by janestcapital.com with ESMTP
  (SMTPD-9.10) id A8ED0178; Wed, 21 Feb 2007 09:36:29 -0500
Message-ID: <45DC58ED.6080103@janestcapital.com>
Date: Wed, 21 Feb 2007 09:36:29 -0500
From: Brian Hurt <bhurt@janestcapital.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: Fernando Alegre <fernando@cc.gatech.edu>
Cc: Erik de Castro Lopo <mle+ocaml@mega-nerd.com>,
	caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Combinatorics in a functional way
References: <20070221203603.e222647a.mle+ocaml@mega-nerd.com> <20070221134635.GA28981@gaia.cc.gatech.edu>
In-Reply-To: <20070221134635.GA28981@gaia.cc.gatech.edu>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Miltered: at concorde with ID 45DC58F1.003 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; bool:01 accum:01 accum:01 okasaki:01 rec:01 rec:01 caml-list:01 tail:01 tail:01 append:02 append:02 match:02 functional:02 functional:02 arg:03 

A good, functional, generic solution:

type 'a queue = 'a list * 'a list;;

let init lst : 'a queue = lst, [];;

let is_empty : 'a queue -> bool = function
    | [], [] -> true
    | _ -> false
;;

let rem_head : 'a queue -> 'a * 'a queue = function
    | (h::t), b -> h, (t, b)
    | [], b ->
        match (List.rev b) with
        | h :: t -> h, (t, [])
        | [] -> invalid_arg "rem_head on empty queue!"
;;

let append_tail ((s, b) : 'a queue) x : 'a queue = s, (x :: b);;

let fold_permute_list f accum lst =
    let rec loop1 acc t q n =
        if is_empty q then
            f acc (List.rev t)
        else
            let rec loop2 acc q i =
                if i == 0 then
                    acc
                else
                    let h, q = rem_head q in
                    let acc = loop1 acc (h :: t) q (n-1) in
                    loop2 acc (append_tail q h) (i-1)
            in
            loop2 acc q n
    in
    loop1 accum [] (init lst) (List.length lst)
;;

Okasaki should be required reading.

Brian