Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Not return anything from LISP/Scheme

Basically, I would like to use map to do selection in a list like

(define tbl '(a b c d))
(map (lambda (item 'c) (if (eq? item 'c) item (...what in else?) )))

The result I want is

'(c)

I tried leave the else part empty, it complains that the else part is needed. I tried

(display "foo") 

as else part and got

(#<void> #<void> c #<void>)

That is close.

Is there any way that I can use map to get '(c)? I know the recursive way, but I am wondering if map can do it as well. If not '(c), at least (# # c #) but not using the display hack to achieve a void type return value.


like image 915
Alfred Zhong Avatar asked Jul 16 '13 15:07

Alfred Zhong


3 Answers

You want to use filter, not map - because the output list will potentially have less elements than the input list. All those #<void> values returned by display are there because map will always include a result in the output list, even for those elements we're not interested in.

(define tbl '(a b c d))

(filter (lambda (item) (eq? item 'c)) tbl)
=> '(c)

Equivalently, and a bit shorter:

(filter (curry eq? 'c) tbl)
=> '(c)

map is used when you want to do something to each of the elements in the input list, without discarding elements. On the other hand, filter is used for selecting some of the elements in the input list, those that evaluate to #t for a given predicate, and filter is available in most Scheme interpreters, if it's not available you can import SRFI-1 or use the reference implementation.

There's no way to obtain '(c) using only map (it can be hacked using map plus apply or remove*, etc. but that's not the idea, is it?); if for some reason you have to use only map and don't mind returning a list with placeholders, here are a couple of alternatives:

(map (lambda (item) (if (eq? item 'c) item '%)) tbl) ; placeholder in else part
=> '(% % c %)

(map (lambda (item) (when (eq? item 'c) item)) tbl)  ; when has implicit #<void>
=> '(#<void> #<void> c #<void>)

Time for a little hacking. Using map plus apply (as explained in @WillNess' answer), this has the advantage of working in any RxRS interpreter and is the most portable solution, because it uses standard procedures:

(apply append (map (lambda (item) (if (eq? item 'c) (list item) '())) tbl))
=> '(c)

Using map plus remove*:

(remove* (list (void)) (map (lambda (item) (when (eq? item 'c) item)) tbl))
=> '(c)

For a change, a solution without map - using foldr instead:

(foldr (lambda (item a) (append (if (eq? item 'c) (list item) '()) a)) '() tbl)
=> '(c)

Of course, you can always implement your own version of filter using only standard procedures, this will also be portable across all RxRS interpreters:

(define (filter pred? lst)
  (cond ((null? lst)
         '())
        ((not (pred? (car lst)))
         (filter pred? (cdr lst)))
        (else
         (cons (car lst)
               (filter pred? (cdr lst))))))

(filter (lambda (item) (eq? item 'c)) tbl)
=> '(c)
like image 193
Óscar López Avatar answered Nov 10 '22 12:11

Óscar López


The simple "standard" trick is

(apply append (map (lambda(x)(if (eq? x 'c) (list x) '())) '(a b c d)))
;Value 12: (c)

which returns (c). The apply append ... map combo is known as mapcan in Common Lisp ("mapcan" for "map and concatenate"):

[1]> (mapcan #'(lambda(x)(if (eq x 'c) (list x))) '(a b c d))
(C)

MIT Scheme has this function too.

apply append flattens one level of its argument list, (apply append '((a) () (c) ())) == (append '(a) '() '(c) '()) --> (a c). Since empty lists disappear, it is useful for eliminating elements with map. This achieves the same effect as filter if you have one available (it is not in R5RS, but it is in SRFI1).

It can be used for other effects too, like doubling:

[2]> (mapcan #'(lambda(x)(if (evenp x) (list x x))) '(1 2 3 4))
(2 2 4 4)

As an aside, mapcan is what's known as list monad's "bind" (with arguments flipped), and (apply append ...) as its "join" operation. Indeed as it must be for any monad, for lists too bind m f == join (map f m).

This is also the basis for e.g. Haskell's list comprehensions:

Prelude> [y | x<-[1,2,3,4], even x, y<-[x,x]]
[2,2,4,4]
like image 29
Will Ness Avatar answered Nov 10 '22 14:11

Will Ness


You didn't mention your Scheme version/environment. Assuming you only have the most basic Scheme, it is easy enough to implement something:

(define (choose-if pred list)
  (let choosing ((list list) (rslt '()))
    (if (null? list)
        (reverse rslt)
        (choosing (cdr list)
                  (if (pred (car list))
                      (cons (car list) rslt)
                      rslt)))))

and then related:

(define (choose item list)
  (choose-if (lambda (elt) (eq? item elt)) list))

(define (choose-if-not pred list)
  (choose-if (lambda (elt) (not (pred elt))) list))

and use:

> (choose 'c '(a b c d))
(c)

You also have the option to use low-level primitives like:

(define (choose item list)
  (remq #f (map (lambda (elt) (eq? item elt)) list)))

or

(define (choose item list)
   (remp (lambda (elt) (not (eq? item elt))) list))
like image 20
GoZoner Avatar answered Nov 10 '22 13:11

GoZoner