This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

list composition functions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Jacques Garrigue Subject: Re: list composition functions
```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

```