Re: "ocaml_beginners"::[] Is ocaml smart on memory usage here?

roparzhhemon wrote:
&gt; --- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, Jon Harrop <jon...> wrote:
&gt;
>>; The only notable exception to this rule crops up when you're traversing trees.
>>; Consider a function to substitute a value for a variable name in a symbolic
>>; expression:
>>;
>>; # let rec subst var value = function
>> | `Add(f, g) -> `Add(subst var value f, subst var value g)
>&gt; | `Mul(f, g) -> `Mul(subst var value f, subst var value g)
>&gt; | `Int n -> `Int n
>&gt; | `Var v when v=var -> value
&gt;> | `Var v -> `Var v;;
>> val subst :
>&gt; 'a ->
&gt;> ([> `Add of 'b * 'b | `Int of 'c | `Mul of 'b * 'b | `Var of 'a ] as 'b) ->
&gt;> ([< `Add of 'd * 'd | `Int of 'c | `Mul of 'd * 'd | `Var of 'a ] as 'd) ->
&gt;> 'b = <fun>;
>>;
>>; This function might look ok but it is actually hugely inefficient because it
>>; copies the entire tree, even if no substitution is made.
&gt;>
>
> But is there a more efficient implementation in this case ?
>
> Ewan
>;
>
Yes, for instance the line

| `Var v -> `Var v;;

reconstructs a value from the existing one (and thus makes a copy), a cost you can avoir by writing

| `Var v as x -> x;;

so that it should be possible to return the original value when no substitution is made. OTOH, if substitutions are made, the part of the tree above the substitutions has to be copied, if you are working with immutable fields.

Frédéric vdP

Messages in this topic (8) Reply (via web post) | Start a new topic

.

On 2/14/07, Frédéric van der Plancke < fvdp%40decis.be">fvdpdecis.be&gt; wrote:
&gt; roparzhhemon wrote:
&gt; > --- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, Jon Harrop <jon...> wrote:
&gt; >
>; >> The only notable exception to this rule crops up when you're traversing trees.
&gt; >> Consider a function to substitute a value for a variable name in a symbolic
> >> expression:
> >>
> >> # let rec subst var value = function
> >> | `Add(f, g) -> `Add(subst var value f, subst var value g)
> >> | `Mul(f, g) -> `Mul(subst var value f, subst var value g)
> >> | `Int n -> `Int n
> >> | `Var v when v=var -> value
&gt; >> | `Var v -> `Var v;;
> >> val subst :
> >> 'a ->
&gt; >> ([> `Add of 'b * 'b | `Int of 'c | `Mul of 'b * 'b | `Var of 'a ] as 'b) ->
&gt; >> ([< `Add of 'd * 'd | `Int of 'c | `Mul of 'd * 'd | `Var of 'a ] as 'd) ->
&gt; >> 'b = <fun>;
> >>
> >> This function might look ok but it is actually hugely inefficient because it
> >> copies the entire tree, even if no substitution is made.
&gt; >>
> >
>; > But is there a more efficient implementation in this case ?
> >
>; >
>; Yes, for instance the line
>;
> | `Var v -> `Var v;;
>
> reconstructs a value from the existing one (and thus makes a copy), a cost you can avoir by writing
>
> | `Var v as x -> x;;
>
> so that it should be possible to return the original value when no substitution is made. OTOH, if substitutions are made, the part of the tree above the substitutions has to be copied, if you are working with immutable fields.
>
To expand on this, you need to communicate whether a substitution was
made, for example with a variant:

let rec subst var value = function
| `Add(f, g) ->
(match subst var value f, subst var value g with
None, None -> None
| Some a1, None -> Some (`Add (a1, g))
| None, Some a2 -> Some (`Add (f, a2))
| Some a1, Some a2 -> Some (`Add (a1, a2))
)
| `Mult(f, g) ->
(match subst var value f, subst var value g with
None, None -> None
| Some a1, None -> Some (`Mult (a1, g))
| None, Some a2 -> Some (`Mult (f, a2))
| Some a1, Some a2 -> Some (`Mult (a1, a2))
)
| `Int n -> None
| `Var v when v=var -> Some value
| `Var v -> None;;

This way only substitution paths are copied.

Best wishes,
Lukasz

Messages in this topic (9) Reply (via web post) | Start a new topic

.