list composition functions

list composition functions

[Julian Assange]

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 = function x ->
  let rec loop = function
      [] -> []
    | hd::tl ->
	let rec loop2 = function
	    [] -> loop tl
	  | hd::tl -> b hd @ loop2 tl
	in
	  loop2 (a hd)
  in
    loop x

# (>>);;
- : ('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?

Re: list composition functions

[Jacques Garrigue]

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

Re: list composition functions

[Alain Frisch]

On 16 Oct 2000, Julian Assange wrote:
> 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]

You could try something like:

let build_transformer f x =
    List.concat (List.map f x)

let (>>) t1 t2 x =
    t1 (t2 x)

let mirror = build_transformer (fun x -> [x;x])
let plus1  = build_transformer (fun x -> [x+1])
let none   = build_transformer (fun x -> [])


(mirror and none are not generalized since their definition
is expansive)


-- 
  Alain Frisch

Re: list composition functions

[Julian Assange]

> On 16 Oct 2000, Julian Assange wrote:
> 
> You could try something like:
> 
> let build_transformer f x =
>     List.concat (List.map f x)
> 
> let (>>) t1 t2 x =
>     t1 (t2 x)

The problem with this is that it builds an intermediary list at each stage,
before handing it to the next. The function that I used does not.

Cheers,
Julian.