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=0.3 required=5.0 tests=AWL,HTML_MESSAGE autolearn=disabled version=3.1.3 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id CADBBBBCA for ; Tue, 13 May 2008 00:22:15 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ag4CACRgKEhC+VLoc2dsb2JhbACCNjWPJgEMAwQECQ8FlROEXA X-IronPort-AV: E=Sophos;i="4.27,475,1204498800"; d="scan'208";a="26092117" Received: from wx-out-0506.google.com ([66.249.82.232]) by mail4-smtp-sop.national.inria.fr with ESMTP; 13 May 2008 00:22:14 +0200 Received: by wx-out-0506.google.com with SMTP id i30so2036476wxd.15 for ; Mon, 12 May 2008 15:22:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type; bh=OlbvHHgJvScXkXigihp6YuA1L7Igr7jdxq4O32JMonQ=; b=MCp0dsoR4e5B4p0T7VlPdxxBrbZjyjkdo/xJSeeU2BCABNPfGoyuDFaU2GuDHIwQZUUmhz3ldLAywsJCQciaC/+5lSADJAHrAuAjvaKhWjHMofpGInEU7FZ2DvXp5Ca7+/W90UXO8GLAB8SLN9zmIWKoMJNz8Dd+2gdBG4ge19c= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:mime-version:content-type; b=rgqmuOoKOKvPqHBFF/mw4yF7TJc4fOlBH5L9wHFN23W/O3OH7tPB7RlRWaP5Y40Mwy2mSvOIu511WFtFPv+Jy1xVlK9Ru1sh6ioqHsVwJhx9CXjXAMJfDkE+SihUnHO+UVpH5JOV+25B6rxUNqkTUG+Synz7IaVjBObBykSLHgQ= Received: by 10.100.41.8 with SMTP id o8mr9038361ano.82.1210630933763; Mon, 12 May 2008 15:22:13 -0700 (PDT) Received: by 10.100.216.8 with HTTP; Mon, 12 May 2008 15:22:13 -0700 (PDT) Message-ID: Date: Mon, 12 May 2008 18:22:13 -0400 From: "Jacques Le Normand" To: "caml-list caml-list" Subject: polymorphic recursion clarification MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_9942_4182762.1210630933762" X-Spam: no; 0.00; recursion:01 recursion:01 val:01 subtype:01 val:01 subtype:01 polymorphic:01 polymorphic:01 rec:01 rec:01 match:02 match:02 jacques:03 element:03 element:03 ------=_Part_9942_4182762.1210630933762 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline maybe I should state why I need polymorphic recursion consider the function traverse which takes a function and an element of what I want to traverse and returns a list of results. let rec traverse f n= let ret = f n in let rest = match n#get_right_sibling_specific with None -> [] | Some y -> traverse f y in let rest2 = match n#get_child_specific with None -> [] | Some y -> traverse f y in match ret with None -> rest @ rest2 | Some y -> y :: rest @ rest2 with type val traverse : ((< get_child_specific : 'a option; get_right_sibling_specific : 'a option; .. > as 'a) -> 'b option) -> 'a -> 'b list the problem is that get_child_specific may not return an 'a option, but it will always return a subtype of 'a option. is there any way to do this? ie, give it a type ((< get_child_specific : #'a option; get_right_sibling_specific : #'a option; .. > as 'a) -> 'b option) -> 'a -> 'b list ? (I believe this can be done with polymorphic recursion) --Jacques ------=_Part_9942_4182762.1210630933762 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline maybe I should state why I need polymorphic recursion
consider the function traverse which takes a function and an element of what I want to traverse and returns a list of results.

let rec traverse f n=
  let ret = f n in
  let rest = match n#get_right_sibling_specific with
      None -> []
    | Some y -> traverse f y
  in
  let rest2 = match n#get_child_specific with
      None -> []
    | Some y -> traverse f y
  in
    match ret with
    None -> rest @ rest2
      | Some y -> y :: rest @ rest2


with type

val traverse :
  ((< get_child_specific : 'a option; get_right_sibling_specific : 'a option;
      .. >
    as 'a) ->
   'b option) ->
  'a -> 'b list
 
the problem is that get_child_specific may not return an 'a option, but it will always return a subtype of 'a option. is there any way to do this? ie, give it a type

((< get_child_specific : #'a option; get_right_sibling_specific : #'a option;
      .. >
    as 'a) ->
   'b option) ->
  'a -> 'b list

? (I believe this can be done with polymorphic recursion)
--Jacques
------=_Part_9942_4182762.1210630933762--