Re: list composition functions

[Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>]

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