racket: (my-filter p lst) function with lambda and foldr

Question

I am trying to implement a function (my-filter p lst) by using lambda, map and foldr.

What I have so far is:

(define (my-filter1 p lst)
  (cond [(empty? lst) empty]
        [(p (first lst))
         (cons (first lst) (my-filter1 p (rest lst)))]
        [else (my-filter1 p (rest lst))]))

It works fine, but I how can I change the code to one using lambda, map and foldr?

Thanks in advance!

soegaard soegaard · Accepted Answer · 2016-06-10T09:43:20

First we need to see how foldr works.

  (foldr k e '(1 2 3))
= (k 1 (k 2 (k 3 e)))

It helps to think of k as cons and of e as empty. For example:

  (foldr cons empty '(1 2 3))
= (cons 1 (cons 2 (cons 3 empty)))
= (list 1 2 3)

To make a filter we need to use a "cons" that only prepends the element if the element, if the predicate is fulfilled.

(define (kons x xs)
  (if (p x)           ; where p is the predicate
      (cons x xs)
      xs))

Given this custom "cons" function we can write filter as

 (foldr kons empty '(1 2 3))

A complete example:

#lang racket

(define p odd?)

(define (kons x xs)
  (if (p x)
      (cons x xs)
      xs))

(foldr kons empty '(1 2 3 4 5 6))

The result is:

 '(1 3 5)

To turn this into a filter function use this template:

(define (my-filter p xs)
   (define (kons x xs) ...)
   (foldr ...))

racket: (my-filter p lst) function with lambda and foldr

1 Answers