LispForum

Discuss and learn Lisp programming of all dialects

This is a read-only archive of lispforum.com. The forum was locked to new users and posts and is preserved here as static HTML from a database snapshot taken on 2019-09-07.

Some basic lisp functions -trying to teach myself the basics

13 posts · 16698 views

arturoVidal
#1
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:
(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

Last edited by nuntius on , edited 1 time in total. Reason: added [code] tags

nuntius Administrator
#2

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

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

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

The filter function can look like this: 
(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.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.
Konfusius
#4

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

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

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

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
#6

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

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

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

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
#8

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

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?
edgar-rft
#9

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

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?
(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)

Last edited by edgar-rft on , edited 2 times in total.

pjstirling
#10

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

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

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

WOW thanks heaps for your help (both of you ;) )

Finally wrote my static heuristic evaluation function for C4 :D :D :D
ykm
#12

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

head about set-differrence?
CL-USER> (set-difference '(1 2 3 4 5) '(3 4))
(5 2 1)
Goheeca
#13

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

It depends, whether the resulting set should be generated in a stable way.
There is no guarantee that the order of elements in the result will reflect the ordering of the arguments in any particular way. The result list may share cells with, or be eq to, either of list-1 or list-2, if appropriate.
OP didn't answer this.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version). Temporary mirrors of aferomentioned: CLHS and a dark version.