Some basic lisp functions -trying to teach myself the basics

[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

[nuntius]

In the second COND branch, your function is only inspecting one value and then returning...

[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.

[Konfusius]

Code: Select all

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

[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.

[arturoVidal]

Thanks guys. That was a silly mistake

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).

[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

[arturoVidal]

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?

[edgar-rft]

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)

[pjstirling]

Strictly it should be (NTH column (NTH row board)) otherwise you transpose between the natural PRINT of lists