[m-rev.] for review: add transform_value predicate to map.

Julien Fischer juliensf at cs.mu.OZ.AU
Wed Jan 12 19:54:04 AEDT 2005


On Wed, 12 Jan 2005, Ian MacLarty wrote:

> For review by anyone.
>
> Estimated hours taken: 2
> Branches: main
>
> Add transform_value predicate to map, tree234 and rbtree.  This applies

I suggest: Add the operation transform_value to ....
(since there are both predicate and function versions).

> a higher order argument to a value in the map.  Often a value needs to be
> updated using its previous value, currently requiring two lookups of the
> key.  With transform_value only one lookup is required.
>
Make the last bit here a separate sentence, e.g.

	This currently reuiqres two lookups of the key.  etc

> NEWS
> 	Mention the new predicate.
>
> library/map.m
> library/rbtree.m
> library/tree234.m
> 	Add transform_value.
>
> library/require.m
> 	Add a version of report_lookup_error that doesn't take a value
> 	argument, since the value argument is not available in transform_value.
>

> Index: NEWS
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/NEWS,v
> retrieving revision 1.360
> diff -u -r1.360 NEWS
> --- NEWS	11 Jan 2005 06:06:14 -0000	1.360
> +++ NEWS	12 Jan 2005 07:32:41 -0000
> @@ -234,7 +234,7 @@
>    variables.  We've also added a function version.
>
>  * We've added some new predicates, map__common_subset, map__foldl3,
> -  and map__overlay_large_map, to map.m.
> +  map__overlay_large_map and map__transform_value, to map.m.
>
>  * We've added a predicate, map_fold, to set.m.
>
This doesn't mention the changes to the rbtree module.

> Index: library/map.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/map.m,v
> retrieving revision 1.93
> diff -u -r1.93 map.m
> --- library/map.m	10 Jan 2005 05:23:46 -0000	1.93
> +++ library/map.m	12 Jan 2005 02:25:33 -0000
> @@ -124,6 +124,20 @@
>  :- pred map__det_update(map(K, V)::in, K::in, V::in, map(K, V)::out) is det.
>  :- func map__det_update(map(K, V), K, V) = map(K, V).
>
> +	% Update the value at the given key by applying the supplied
> +	% transformation to it.  Fails if the key is not found.  This is faster
> +	% that first searching for the value and then updating it.
> +	%
e/that/than/ above

> +:- pred map__transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
> +	map(K, V)::in, map(K, V)::out) is semidet.

I think you should also add a mode where the closure is semidet.

> +
> +	% Same as transform_value/4, but aborts instead of failing if the
> +	% key is not found.
> +	%

I prefer "throws an exception" to "aborts"

> +:- pred map__det_transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
> +	map(K, V)::in, map(K, V)::out) is det.
> +:- func map__det_transform_value(func(V) = V, K, map(K, V)) = map(K, V).
> +

Our current coding standards say that if there is both a predicate
and a function version of a procedure then the :- func declaration
should appear first.

>  	% Update value if the key is already present, otherwise
>  	% insert new key and value.
>  :- pred map__set(map(K, V), K, V, map(K, V)).
> @@ -563,6 +577,23 @@
>  	;
>  		report_lookup_error("map__det_update: key not found", K, V)
>  	).
> +
> +map__transform_value(P, K, !Map) :-
> +	tree234__transform_value(P, K, !Map).
> +
> +map__det_transform_value(P, K, !Map) :-
> +	(
> +		map__transform_value(P, K, !.Map, NewMap)
> +	->
> +		!:Map = NewMap
> +	;
> +		report_lookup_error("map__det_transform_value: key not found",
> +			K)
> +	).
> +
> +map__det_transform_value(F, K, Map0) = Map :-
> +	map__det_transform_value(pred(V0::in, V::out) is det :- V = F(V0), K,
> +		Map0, Map).
>
>  map__set(Map0, K, V, Map) :-
>  	tree234__set(Map0, K, V, Map).

