Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: the great split up
Message-ID: <3176@munnari.oz.au>
Date: 13 Feb 90 02:12:11 GMT
References: <EIVERSON.90Feb11221732@hades.nmsu.edu>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Distribution: comp
Organization: Comp Sci, University of Melbourne
Lines: 65

In article <EIVERSON.90Feb11221732@hades.nmsu.edu> eiverson@nmsu.edu (Eric Iverson) writes:
>
>Here is a split routine I wrote.  Think of it as one string acting as
>a catalyst to split another string in two.  If you can think of a
>better, more efficient way to do it, please let me know.  This is for
>Quintus Prolog and is going to be called many many times.
>
% split(Cat,String,A,B) binds Cat onto String and splits it into A and B.
% String is split at the center of Cat.
	% eg split([a,b], [x,a,b,z], [x,a], [b,z])
split(Cat, String, A, B) :-
	built_template(Cat, TS, TA, TB),
	match_template(String, TS, TA, TB, A, B).

	% uses templates to match string and return
	% bits which are wanted
	% if TS matches with (front of) String
	%    TA is (tail of) A, and
	%    TB is B
match_template(TS, TS, TA, TB, TA, TB).
match_template(S.String, TS, TA, TB, S.A, B) :-
	match_template(String, TS, TA, TB, A, B).

	% builds templates from Cat, for use above
	% eg, if Cat = a.b.c.d.[]
	%	TS = a.b.c.d.Tail,
	%	TA = a.b.[],
	%	TB = c.d.Tail
built_template(Cat, TS, TA, TB) :-
	half_length(Cat, HLen),
	built_template_len(HLen, Cat, TS, TA, TB).

	% as above but has length to split Cat
built_template_len(0, Cat, Tail, [], Tail).
built_template_len(s(HLen), C.Cat, C.TS, C.TA, TB) :-
	built_template_len(HLen, Cat, TS, TA, TB).

	% returns half length of Cat (rounded up)
	% uses s(s(0)) notation
half_length([], 0).
half_length(C.Cat, s(HLen)) :-
	half_length_1(Cat, HLen).

	% as above, but rounds down
half_length_1([], 0).
half_length_1(C.Cat, HLen) :-
	half_length(Cat, HLen).


The code is longer than the previous version, but should be faster
and use less space.

The computation of half the length of Cat is done only once.
This computation uses a constant amount of stack space (compared with
O(Length_of_Cat) in the previous version) since it only uses tail
recursion.  No choice points are created at this stage (this is possible
because the length is represented using successor notation, rather than
Prolog integers and hence clause indexing can be used), and hence no cuts
are needed (the previous version had some unnecessary cuts also).

The matching process, and construction of A and B, is all done by a
single unification (with nice use of a logic variable in the templates),
instead of several procedure calls.

	lee