julian@cernvax.UUCP (julian bunn) (08/08/90)
Can some kind person please help with a trivial Prolog problem? I am trying to write a program that will remove leading blank characters from a list. For example, the result of: remove_blanks([32,32,32,104,104],X). should be: X = [104,104] I have tried, with reckless abandon, the following definition: remove_blanks([H|T],T) :- H=32, remove_blanks(T,_). remove_blanks(S,S). which, when tracing, seems to do nicely recursively, but in the end returns me with T equal to the original list! Help !
vu0310@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (08/09/90)
In article <2157@cernvax.UUCP> julian@cernvax.UUCP (julian bunn) writes: >Can some kind person please help with a trivial Prolog problem? >I am trying to write a program that will remove leading blank >characters from a list. For example, the result of: [stuff deleted] >remove_blanks([H|T],T) :- H=32, remove_blanks(T,_). >remove_blanks(S,S). > >which, when tracing, seems to do nicely recursively, but in the >end returns me with T equal to the original list! There are a couple of problems with your code. The first is that clause 1 doesn't look past the first blank in the string. You want: remove_blanks([H|T],T1) :- H=32, remove_blanks(T,T1). Also, to prevent backtracking to the second clause if something *subsequent* to calling remove_blanks/2 fails, you don't want the second clause to succeed if the first did. One way to do this is with a cut. Another method is to use a test thus: remove_blanks(S,S) :- not(S=[32|_]). You can also use more unification in the first clause to give a final version something like: remove_blanks([32|T],T1) :- !, remove_blanks(T,T1). remove_blanks(S,S) :- not(S=[32|_]). -Kym ===
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/10/90)
In article <2157@cernvax.UUCP>, julian@cernvax.UUCP (julian bunn) writes: > I am trying to write a program that will remove leading blank > characters from a list. You're clearly not using the QP library, because it's all there... > remove_blanks([H|T],T) :- H=32, remove_blanks(T,_). > remove_blanks(S,S). (a) Let's look at that first clause, and let's consider the case where you called remove_blanks(" sargon", Ans). This unifies with the head of the first clause, giving H = (0' ) = 32 T = " sargon" Ans = T = " sargon" the body becomes 32 = 32, remove_blanks(" sargon", _dont_dare_tell_me_this_answer_) the first goal of which succeeds, and then your recursive call says 'discard leading blanks from " sargon" AND THEN THROW AWAY THE ANSWER' So you want your first clause to be remove_blanks([0' |T], Answer) :- remove_blanks(T, Answer). (b) The second clause will _also_ succeed in this case, with S = " sargon" Answer = S = " sargon". You presumably don't want this to happen. A pure way of doing it is remove_leading_blanks([], []). remove_leading_blanks([H|T], [H|T]) :- H =\= " ". remove_leading_blanks([H|T], R ) :- H =:= " ", remove_leading_blanks(T, R). If you don't mind a red cut, you can do remove_leading_blanks([32|T], R) :- !, remove_leading_blanks(T, R). remove_leading_blanks(T, R). (I changed the name to remove_leading_blanks/2 because it doesn't remove ^^^^^^^ _all_ blanks as the name suggests; trailing blanks and consecutive internal blanks are left alone.) -- Taphonomy begins at death.
julian@cernvax.UUCP (julian bunn) (08/10/90)
Thanks to everyone who answered my simple Prolog question. All the solutions proposed seem to work. What amazes me is the richness in variety of solutions ! Thanks again.
debray@cs.arizona.edu (Saumya K. Debray) (08/11/90)
Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes: > A pure way of doing it is > > remove_leading_blanks([], []). > remove_leading_blanks([H|T], [H|T]) :- H =\= " ". > remove_leading_blanks([H|T], R ) :- H =:= " ", > remove_leading_blanks(T, R). > > If you don't mind a red cut, you can do > > remove_leading_blanks([32|T], R) :- !, > remove_leading_blanks(T, R). > remove_leading_blanks(T, R). I think I would prefer the following ("look, Ma, no choice points"): remove_leading_blanks([], []). remove_leading_blanks([H|T], L) :- H =:= " " -> remove_leading_blanks(T, L) ; L = [H|T]. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@cs.arizona.edu uucp: uunet!arizona!debray
vu0310@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (08/11/90)
In article <3542@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: [stuff deleted] > remove_leading_blanks([32|T], R) :- !, > remove_leading_blanks(T, R). > remove_leading_blanks(T, R). ^^^ Should be remove_leading_blanks(R, R) maybe? -Kym
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/13/90)
> Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes: > > remove_leading_blanks([32|T], R) :- !, > > remove_leading_blanks(T, R). > > remove_leading_blanks(T, R). ^^^^ mistake, should be R, R In article <24120@megaron.cs.arizona.edu>, debray@cs.arizona.edu (Saumya K. Debray) writes: > I think I would prefer the following ("look, Ma, no choice points"): > > remove_leading_blanks([], []). > remove_leading_blanks([H|T], L) :- > ( H =:= " " -> > remove_leading_blanks(T, L) > ;/* H =\= " " */ > L = [H|T] > ). I'd prefer that too. Indeed, Debray's SB-Prolog will let you write that last clause as remove_leading_blanks([H|T], L) :- ( H =:= " ", remove_leading_blanks(T, L) ; H =\= " ", L = [H|T] ). and the compiler is smart enough to notice that the two tests conflict, and it will plant the cut for you. That's the _really_ nice way to write it. (Does the new Berkeley compiler do this too?) -- The taxonomy of Pleistocene equids is in a state of confusion.
vanroy@pisces (Peter Van Roy) (08/14/90)
In article <3553@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > >I'd prefer that too. Indeed, Debray's SB-Prolog will let you write that >last clause as > remove_leading_blanks([H|T], L) :- > ( H =:= " ", > remove_leading_blanks(T, L) > ; H =\= " ", > L = [H|T] > ). >and the compiler is smart enough to notice that the two tests conflict, >and it will plant the cut for you. That's the _really_ nice way to write it. >(Does the new Berkeley compiler do this too?) Yes, the Berkeley compiler generates deterministic code for this example, but it does not "plant a cut". A single conditional branch is generated to distinguish between the two arms of the disjunction. Even if the two tests do not conflict entirely, the compiler is smart enough to generate a choice point only when they overlap. For example, consider: max(A, B, C) :- A>=B, C=A. max(A, B, C) :- A=<B, C=B. A choice point is generated only if A=:=B. Sincerely, Peter Van Roy