Re: sequencing

[Michel Quercia <quercia@cal.enst.fr>]

Jean.Luc.Paillet@lim.univ-mrs.fr wrote:
> 
>    Quelqu'un pourrait-il m'expliquer pourquoi le sequencement d'une fonction
> a` effet de bord, telle que "print_string" par exemple, semble inverse'
> quand elle est appliquée sur une liste au moyen d'un iterateur.
> 
> Par exemple
>    map print_string ["a" ; "b"] ;;   produit
> 
>     ba- : unit list = [(); ()]
> ce qui implique un parcours de la liste de droite a gauche .
> Plus curieux, avec une definition recursive "personnelle" de l'iterateur,
> telle que
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;

Un coup d'oeil a la bibliotheque sur les listes
(/usr/local/lib/caml-light/list.ml) monter que map est a peu pres defini
comme cela.

> 
> On pourrait s'attendre ici a ce que  "(f head)" soit evalue avant
> l'appel recursif. He bien non,

L'ordre d'evaluation de (expr_a) :: (expr_b) n'est pas specifie dans le
manuel de reference. En pratique, il se trouve que expr_b est evalue
d'abord.
Voici une fonction lr_map produisant une application de gauche a droite
:


>       Caml Light version 0.73

#map print_char [`a`; `b`; `c`];;
cba- : unit list = [(); (); ()]
#let rec lr_map f liste = match liste with
| [] -> []
| t::q -> let t' = f(t) in t' :: (lr_map f q)
;;
lr_map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#lr_map print_char [`a`; `b`; `c`];;
abc- : unit list = [(); (); ()]
#

> **********************************************
> ££  English version  ££
> 
> I don't understand why the sequencing of side effects seems to be inverted,
> when using "map" , like for example in the following:
> 
>      map print_string ["a" ; "b"] ;;   gives
>     ba- : unit list = [(); ()]
> 
> it means that the list is scanned from the right to the left
> 
> More surprising, with a recursive hand made definition of "map", such as
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;
> 

Look at the list implementation (/usr/local/lib/caml-light/list.ml),
you'll see that map is roughly defined that way.

> 
> We could thing that   "(f head)" is evaluated before the recursive call .
> 

The order of evaluation of (expr_a) :: (expr_b) is unspecified in the
reference manual. Actually, it turns out that expr_b is evaluated first.
Here is a function lr_map going from left to right :


>       Caml Light version 0.73

#map print_char [`a`; `b`; `c`];;
cba- : unit list = [(); (); ()]
#let rec lr_map f liste = match liste with
| [] -> []
| t::q -> let t' = f(t) in t' :: (lr_map f q)
;;
lr_map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#lr_map print_char [`a`; `b`; `c`];;
abc- : unit list = [(); (); ()]
#


-- 
Michel Quercia
Lycee Carnot  16 bd Thiers  21000 Dijon
mailto:quercia@cal.enst.fr