[plt-scheme] idiomatic way to split a list into first, middle, last?
On Thu, 2006-01-05 at 23:44 -0500, Matthias Felleisen wrote:
. . .
> You got the constructor wrong here. This wouldn't do it.
I'm not sure what you mean by "constructor" here. I gathered from
reading the code in the original message that the intent was to extract
the first item, the last item, and the list of intervening items from an
input list, and to apply first-proc to the first, middle-proc to each of
the intervening ones, and last-proc to the last. I decided the nubbin
of the problem was the extraction; applying the procs is trivial. Hence
I focussed on pattern-matching to extract the relevant parts of the
input list. The following is a transcript of an SWI Prolog session:
====================================================================
$ pl
Welcome to SWI-Prolog (Multi-threaded, Version 5.4.7)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [user].
|: trisect( List, First, Middle, Last ) :-
|: append( [First], Xs, List ),
|: append( Middle, [Last], Xs ).
|: % user://1 compiled 0.00 sec, 424 bytes
Yes
?- trisect( [1,2,3,4,5], F, M, L ).
F = 1
M = [2, 3, 4]
L = 5 ;
No
?- trisect( [1,2], F, M, L ).
F = 1
M = []
L = 2 ;
No
?-
====================================================================
I think the variables F,M,L are bound correctly in both cases above.
-- Bill Wood
PS Some notes for those who aren't familiar with Prolog.
1) Code is loaded into the interpreter by "consult"ing a file, and an
abbreviation for "consult( foo )" is "[ foo ]. "user" is initially
bound to stdin, so "[user]." at the prompt allows interactive entry
of code to the interpreter. Oh yeah, each line entered at top level
must end with "." so the interpreter will know you're done.
2) In Prolog, variables are indicated by initial caps (or initial "_").
3) A definition of a predicate looks like
foo( A1,...An ) :- bar1( B11,...B1n1), ..., barm( Bm1,...Bmnm ).
Read this as "foo(...) succeeds if bindings for the variables in each
of bar1,...,barm can be found which satisfy each of bar1(...) through
barm(...)
So, the three lines of code following "|:" prompts in the transcript
define the predicate "trisect( List, First, Middle, Last )" to be
satisfied by bindings to the four variables List, First, Middle, Last
if they satisfy both the subgoals "append( [First], Xs, List )" and
"append( Middle, [Last], Xs )"
4) "append( Xs, Ys, Zs )" is a built-in predicate that is read as "Zs is
the result of appending the list bound to Xs to the list bound to Ys
(in that order). If you want to append two lists, say [1,2,3] and
[7,6,5], and bind the result to Z, the call would be
append( [1,2,3], [7,6,5], Z )
and Z would be bound to the list [1,2,3,7,6,5].
On the other hand, if you want to decompose [1,2,3,7,6,5] into a left
hand part and a right hand part bound to the variables Left and Right
respectively, then the call would be
append( Left, Right, [1,2,3,7,6,5] )
5) The Prolog engine works by making choices of goals and, if necessary,
backtracking through the tree of choice points trying all possible
paths.
At top level, when a goal succeeds the interpreter prints out the the
successful bindings to all the variables in the goal, and then
pauses. If you press <RETURN> you get "Yes" followed by the prompt;
if you press ";" followed by <RETURN> the interpreter fails the
current goal, so backtracking is attempted and, if successful, the
new variable bindings for the new successful goal are printed. In
general, if a top-level goal fails the interpreter prints "No", so if
you keep asking for alternatives eventually the goal fails, "No" is
printed followed by the prompt.
The transcript shows my request for all alternative sets of bindings
to the variables; in each call there was exactly one successful
binding set.
6) A list literal is written "[x1,...,xn]".
-- wtw