> Index: library/rbtree.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/rbtree.m,v
> retrieving revision 1.17
> diff -u -r1.17 rbtree.m
> --- library/rbtree.m	11 Nov 2004 13:46:40 -0000	1.17
> +++ library/rbtree.m	12 Jan 2005 02:44:45 -0000
> @@ -15,6 +15,9 @@
>  %	fails if key already in tree.
>  % update:
>  %	changes value of key already in tree.  fails if key doesn't exist.
> +% transform_value:
> +%	looks up an existing value in the tree, applies a transformation to the
> +%	value and then updates the value.  fails if the key doesn't exist.
>  % set:
>  %	inserts or updates. Never fails.
>  %
> @@ -63,6 +66,13 @@
>  :- pred rbtree__update(rbtree(K, V)::in, K::in, V::in, rbtree(K, V)::out)
>  	is semidet.
>
> +	% Update the value at the given key by applying the supplied
> +	% transformation to it.  Fails if the key is not found.  This is faster
> +	% that first searching for the value and then updating it.
> +	%
Again s/that/than/

...

> Index: library/require.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/require.m,v
> retrieving revision 1.31
> diff -u -r1.31 require.m
> --- library/require.m	13 Nov 2003 17:06:11 -0000	1.31
> +++ library/require.m	11 Jan 2005 08:23:22 -0000
> @@ -50,6 +50,15 @@
>  %		Key and Value.  The error message will include Message
>  %		and information about Key and Value.
>
> +:- pred report_lookup_error(string, K).
> +:- mode report_lookup_error(in, in) is erroneous.
> +
You should use predmode syntax there.

> +%	report_lookup_error(Message, Key)
> +%		Call error/1 with an error message that is appropriate for
> +%		the failure of a lookup operation involving the specified
> +%		Key.  The error message will include Message
> +%		and information about Key.
> +
Ideally the documentation should be above the predicate declaration but
since the rest of this module uses that style you should probably leave
it as is.

>  %-----------------------------------------------------------------------------%
>
>  :- implementation.
> @@ -84,6 +93,25 @@
>  		FunctorStr,
>  		"\n\tValue Type: ",
>  		ValueType
> +		],
> +		ErrorString),
> +	error(ErrorString).
> +
> +report_lookup_error(Msg, K) :-
> +	KeyType = type_name(type_of(K)),
> +	functor(K, Functor, Arity),
> +	( Arity = 0 ->
> +		FunctorStr = Functor
> +	;
> +		string__int_to_string(Arity, ArityStr),
> +		string__append_list([Functor, "/", ArityStr], FunctorStr)
> +	),
> +	string__append_list(
> +		[Msg,
> +		"\n\tKey Type: ",
> +		KeyType,
> +		"\n\tKey Functor: ",
> +		FunctorStr
>  		],
>  		ErrorString),
>  	error(ErrorString).
> Index: library/tree234.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/library/tree234.m,v
> retrieving revision 1.44
> diff -u -r1.44 tree234.m
> --- library/tree234.m	16 Dec 2004 03:17:28 -0000	1.44
> +++ library/tree234.m	11 Jan 2005 08:08:11 -0000
> @@ -115,6 +115,13 @@
>  % :- mode tree234__update(di_tree234, in, in, uo_tree234) is det.
>  % :- mode tree234__update(di, di, di, uo) is semidet.
>
> +	% Update the value at the given key by applying the supplied
> +	% transformation to it.  This is faster that first searching for
> +	% the value and then updating it.
> +	%
> +:- pred tree234__transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
> +	tree234(K, V)::in, tree234(K, V)::out) is semidet.
> +
>  	% count the number of elements in a tree
>  :- pred tree234__count(tree234(K, V), int).
>  :- mode tree234__count(in, out) is det.
> @@ -774,6 +781,104 @@
>  			;
>  				Result2 = (>),
>  				tree234__update(T3, K, V, NewT3),
> +				Tout = four(K0, V0, K1, V1, K2, V2,
> +					T0, T1, T2, NewT3)
> +			)
> +		)
> +	).
> +

What is this change here?

Cheers,
Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------



More information about the reviews mailing list