[plt-scheme] idiomatic way to split a list into first, middle, last?

From: Bill Wood (william.wood3 at comcast.net)
Date: Fri Jan 6 02:50:42 EST 2006

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




Posted on the users mailing list.