Re: sequencing

From: Michel Quercia (quercia@cal.enst.fr)
Date: Tue Jun 03 1997 - 13:56:40 MET DST


Date: Tue, 03 Jun 1997 13:56:40 +0200
From: Michel Quercia <quercia@cal.enst.fr>
To: Jean.Luc.Paillet@lim.univ-mrs.fr
Subject: Re: sequencing

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



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:11 MET