Lisp is simmetry, understanding the find function


It may seems quite obvious, but the Lisp’s “find” semantic gave me some headache.
First of all, let’s start with some code:

(defvar *food-list*
  '((mela (pera banana)) (melanzane zucchine peperoni) (carne pesce uova)))

The “find” function gives you the power to search in a list for an item, returning back the element (if found) within his sublist (if present). Unfortunately, if the list is not symmetric, there is no guarantee to get the expected behaviour:

(find 'pera *food-list*)
=> NIL ;;WTF??

With find the list is visited one element at time, applying “eq” to any single element:

(eq 'pera '(mela (pera banana)))
=> NIL
(eq 'pera '(melanzane zucchine peperoni))
=> NIL
(eq 'pera '(carne pesce uova))
=> NIL

But how can we reach our pera within the find function? The “key” is in the “:key” parameter!!
With :key we can specify a function to be executed for each element find visit. It’s an old lisp school technique to use the car & cdr family functions:

(find 'pera *my-list* :key #'caadr)
=> (MELA (PERA BANANA))

Wow, it works! This is what happened in background for each element:

(eq 'pera (caadr '(mela (pera banana))))
=> T
(eq 'pera (caadr '(melanzane zucchine peperoni)))
=> NIL
(eq 'pera (caadr '(carne pesce uova)))
=> NIL

Simple enough, isn’t it?

Low and behold: subsequence

But what about searching for a sublist? What about searching for ‘(pera banana)? The following doesn’t work:

(find '(pera banana) *food-list* :key #'cadr)
=>NIL ;;WTF!!! AGAIN!!! WHY??

In order to solve this, remember what I’ve said about the comparison element by element! Yes, it’s made with the “eq” function! But you should know that “eq” works with nothing but symbols! We need the equal function in order to archive the result, but how can we force “find” using “equal”? The answer is in “:test”:

(find '(pera banana) *food-list* :test #'equal :key #'cadr)
=> (MELA (PERA BANANA)

Yes!

Conclusions

At the beginning some Lisp’s functions can be puzzling even if you are not a newbie with the functional programming, but this post should be useful to properly understand even the “find” function: Now let’s the hack begin! (cit. from Slime)

Bye!

Alfredo

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...