From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA21972 for caml-red; Mon, 16 Oct 2000 09:50:45 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA21259 for <caml-list@pauillac.inria.fr>; Mon, 16 Oct 2000 08:59:09 +0200 (MET DST)
Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e9G6x7P09795
	for <caml-list@inria.fr>; Mon, 16 Oct 2000 08:59:08 +0200 (MET DST)
Received: from localhost (sansho.kurims.kyoto-u.ac.jp [130.54.16.90])
	by kurims.kurims.kyoto-u.ac.jp (8.9.3/3.7W) with ESMTP id PAA29053;
	Mon, 16 Oct 2000 15:58:47 +0900 (JST)
To: proff@iq.org
Cc: caml-list@inria.fr
Subject: Re: list composition functions
In-Reply-To: Your message of "16 Oct 2000 10:42:03 +1100"
	<wxg0lxisdw.fsf@foo.iq.org>
References: <wxg0lxisdw.fsf@foo.iq.org>
X-Mailer: Mew version 1.93 on Emacs 20.7 / Mule 4.0 (HANANOEN)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <20001016155741M.garrigue@kurims.kyoto-u.ac.jp>
Date: Mon, 16 Oct 2000 15:57:41 +0900
From: Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>
X-Dispatcher: imput version 980905(IM100)
Sender: weis@pauillac.inria.fr

From: Julian Assange <proff@iq.org>

> Imagine you have the follow three functions,
> 
> let mirror x = [x;x]
> let plus1 x = [x+1]
> let none x = []
> 
> I'm trying to define an operator (>>) that will then operate like so
> 
> (mirror >> mirror >> plus1) [1]
> 
> [2;2;2;2]
> 
> let (>>) a b l = List.flatten (List.map b (List.flatten (List.map a l)))
> 
> # (>>);;
> - : ('a -> 'b list) -> ('b -> 'c list) -> 'a list -> 'c list = <fun>
> 
> While this looks okay, and works fine for two applications, the list
> type keeps on growing with each partial application.
> 
> plus1 >> plus1 >> plus1 >> plus1;;
> - : int list list list -> int list = <fun>
> # 
> 
> Is there anyway I can prevent this, short of making plus1, etc symmetric
> with respect to their argument types?

The problem is that your (a >> b) does not bear any symmetry with the
argument functions.
I can see at least two candidates for this.
1) The bind of the non-determinism monad:
   # let (>>) l f = List.flatten (List.map f l);;
   val ( >> ) : 'a list -> ('a -> 'b list) -> 'b list = <fun>
   # [1] >> mirror >> mirror >> plus1;;
   - : int list = [2; 2; 2; 2]
2) Flattening composition
   # let (>>) a b x = List.flatten (List.map b (a x));;
   val ( >> ) : ('a -> 'b list) -> ('b -> 'c list) -> 'a -> 'c list = <fun>
   # (mirror >> mirror >> plus1) 1;;
   - : int list = [2; 2; 2; 2]

They both slightly differ from what you were asking for, but I see no
other way to proceed as long as your basic blocks have type ('a -> 'b
list).

Jacques Garrigue