Page 1 of 2

Some basic lisp functions -trying to teach myself the basics

Posted: Fri Sep 06, 2013 5:16 am
by arturoVidal
Hi everyone,

So I've been playing around with LISP lately in order to develop an appreciation for functional programming.

Now I've come into a problem I can't solve. Here is the scenario. I want to write a function that takes two lists - both lists contain words. The idea is for the function to output the list of words that appear in the first list, but don't appear in the second list.

Expected output:
(filter '(1 2 3 4 5) '(3 4))

> (1 2 5)

I've made an attempt and here's my progress so far:

Code: Select all

(defun filter (lst items-to-filter)
   (cond ((null lst) nil)
         ((not (member (first lst) items-to-filter)) (cons (first lst) '() ) )
         (t (filter (cdr lst) items-to-filter))))
My output is only (1) when it should be (1 2 5). Could anyone point me in the right direction? Thanks :D :D :D

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Mon Sep 09, 2013 7:38 pm
by nuntius
In the second COND branch, your function is only inspecting one value and then returning...

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Tue Sep 10, 2013 8:26 am
by Goheeca
The filter function can look like this:

Code: Select all

(defun filter (lst items-to-filter)
   (cond ((null lst) nil)
         ((member (car lst) items-to-filter) #1=(filter (cdr lst) items-to-filter))
         (t (cons (car lst) #1#))))
but if it just isn't an exercise and we don't demand the result set be ordered exactly this way we can use set-difference.

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Fri Sep 13, 2013 5:11 am
by Konfusius

Code: Select all

(defun filter (lst items-to-filter)
  (loop for x in items-to-filter
        if (not (member x lst))
          collect x))

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Fri Sep 13, 2013 8:16 pm
by farticustheelder
Without writing code, what needs to happen is to sort both lists, and reduce to sorted, no duplicates. For each element of list a scan list b from start to an equal or greater than word in list b: if equal word in both lists, if greater word from list a is unique so accumulate. When list a is exhausted first the job is done, if list b is exhausted first the remainder of list a is unique. Iterating across two lists in a jerky way like this is a job for the loop macro. Hope it helps.

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Sat Sep 14, 2013 7:58 am
by arturoVidal
Thanks guys. That was a silly mistake 8-)

I've come across a slightly tricky problem. Say I have the following parameter which represents a connect 4 board:

(defparameter *board*
'((nil nil nil nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)
(nil nil nil nil nil nil)))

Say I also have another parameter that contains all 69 winning lines of C4, e.g.

'( ((0 0) (0 1) (0 2) (0 3))
((0 1) (0 2) (0 3) (0 4))
((0 2) (0 3) (0 4) (0 5))
....all other winning lines
)

How can I check the contents of cells on my board. e.g. the bottom row first column, how can I check what (0 0) contains? I have working code of a C4 game, but I'm trying to write a heuristic function for it (it currently just operates in a breadth-first fashion and always returns 0).

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Sat Sep 14, 2013 2:52 pm
by pjstirling
There are no circumstances where representing a fixed size 2d structure as a list-of-lists makes sense, but you can use NTH for random-access into lists.

For my sudoku solver I use 2D arrays of a "square" class that contains its coordinates (because they also get put in other data structures that don't want to track their coordinates for them). For connect-4 you may

MAKE-ARRAY can take a list of dimensions, '(6 6) in your case, and then (AREF board y x) to access squares

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Sat Sep 14, 2013 10:19 pm
by arturoVidal
pjstirling wrote:There are no circumstances where representing a fixed size 2d structure as a list-of-lists makes sense, but you can use NTH for random-access into lists.

For my sudoku solver I use 2D arrays of a "square" class that contains its coordinates (because they also get put in other data structures that don't want to track their coordinates for them). For connect-4 you may

MAKE-ARRAY can take a list of dimensions, '(6 6) in your case, and then (AREF board y x) to access squares
I agree. I have no idea why make-array isn't being used. But how would I go out about using NTH to access a random element in a list of lists. Can't NTH only take a single index?

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Sat Sep 14, 2013 11:41 pm
by edgar-rft
arturoVidal wrote:But how would I go out about using NTH to access a random element in a list of lists. Can't NTH only take a single index?

Code: Select all

(nth <column> (nth <row> *board*)) => <field>
Code updated - thanks to the notice of pjstirling below (one should always test code before posting to the forum)

Re: Some basic lisp functions -trying to teach myself the ba

Posted: Sun Sep 15, 2013 10:34 am
by pjstirling
Strictly it should be (NTH column (NTH row board)) otherwise you transpose between the natural PRINT of lists