Set of prefixes
Torbjörn Lager
I only just started programming in a functional style, and now I need to
define a function that will find the set of prefixes to a list. I'm an
old Prolog programmer, so I first tried to write a piece of
deterministic Prolog code like this:
prefixes([],[[]]).
prefixes([X|Xs],Yss) :-
prefixes(Xs,Xss1),
prefixall(Xss1,X,Yss).
prefixall([],_,[[]]).
prefixall([Xs|Xss],X,[[X|Xs]|Yss]) :-
prefixall(Xss,X,Yss).
So:
| ?- prefixes([a,b,c,d],Ps).
Ps = [[a,b,c,d],[a,b,c],[a,b],[a],[]]
There are of course simpler way to do this in Prolog if you allow
yourself to use nondeterminism. But I'm looking for a deterministic
algorithm. The above is the best I could come up with. However, it isn't
tail recursive and perhaps therefore slow? I'm ashamed to say that all
my attempts to massage it into a tail recursive program failed. Can you
see a way? Another problem from my point of view is that the empty
prefix is included in the solution. I would prefer to generate only the
list of non-empty prefixes. No matter how I tried, I couldn't find a
(nice) way to do that.
I also wrote the following in the functional style of Oz:
fun {Prefixes Xs}
case Xs
of nil then [nil]
[] X|Xs1 then
{FoldR
{Prefixes Xs1}
fun {$ Xs Yss} (X|Xs)|Yss end
[nil]}
end
end
but it encodes exactly the same algorithm, and so it suffers from the
same problems.
My questions: Is there a tail recursive solution to this? Is it likely
to be faster? Is this the kind of thing for which a solution using
arrays (from which you can take slices) is likely to be faster?
Regards,
Torbjörn
--
----------------------------------------------------------------
Torbjörn Lager Computational Linguist
Department of Linguistics Uppsala University
S-751 20 Uppsala Sweden
Phone: +46 18 471 7860 http://stp.ling.uu.se/~torbjorn/
----------------------------------------------------------------
Mark Carroll
prefixes [] = [[]]
prefixes s@(x:xs) = s : prefixes xs
I'm guessing that either this doesn't translate well to Oz or something,
or that it isn't tail recursive?
-- Mark
Mark Carroll
Ah. The latter. Does,
prefixes s =
reverse $ realprefixes s []
where
realprefixes [] a = a
realprefixes s@(x:xs) a = realprefixes xs (s:a)
look better? (I got rid of that [] you don't like at the end too.)
Or is my use of reverse too wicked?
-- Mark
Torbjörn Lager
Very neat. But I'm afraid I don't know Haskell, so I don't know what @
means... What does it do?
-- T
Torbjörn Lager
I still not quite sure what this does, but I guess that you're using an
accumulator and reverse to reverse the reversing effect of that (wow,
that came out funny... :-). If so, I guess it is debatable whether
you'll win something over the non-tail recursive version. In terms of
speed, I mean. I'm looking for the fastest way of doing this, since I'm
writing a program that does it a lot. I'm willing to use arrays if I
have to, and that's no problem, since Oz supports that too. A clean
declarative solutions would be nicer though...
-- T
Steffen Mazanek
Maybe
>prefixes [] = [[]]
>prefixes xs = [xs]++prefixes (init xs)
init [1,2,3,4] = [1,2,3]
Matthias Blume
[more snipped]
Rule of thumb: Write it "naturally" first, worry about microoptimizations later:
fun prefixes [] = [[]]
| prefixes (l as (_ :: l')) = l :: prefixes l'
This is not all bad even though it is not tail-recursive. Its complexity in
both space and time is O(length(l)), and no solution can do better than that.
But if you want to make it tail-recursive, slightly reducing temporary storage
(trading stack space for an intermediate list), here you go:
fun prefixes l = let
fun loop ([], acc) = rev acc
| loop (_ :: l, acc) = loop (l, l :: acc)
in
loop (l, [l])
end
(All this code is Standard ML, in case you wonder.)
Matthias
Mark Carroll
Steffen Mazanek <steffen...@unibw-muenchen.de> wrote:
>Doesn't work:
Oh! Sorry - I did suffixes instead, didn't I? (-:
-- Mark
Torbjörn Lager
I really appreciate your efforts, but I need a program computing
_prefixes_ (and that's what my example programs were doing!) and now I'm
realizing that although I don't know Haskell nor ML, you are suggesting
to me programs computing sets of _suffixes_ (which is a lot easier).
Right? It's late in the evening here, but I'm pretty sure that's the
case. :-)
Wow, I became really curious about the magic that @ could perform in
Haskell :-)
So Matthias, is your reasoning concerning the space and time complexity
for a non-tail recursive version valid for a prefix-computing program as
well?
Cheers,
Mark Carroll
=?iso-8859-1?Q?Torbj=F6rn?= Lager <la...@ling.gu.se> wrote:
(snip)
>I still not quite sure what this does, but I guess that you're using an
It appears to do suffixes instead of prefixes. I didn't read your
original article carefully enough. (-: Prefixes could be,
prefixes s =
reverse (realprefixes s [])
where
realprefixes [] a = a
realprefixes s a = realprefixes (allbutlast s) (s:a)
allbutlast xs = realallbutlast xs []
realallbutlast (x:y:zs) a = realallbutlast (y:zs) (a++[x])
realallbutlast _ a = a
I'm not sure if that's tail-recursive or not, but it might be? (-:
>accumulator and reverse to reverse the reversing effect of that (wow,
>that came out funny... :-). If so, I guess it is debatable whether
You seem to have the idea. (-:
>you'll win something over the non-tail recursive version. In terms of
>speed, I mean. I'm looking for the fastest way of doing this, since I'm
>writing a program that does it a lot. I'm willing to use arrays if I
>have to, and that's no problem, since Oz supports that too. A clean
>declarative solutions would be nicer though...
Oh! In that case, I'd just go with something like,
prefixes [] = []
prefixes s =
s : prefixes (allbutlast s)
where
allbutlast (x:y:zs) = x : allbutlast (y:zs)
allbutlast _ = []
It probably won't be all that bad. (-:
-- Mark
Torbjörn Lager
Well, I timed both your solution and my original solution (both coded in
Prolog). I tried them with very long input (10000 elements), and with
short input (many times). In terms of speed, they were indistinguisable.
Still, I believe both solutions must be slow; mine because it's non-tail
recursive, and your's because allbutlast traverses the same list many
times. (I must admit that your solutions is simpler and more intuitive
but I expected it to be even slower than mine because of this allbutlast
business; but it wasn't.) Is this the best we can do? If so, I suspect
that one could do much better not working with lists but instead with
arrays of bytes from which one can slice from within a for loop.
Still hope someone will come up with an optimal solution which is list
based ...
Cheers,
Dylan Thurston
>I really appreciate your efforts, but I need a program computing
>_prefixes_ (and that's what my example programs were doing!) and now I'm
>realizing that although I don't know Haskell nor ML, you are suggesting
>to me programs computing sets of _suffixes_ (which is a lot easier).
>Right? It's late in the evening here, but I'm pretty sure that's the
>case. :-)
That's correct. Because of the way lists are stored, this is inherently
more efficient; for one thing, the result list of suffixes all share the
same space, while the list of prefixes cannot share and so must use
space (and time) O(l^2).
Is there a way to restructure your algorithm so that you need to compute
suffixes rather than prefixes?
If not, other data structures (maybe immutable arrays, depending on the
implementation) might be more efficient.
In any case, I recommend you write your program first and then worry about
its speed. Your bottleneck may not be where you think it is.
>Wow, I became really curious about the magic that @ could perform in
>Haskell :-)
'@' in Haskell and 'as' in ML are pretty much equivalent. Both give a name
to a larger piece of a pattern.
Best,
Dylan Thurston
Mark Carroll
=?iso-8859-1?Q?Torbj=F6rn?= Lager <la...@ling.gu.se> wrote:
(snip)
>business; but it wasn't.) Is this the best we can do? If so, I suspect
>that one could do much better not working with lists but instead with
>arrays of bytes from which one can slice from within a for loop.
>
>Still hope someone will come up with an optimal solution which is list
>based ...
A slightly nicer solution I just thought of is,
prefixes xs = foldr (\y ys -> [y] : map (y:) ys) [] xs
I fear it's just as slow, though. Fundamentally, the problem is that
the lists that are the elements of the resulting list all have to be
different copies because their tails differ, so you're looking at
O(n^2) in space and time.
-- Mark
Mark Carroll
Mark Carroll <ma...@chiark.greenend.org.uk> wrote:
(snip)
> prefixes xs = foldr (\y ys -> [y] : map (y:) ys) [] xs
As an extra explanatory note in case you don't immediately recognise
the Haskell notation:
foldr (+) 4 [7,8,9] = 7 + (8 + (9 + 4)) = 28
(\x y -> x * y) 5 7 = 5 * 7 = 35
map (3:) [[4],[6,7]] = [3:[4],3:[6,7]] = [[3,4],[3,6,7]]
(I think I got that correct, anyway.)
-- Mark
Thomas Sjöland
% 1st attempt using ordinary lists.
prefixes(L,R) :- allpre(L,[[]],R).
allpre([],R,R).
allpre([H|T],[A|S],R) :-
append(A,[H],B),
allpre(T,[B,A|S],R).
% 2nd using difference lists
dappend(A-B,B-C,A-C).
%dallpre([],R,R).
%dallpre([H|T],[A|S],R) :-
% dappend(A,[H|U]-U,B),
% dallpre(T,[B,A|S],R).
% transformed by unfolding dappend/3
dallpre([],R,R).
dallpre([H|T],[A-[H|C]|S],R) :-
dallpre(T,[A-C,A-[H|C]|S],R).
dprefixes(L,R) :- dallpre(L,[A-A],S), mapd2l(S,R).
mapd2l([],[]).
mapd2l([Ah-Ar|T],R) :- unify_with_occurs_check(Ah,Ar), !, mapd2l(T,R).
mapd2l([A|T],[B|S]) :-
d2l(A,B),
mapd2l(T,S).
d2l(A-B,[]):- unify_with_occurs_check(A,B).
d2l(A-S,[H|R]) :- nonvar(A), A=[H|T], d2l(T-S,R).
Torbjörn Lager wrote:
[snip]
> However, it isn't
> tail recursive and perhaps therefore slow? I'm ashamed to say that all
> my attempts to massage it into a tail recursive program failed. Can you
> see a way? Another problem from my point of view is that the empty
> prefix is included in the solution. I would prefer to generate only the
> list of non-empty prefixes. No matter how I tried, I couldn't find a
> (nice) way to do that.
The latter of the two above prolog algorithms does that "on-the-fly" in the
post-processing phase where difference lists are translated to ordinary lists.
Whether it is "nice" is in the eye of the beholder, I guess.
> I also wrote the following in the functional style of Oz:
Translating the two above prolog algorithms into Oz should be a reasonable
excersise. After all Oz has logical variables so techniques like
difference-structures are usable just as in prolog.
> My questions: Is there a tail recursive solution to this? Is it likely
> to be faster? Is this the kind of thing for which a solution using
> arrays (from which you can take slices) is likely to be faster?
The above are both tail recursive.
The use of map2dl is applied after the algorithm has constructed the prefixes
to translate the difference lists back to ordinary lists and add some
penalty. It is well compensated by the transformation allowing us to
discard append in each recursive step altogether though.
Torbjörn Lager
<lots of interesting code snipped>
Wow, that's a nice approach! I sort of figured that difference lists
would come in handy somehow, but couldn't get it right. I really like
the way you were able to start with a simple append for difference list
and then transform it by unfolding. That's a methodologically very sound
trick (which, as you say, one is able to play (at least with difference
lists) only in a language that has logical variables, i.e. languages
like Prolog and Oz - I don't understand how people can live without
logical variables ;-)
But did you benchmark your program? You see the sad thing is that my
tests seem to show that the difflist version is actually slower - and in
fact 10 times slower - than my original version, and indeed 12-13 times
slower than your 'naive' version using ordinary append/3! (I really hope
I didn't make any mistakes when testing it...) I guess this shows that
my original assumption, that a cleverly implemented tail recursive
prefix/2 (= your dprefixes/2) would be faster than the naive version, is
false. So it seems that it is only in theory that dprefixes/2 is
'optimal'; in practice it is not; perhaps it is shuffeling too much
memory or something? I guess one would have to do more benchmarking to
see where the bottlenecks are...
But this is what I'm planning right now (but implemented in Oz):
prefixes(Xs,Xss) :-
( Xs = [A]
-> Xss = [Xs]
; Xs = [A,B]
-> Xss = [Xs,[A]]
; Xs = [A,B,C]
-> Xss = [Xs,[A,B],[A]]
% etc,... you get the idea...
; allpre(Xs,[[]],Xss)
).
allpre([],R,R).
allpre([H|T],[A|S],R) :-
append(A,[H],B),
allpre(T,[B,A|S],R).
It ain't pretty, but its fast. I'm using this to compute prefixes of
natural language words, and words being what they are, it is probably
enough to 'cache' cases up to a word length of 10 or so. If its longer
(which doesn't happen very often) the general case - where I use your
allpre/3 since it is the fastest one so far - will take care of it. My
tests show that this is about twice as fast as using only allpre/3. So
in a way, I ended up doing some 'partial evaluation' anyway.
Thanks for your help!
Regards,
Torbjörn
Thomas Sjöland
time complexity, though. Did you include the
post-processing phase of translation into ordinary lists in your
benchmark? That is probably not very efficient due to the use of
unify_with_occurs_check/2 (needed to avoid strange loops, could
possibly be done away with by introducing non-logical stuff,
var/1 nonvar/1 etc.).
-Thomas
Thomas Sjöland
:- length(L,5000), dallpre(L,[A-A],S).
is almost instant
while
:- length(L,5000), prefixes(L,P).
takes about a minute on my 450 Mhz PC running SICStus Prolog 3.8.6
My transformation technique is more or less a textbook approach of
Sterling and Shapiro "The Art of Prolog". Look at their chapter 15 on
incomplete datastructures.
I also tried this optimisation in order to avoid the reconstruction of
the cells corresponding to B giving a slight improvement for very long lists.
dallpre([],R,R).
dallpre([H|T],[B|S],R) :-
B=A-[H|C],
dallpre(T,[A-C,B|S],R).
Anyway this all should be fairly easy to move to Oz (to motivate the posting
in this newsgroup).
Torbjörn Lager
>
> No, I didn't benchmark the d-list version. It should have better
> time complexity, though.
Indeed, but it doesn't show when I time it :-( Not for long lists
(thousands of elements), nor for short ones (many times).
> Did you include the
> post-processing phase of translation into ordinary lists in your
> benchmark?
Yes, I did.
> That is probably not very efficient due to the use of
> unify_with_occurs_check/2 (needed to avoid strange loops, could
> possibly be done away with by introducing non-logical stuff,
> var/1 nonvar/1 etc.).
You are right. Here are some figures (run on a list of 10 elements 10000
times):
my original version: 770
my faster version: 330
allpre/3: 660
dallpre/3: 270
dprefixes/2: 6760
So your difflist version won this race. But only before converting the
result to ordinary lists (which is the form I need it in, and no, I dont
think I can adapt the rest of my program to use difflists...)
-- Torbjörn
--
Thomas Sjöland
identity)
mapd2l([],[]).
mapd2l([Ah-Ar|T],R) :-
% unify_with_occurs_check(Ah,Ar), !, mapd2l(T,R).
Ah==Ar, !, mapd2l(T,R).
mapd2l([A|T],[B|S]) :-
d2l(A,B),
mapd2l(T,S).
%d2l(A-B,[]):- unify_with_occurs_check(A,B), !.
d2l(A-B,[]):- A==B, !.
d2l(A-S,[H|R]) :- nonvar(A), A=[H|T], d2l(T-S,R).
Torbjörn Lager
>
> I tested a little:
>
> :- length(L,5000), dallpre(L,[A-A],S).
>
> is almost instant
> while
> :- length(L,5000), prefixes(L,P).
> takes about a minute on my 450 Mhz PC running SICStus Prolog 3.8.6
Hmm, I think a minute for 5000 elements indicates that diskswapping set
in... a large stack being built...
But yes, for long lists the difference is really, really striking:
allpre on 1000 elements: 760
prefixes on 1000 elements: 820
dallpre on 100000 elements: 270 (NB: 100 times longer list!)
Times in millisecs, on a 166Mhz PC.
For short lists, the difference isn't that striking (cf. my previous
message).
> Anyway this all should be fairly easy to move to Oz (to motivate the posting
> in this newsgroup).
Yes, but a faster way to transform to an ordinary list is needed...
-- Torbjörn
Ulf Wiger
-> I still not quite sure what this does, but I guess that you're
-> using an accumulator and reverse to reverse the reversing effect
-> of that (wow, that came out funny... :-). If so, I guess it is
-> debatable whether you'll win something over the non-tail
-> recursive version. In terms of speed
I don't know how it plays out in Oz, but at least in Erlang, it
is a pretty common technique. The (reversed) accumulator
version usually *does* win over the non-tail recursive one.
In Erlang, there are a couple of reasons for this:
- the recursive function needs more stack space, and the garbage
collector must traverse the stack; it also usually needs more
heap space than the non-tail recursive function as well, as
old copies of the data structures are sometimes kept until the
recursive function returns.
- List reversal is optimized via a built-in function, and thus
quite fast.
Of course, these factors are reasonably dependent on compiler and
execution environment. Therefore, if the most beautiful solution
is fast enough, go with it. If not, benchmark the alternatives
using the language and compiler of your choice.
Understandably, you asked for a beautiful tail recursive solution.
The accumulator trick is not exactly beautiful, but you get used
to it after a while. (:
/Uffe
--
Ulf Wiger tfn: +46 8 719 81 95
Senior System Architect mob: +46 70 519 81 95
Strategic Product & System Management ATM Multiservice Networks
Data Backbone & Optical Services Division Ericsson Telecom AB
Jim Farrand
My understanding is that this is not tail recursive, because the last
operation of the second case is cons (:) rather than a recursive call.
Or do I misunderstand?
--
Jim Farrand, ML Group, mailto:far...@cs.bris.ac.uk
Department of Computer Science, http://www.cs.bris.ac.uk/~farrand
University of Bristol, tel: +44-(0)117-954-5254
Woodland Road, Bristol, BS8 1UB, UK
Torbjörn Lager
Thomas Sjöland wrote:
>
> Perhaps it is a little better if we allow the use of ==/2 (testing of exact
> identity)
>
> mapd2l([],[]).
> mapd2l([Ah-Ar|T],R) :-
> % unify_with_occurs_check(Ah,Ar), !, mapd2l(T,R).
> Ah==Ar, !, mapd2l(T,R).
> mapd2l([A|T],[B|S]) :-
> d2l(A,B),
> mapd2l(T,S).
>
> %d2l(A-B,[]):- unify_with_occurs_check(A,B), !.
> d2l(A-B,[]):- A==B, !.
> d2l(A-S,[H|R]) :- nonvar(A), A=[H|T], d2l(T-S,R).
Yes, that nearly doubled the speed, but we're still not getting close to
the speed of the other versions. BTW, I noticed that since the variable
tails of the difflists are always identical, we can close them in one
go, so that mapd2l doesn't have to deal with open lists at all. Thus, we
can simplify to something like:
dprefixes(L,R) :- dallpre(L,[A-A],S), close_list(A), mapd2l(S,R).
close_list([]) :- !.
close_list([_|Xs]) :- close_list(Xs).
mapd2l([],[]).
mapd2l([A-B|T],[C|S]) :-
subtract(A,B,C),
mapd2l(T,S).
subtract(A,A,[]).
subtract([X|Xs],A,[X|Ys]) :-
subtract(Xs,A,Ys).
And that also made it a little bit faster...
- Torbjörn
Matthias Blume
>
> Mark and Matthias,
>
> I really appreciate your efforts, but I need a program computing
> _prefixes_ (and that's what my example programs were doing!) and now I'm
> realizing that although I don't know Haskell nor ML, you are suggesting
> to me programs computing sets of _suffixes_ (which is a lot easier).
> Right? It's late in the evening here, but I'm pretty sure that's the
> case. :-)
Oops, so sorry. Let me try again:
fun prefixes l = let
fun suff [] = [[]]
| suff (l as (_ :: l')) = rev l :: suff l'
in suff (rev l)
end
Satisfied? :-)
> Wow, I became really curious about the magic that @ could perform in
> Haskell :-)
>
> So Matthias, is your reasoning concerning the space and time complexity
> for a non-tail recursive version valid for a prefix-computing program as
> well?
Sure.
Matthias
Mark Carroll
Jim Farrand <far...@cs.bris.ac.uk> wrote:
(snip)
>My understanding is that this is not tail recursive, because the last
>operation of the second case is cons (:) rather than a recursive call.
>Or do I misunderstand?
Not at all - you're absolutely right, which is why I added this:
In article <NrC*BR...@news.chiark.greenend.org.uk>,
Mark Carroll <ma...@chiark.greenend.org.uk> wrote:
>In article <0NB*3P...@news.chiark.greenend.org.uk>,
>Mark Carroll <ma...@chiark.greenend.org.uk> wrote:
(snip)
>>I'm guessing that either this doesn't translate well to Oz or something,
>>or that it isn't tail recursive?
>
>Ah. The latter. Does,
(snip)
(-:
-- Mark
Stephen J. Bevan
> > prefixes [] = [[]]
> > prefixes s@(x:xs) = s : prefixes xs
>
> operation of the second case is cons (:) rather than a recursive call.
> Or do I misunderstand?
It isn't a traditionally tail recursive function but if your compiler
implements the tail recursion over constructors optimization then the
result is tail recursive. A nice little example explaining the
details can be found at http://burks.brighton.ac.uk/burks/foldoc/67/112.htm
Robin Garner
news:3B7D5DA0...@ling.gu.se:
> Hi All,
>
> I only just started programming in a functional style, and now I need to
> define a function that will find the set of prefixes to a list.
What about:
prefixes :: [Int] -> [[Int]]
prefixes [] = []
prefixes (x:xs) = [] : map (x:) (prefixes xs)
Robin Garner
Marcin 'Qrczak' Kowalczyk
>> prefixes [] = [[]]
>> prefixes s@(x:xs) = s : prefixes xs
>>
>> I'm guessing that either this doesn't translate well to Oz or something,
>> or that it isn't tail recursive?
>
> Very neat. But I'm afraid I don't know Haskell, so I don't know
> what @ means... What does it do?
A pattern in the form
name@pattern
behaves in the same way as
pattern
except that on the rhs of the function you may also use the given
name to refer to the whole thing the pattern matched.
--
__("< Marcin Kowalczyk * qrc...@knm.org.pl http://qrczak.ids.net.pl/
\__/
^^ SYGNATURA ZASTĘPCZA
QRCZAK
Torbjörn Lager
Marcin 'Qrczak' Kowalczyk wrote:
>
> Fri, 17 Aug 2001 21:05:46 +0200, Torbjörn Lager <la...@ling.gu.se> pisze:
>
> >> prefixes [] = [[]]
> >>
> >>
> >> I'm guessing that either this doesn't translate well to Oz or something,
> >> or that it isn't tail recursive?
> >
> > Very neat. But I'm afraid I don't know Haskell, so I don't know
> > what @ means... What does it do?
>
> A pattern in the form
> name@pattern
> behaves in the same way as
> pattern
> except that on the rhs of the function you may also use the given
> name to refer to the whole thing the pattern matched.
I eventually figured that out. The problem was that I was trying to give
the construct X@Y a meaning such that the program
prefixes [] = [[]]
prefixes s@(x:xs) = s : prefixes xs
works as intended, i.e. computes the set of prefixes given it argument
(as the name of the function implies).
Maybe you can. I failed....
So why did I fail? Well, the program does not compute the set of
prefixes, but the set of suffixes!
-- T
Matthias Blume
Err, actually, no. As someone else has pointed out, with the de-facto standard
list representation, the list of prefixes must inherently use O(n^2) space and
therefore takes at least O(n^2) time to construct. The above code does that.
Matthias
Lyndon While
Garner <robin....@delete.iname.com> wrote:
> Torbjörn Lager <la...@ling.gu.se> wrote in
> news:3B7D5DA0...@ling.gu.se:
> > I only just started programming in a functional style, and now I need to
> > define a function that will find the set of prefixes to a list.
>
> What about:
>
> prefixes :: [Int] -> [[Int]]
> prefixes [] = []
> prefixes (x:xs) = [] : map (x:) (prefixes xs)
Here's a concise Haskell definition that I haven't seen mentioned yet:
prefixes = takeWhile (not . null) . iterate init
This will return only the non-empty prefixes.
Jón Fairbairn
> Here's a concise Haskell definition that I haven't seen mentioned yet:
>
> prefixes = takeWhile (not . null) . iterate init
>
> This will return only the non-empty prefixes.
Mmm. but
prefixes = reverse . tail . inits
is even more concise, and if you don't mind getting the other order
and including the empty list,
prefixes = inits
:-)
--
Jón Fairbairn Jon.Fa...@cl.cam.ac.uk