From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.1 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 706DCBC6C for ; Thu, 31 Jan 2008 19:18:59 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFqgoUdIDtbneWdsb2JhbACQIgEBCQQECwYTl2qBbw X-IronPort-AV: E=Sophos;i="4.25,286,1199660400"; d="scan'208";a="7484253" Received: from discorde.inria.fr ([192.93.2.38]) by mail1-smtp-roc.national.inria.fr with ESMTP; 31 Jan 2008 19:18:59 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m0VIIx1g013427 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Thu, 31 Jan 2008 19:18:59 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFqgoUdIDtbneWdsb2JhbACQIgEBCQQECwYTl2qBbw X-IronPort-AV: E=Sophos;i="4.25,286,1199660400"; d="scan'208";a="7484252" Received: from hu-out-0506.google.com ([72.14.214.231]) by mail1-smtp-roc.national.inria.fr with ESMTP; 31 Jan 2008 19:18:58 +0100 Received: by hu-out-0506.google.com with SMTP id 16so494827hue.7 for ; Thu, 31 Jan 2008 10:18:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=BEEcDB/AOucOXLv20uAjdi7/ePCKJ7w8GkAwnVpCKRU=; b=SMiYDD5POZVZWWPErpCypwVgyH/qspf93BVOcwEQCt2LYmsI3coZO882L2FxSwUc/QTWMRWeszQs8LpaWfsGQDMXuePgtEotVvjAt7s47Z3ISELgW/6lGhY6ZFRX8/oiR06Of2M2B2uT0MGgFZG8T9Bjo8dvyw1tVvo3MATbNcI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=Bd1NudzHDJKzt2G6uGVUO0eYXA/SY8T47yvKXQBzE2F+Pqr0c+yO9AopQd7xqZZEdO/OCpIEKR/ybUwet4meAwP9OjyLlGIDJkGZnUnZ2UWYFdu6sxbcQWdo4cD4xbXwX2PLlLqNJN7CnpKf0NPjV94gLt2aaT/atRbqQlgqyhQ= Received: by 10.78.160.2 with SMTP id i2mr3930027hue.53.1201803537801; Thu, 31 Jan 2008 10:18:57 -0800 (PST) Received: by 10.78.156.14 with HTTP; Thu, 31 Jan 2008 10:18:57 -0800 (PST) Message-ID: <4a051d930801311018k6aa4b8bdge32400c6a36b9b78@mail.gmail.com> Date: Thu, 31 Jan 2008 13:18:57 -0500 From: "Christopher L Conway" Sender: christopherleeconway@gmail.com To: caml-list Subject: Re: [Caml-list] Induction over types In-Reply-To: <47A20799.4030706@wp.pl> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <47A20799.4030706@wp.pl> X-Google-Sender-Auth: faefd470ba8c455f X-Miltered: at discorde with ID 47A21113.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; runtime:01 ocaml:01 haskell:01 non-trivial:01 invokes:01 ocaml:01 'a-:01 val:01 val:01 beginner's:01 bug:01 scrap:98 polymorphic:01 beginners:01 wrote:01 Dawid, Your example seems to require dependent types (e.g., "nested lists of depth k") or runtime type inspection. Neither is directly supported by OCaml (although there might be experimental extensions out there that do what you want). You might be interested the "Scrap Your Boilerplate" approach which is available in the latest versions of Haskell (http://www.cs.vu.nl/boilerplate). I think this would accomplish what you're asking. But it's implementation and use is non-trivial. Chris On Jan 31, 2008 12:38 PM, Dawid Toton wrote: > I want to write a polymorphic function that invokes itself recursively, > but with different types. > For example I'd like to translate the following pseudo-code into OCaml: > > let rec deep_rev (lst:'a list) = List.rev (List.map (deep_rev:'a->'a) lst) > let deep_rev (element:'a) = element (* initial induction step *) > > let rec super_wrap (depth:int) (lst:'a list) = > match depth with > | 0 -> lst > | d -> super_wrap (d+1) [lst] > > And how can I have arbitrary transposition: > > val transpose: int list -> 'a list -> 'a list > > # transpose [2;0;1] > [[[1;2];[3;4]] > ;[[5;6];[7;8]] > ] > - : int list list list = [[[1; 3]; [5; 7]]; [[2; 4]; [6; 8]]] > > Do I have to have separate functions: > > val transpose1: int list -> 'a list -> 'a list (* identity *) > val transpose2: int list -> 'a list list -> 'a list list > val transpose3: int list -> 'a list list list -> 'a list list list > ... > > But this is huge amount of redundant code! > Here is for example my transpose3: > http://www.toton.2-0.pl/OCaml/transpose.ml > > Dawid Toton > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > >