this simple function i'm trying to write is giving me headaches!
basically i want to do something that does:
(variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
i come from a procedural programming background and find functional
programming very confusing (especially recursion). can someone give
me some hints? my attempts at this make no sense so pasting them here
would only confirm my newbish forray into LSIP. thanks for any help!
kareem
On Fri, Sep 17, 2004 at 12:48:37PM -0700, methodmano wrote:
> this simple function i'm trying to write is giving me headaches!
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
>
> i come from a procedural programming background and find functional
> programming very confusing (especially recursion). can someone give
> me some hints? my attempts at this make no sense so pasting them here
> would only confirm my newbish forray into LSIP. thanks for any help!
The trick to functional programming is to describe your problem to the
computer, and then the solution will come naturally from that. A simple
English description of the problem also helps: it appears that you are
trying to collect a list of lists where for each list the first
parameter is inserted into one of the ``empty spaces'' of the second
parameter.
Given a function VARIATIONS with parameters I and SYM-LIST.
Base case: If SYM-LIST is empty, then our result is simply
(list (list I)) -> ((<value of I>))
Otherwise: SYM-LIST is not empty, it is a list. We shall label the
first element of this list as A.
Assume, for the moment, that the function VARIATIONS is already
written and works. Then we can let RESULT be the value of calling
VARATIONS on I and (rest SYM-LIST). We assume that RESULT will
be bound to the correct answer for the rest of the list. Now the
problem is: describe a way of adding to the result so that it
also incorporates the element A. (Now the problem is much simpler
than before).
(Don't read below this line if you want to try solving this
sub-problem yourself).
There are two steps: first you must change the sub-lists in RESULT
to have the element A, and then you must generate a new sub-list
for the new empty space corresponding to the place ``before'' A in the
list.
The first step is simply a matter of using MAPCAR cleverly:
(mapcar (lambda (sub-list) (cons A sub-list))
result)
The second step is also simple, you take the result of the first
step and cons a new element to the front of it, that new element
being a sub-list itself:
(cons (cons I SYM-LIST) (mapcar ...))
Now you simply put all of this together, in a form the computer can
understand:
(defun variations (i sym-list)
(cond ((null sym-list)
;; base case
(list (list i)))
(t
;; otherwise
(let ((a (first sym-list))
(result
;; Our assumption is that this returns the correct
;; answer
(variations i (rest sym-list))))
(cons (cons i sym-list)
(mapcar (lambda (sub-list) (cons a sub-list))
result))))))
All we did was define a base case, and a way to go from a list of length
N to a list of length N+1. The rest falls naturally from there by what
is called structural induction (on the list).
This could have been done in a procedural manner too: you would have to
loop over the list and insert I in every place.
(defun insert-at-position (i n list)
(let ((cell (nthcdr n list)))
(setf (rest cell)
(cons i (rest cell)))
list))
(defun variations (i sym-list)
(let ((result (list (cons i sym-list))))
(dotimes (n (length sym-list))
(push (insert-at-position i n (copy-list sym-list))
result))
(nreverse result)))
Lisp supports all kinds of programming styles.
BTW: Neither of these implementations is very efficient algorithmically.
--
;;;; Matthew Danish -- user: mrd domain: cmu.edu
;;;; OpenPGP public key: C24B6010 on keyring.debian.org
On Fri, 17 Sep 2004 16:42:56 -0400, Matthew Danish wrote:
[snip - another nice solution]
> This could have been done in a procedural manner too: you would have to
> loop over the list and insert I in every place.
>
> (defun insert-at-position (i n list)
> (let ((cell (nthcdr n list)))
> (setf (rest cell)
> (cons i (rest cell)))
> list))
>
> (defun variations (i sym-list)
> (let ((result (list (cons i sym-list))))
> (dotimes (n (length sym-list))
> (push (insert-at-position i n (copy-list sym-list))
> result))
> (nreverse result)))
My solution was similar to this one but, FWIW, I prefer my version:
(defun insert (x lst n)
"Insert x into lst at position n"
(if (= n 0)
(cons x lst)
(cons (car lst) (insert x (cdr lst) (1- n)))))
(defun variations (x lst)
"List all variations formed by inserting x into lst at different positions"
(let ((result nil))
(dotimes (i (1+ (length lst)) result)
(push (insert x lst i) result))))
Cheers,
Bill.
--
Dr. William Bland.
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax. (Ken Anderson).
On Fri, 17 Sep 2004 21:26:23 GMT, William Bland
<·······@abstractnonsense.com> wrote:
> My solution was similar to this one but, FWIW, I prefer my version:
>
> (defun insert (x lst n)
> "Insert x into lst at position n"
> (if (= n 0)
> (cons x lst)
> (cons (car lst) (insert x (cdr lst) (1- n)))))
>
This version can be more efficient is tail recursion elimination is
available ;)
Only consing up to element saves memory. Tail elimination saves stack
space.
(defun insert (index element list &optional (result nil))
(cond
((= index 0) (cons result (cons element list)))
(t (insert (1- index) element (cdr list) (cons (car list) result)))))
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Thanks a lot for your hints and explanations. They were way more than I
was hoping for! I haven't quite gotten a firm grasp of what you wrote,
but I'm going to study up on them this weekend. I'm guessing you'll be
hearing more from me in the immediate future since this is such a good
resource for beginners like myself. Thanks again!
kareem
On Fri, 17 Sep 2004 12:48:37 -0700, methodmano wrote:
> this simple function i'm trying to write is giving me headaches!
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
>
> i come from a procedural programming background and find functional
> programming very confusing (especially recursion). can someone give
> me some hints? my attempts at this make no sense so pasting them here
> would only confirm my newbish forray into LSIP. thanks for any help!
>
> kareem
Once you're used to FP you can solve this in a couple of minutes (I
did, just now). To get used to the Lisp way (or rather one Lisp way) of
doing things I'd suggest thinking like this:
Variations is very simple. All it does is insert 'x at every possible
position in '(y z) and collect the results together.
So assume we have a function that inserts an element at a given position
in a list. Then we can easily write variations (hint: I used dotimes).
Now you need to write insert. As a base-case, if you insert 'x at
position zero of '(y z) you get (cons 'x '(y z)). If the position is
bigger than zero, you can cons the car of the list onto what you get
from inserting the element onto the cdr of the list at a position one
smaller than what you're trying to do now. This will give you a recursive
insert function.
Disclaimer: I've been more of a Schemer in the past, so I shy away from
things like loop, which could probably do this too.
Hope that helps.
Cheers,
Bill.
--
Dr. William Bland.
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax. (Ken Anderson).
William Bland <·······@abstractnonsense.com> writes:
> Disclaimer: I've been more of a Schemer in the past, so I shy away from
> things like loop, which could probably do this too.
Did someone say LOOP?
(defun variations (x list)
(loop for cons on (cons nil list) collecting
(nconc (ldiff list (cdr cons)) (cons x (cdr cons)))))
Okay, so that's arguably obfuscated Lisp. But you should never pass up
a chance to combine LOOP, LDIFF, and abuse of Common Lisp's Lisp-2
nature.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
methodmano wrote:
> this simple function i'm trying to write is giving me headaches!
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
;; More variations on variations
(defun variations (obj list)
(loop for i from 0 to (length list)
with middle = (list obj)
collect (append (subseq list 0 i) middle (subseq list i) ))))
;; More efficient version
(defun variations (obj list)
(loop with head = nil
with head-tail = nil
with middle = (list obj)
for tail = list then (cdr tail)
collect (append head middle tail) into variations
do (if head-tail
(setf (cdr head-tail) (cons (first tail) nil))
(setf head-tail (setf head (cons (first tail) nil))))
when (null tail) return variations))
Wade
Wade Humeniuk wrote:
> methodmano wrote:
>
>> this simple function i'm trying to write is giving me headaches!
>> basically i want to do something that does:
>> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
>
>
> ;; More variations on variations
>
> (defun variations (obj list)
> (loop for i from 0 to (length list)
> with middle = (list obj)
> collect (append (subseq list 0 i) middle (subseq list i) ))))
>
I like yours. Now if i want to capitalize from it :
;; general function which return all (L1 L2) such that (append L1 L2) == L
* (defun append-ooi (list)
(loop for i from 0 to (length list)
collect (list (subseq list 0 i) (subseq list i) )))
APPEND-OOI
* (append-ooi '(y z))
((NIL (Y Z)) ((Y) (Z)) ((Y Z) NIL))
and now :
* (defun variations (obj list)
(loop for (L1 L2) in (append-ooi list)
with middle = (list obj)
collect (append L1 middle L2) ))
VARIATIONS
* (variations 'x '(y z))
((X Y Z) (Y X Z) (Y Z X))
*
Christophe Turle
··········@gmail.com (methodmano) writes:
> this simple function i'm trying to write is giving me headaches!
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
>
> i come from a procedural programming background and find functional
> programming very confusing (especially recursion). can someone give
> me some hints? my attempts at this make no sense so pasting them here
> would only confirm my newbish forray into LSIP. thanks for any help!
(defun variations (item list)
(if (null list)
(list (list item))
(cons (cons item list)
(mapcar (lambda (rest) (cons (car list) rest))
(variations item (cdr list))))))
For recurtion, you must identify at least one non recursive case,
here, when list is null, we return just a list containing the
singleton containing the item; then you must proceed by building the
result from what you get by applying the function to some smaller part
of the arguments. Here, we compute the (variations item list) given
(variations item (cdr list)).
[12]> (trace variations)
;; Tracing function VARIATIONS.
(VARIATIONS)
[13]> (variations 'x '(y z))
1. Trace: (VARIATIONS 'X '(Y Z))
2. Trace: (VARIATIONS 'X '(Z))
3. Trace: (VARIATIONS 'X 'NIL)
3. Trace: VARIATIONS ==> ((X))
2. Trace: VARIATIONS ==> ((X Z) (Z X))
1. Trace: VARIATIONS ==> ((X Y Z) (Y X Z) (Y Z X))
((X Y Z) (Y X Z) (Y Z X))
[14]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
methodmano wrote:
> this simple function i'm trying to write is giving me headaches!
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
>
> i come from a procedural programming background and find functional
> programming very confusing (especially recursion). can someone give
> me some hints? my attempts at this make no sense so pasting them here
> would only confirm my newbish forray into LSIP. thanks for any help!
>
> kareem
Doesn't this question get asked every September?
Here's a 'functional' version that doesn't rely on side effects (or
MAPCAR). It's HIGHLY recursive and not nearly efficient as some of the
versions others have proposed. If you get lost, try using TRACE to
follow the recursive calls.
(defun variations (elt l)
(insert elt '() l))
;;;
;;; Insert new element ELT at all positions in given list L
;;; (insert 'a '() '((b c))) => ((a b c) (b a c) (b c a))
;;;
;;; BIN is temporary storage as we work our way down L. We pack elements
;;; of L into BIN and then unpack them below.
;;;
(defun insert (elt bin l)
(cond ((null l) (list (insert-1 bin (list elt))))
(t (cons (insert-1 bin (cons elt l))
(insert elt (cons (car l) bin) (cdr l)))) ))
;;;
;;; Unpack the elements of BIN into L.
;;; (insert-1 '(c b) '(a)) => (b c a)
;;;
(defun insert-1 (bin l)
(cond ((null bin) l)
(t (insert-1 (cdr bin) (cons (car bin) l)))) )
David Sletten
kareem seeks hints:
> basically i want to do something that does:
> (variations 'x '(y z)) -> ((x y z) (y x z) (y z x))
You are trying to write a function that takes
an item and a list as arguments. It is a good
bet that recursing on the list will be important.
So your code will fall into the pattern
(defun f (item list)
(if (endp list)
--base_case--
(let ((one-step-simpler (f item (cdr list))))
--inductive_step-- )))
That is (f 'x '(a b c)) is to be computed as
some combination of x, (a b c), and
(f 'x '(b c)). More explicitly
((x a b c)(a x b c)(a b x c)(a b c x))
is to be computed from these ingredients
x
(a b c)
((x b c)(b x c)(b c x))
Alan Crowe
Edinburgh
Scotland