Lists from lambda functions

Translator's note: The original is here . All the examples in the original are written in JavaScript, but I decided to translate them into Scheme. I am sure that it has not become less clear, but all the beauty of this language is visible.
UPD: added to all the examples on the right are also original JavaScript examples.


If you close your eyes to the practical side of computers - size, weight, price, heat, etc., what does a programming language really need? Let's explore this question.

To understand the examples in this article, basic concepts of functions in LISP (Scheme) are needed. If you understand what this code will type, feel free to read further:
')

(define x 10) (define (fy) (display x) (newline) (display y) (newline) ) (define gf) (f 1) (g 2)

var x = 10; var f = function(y) { console.log(x); console.log(y); } var g = f; f(1); g(2);

This article is just a warm-up for the brain, and not something that could be used in real code. But as a guitarist plays scales that he never uses in a real song, so programmers should warm up their brains from time to time.

I will use Scheme for demonstration, but any other language that supports functions as first-class functions, and lexical scope (closures, mostly) will do.

If you have already seen such things (maybe in SICP or The Little Schemer ), you should just run through the code in search of something new for yourself.

If you have n't seen anything like this before, there is something tasty for you. For the first time, everything will look extremely strange. Move slowly. Go to the next part, only by understanding the previous one. The concepts outlined here may not seem intuitive, but they are built from very simple parts.

And finally: if you are stuck in a place, do not despair. Tracking a function on paper can be a very good way to understand how it works (I recommend buying a good portable table for a comfortable letter). If that doesn't help, just close the article and go back to reading tomorrow. Sometimes new concepts have to wander around a bit in your head before they find their place.

• Lists
  
  • Lists of if
  • But where did the data go?
  • Building on these foundations
    
    • map
    • filter
    • and, or, not
    
    
  • Lists from lambda functions
  
  
• Numbers
  
  • What is a Number?
  • inc, dec
  • is_zero
  • add
  • sub
  • sub, pow
  • is_equal
  • less_than, greater_than
  
  
• Closing the circle
  
  • nth
  • drop take
  • length
  
  
• Conclusion

1 Lists

Well, let's start! One of the most frequently executed processes by a programmer is data grouping. Scheme has built-in lists for this (otherwise it would not be LISP;):

(define names (list "Alice" "Bob" "Candice"))

var names = ["Alice", "Bob", "Candice"];

But what if there were no lists in Scheme? Could we make them, or something similar to them, on our own?

To answer this question, let's think about what minimal set of things we need to create something like a list. There are many ways to do this, but we will consider only one of them.

We need four things to work with the list:

• The concept of "empty list"
  
• A way to add an item to the top of the list
  
• A way to get the first item in a list
  
• A way to get everything except the first list item
  

If there are these four things, we can build on their basis whatever we wish. For example, to create a list from one item, you can add this item to the beginning of an empty list.

There are many ways to implement these four parts - I will use functions. Here is their sketch:

(define empty_list '()) (define (prepend el lst) ...) (define (head lst) ...) (define (tail lst) ...) (define (is_empty lst) ...)

var empty_list = null; var prepend = function(el, list) { // ... }; var head = function(list) { // ... }; var tail = function(list) { // ... }; var is_empty = function(list) { // ... };

Here are descriptions of each of these definitions.

empty_list is a special value representing a list of zero items. It can do anything, so I will use the standard '() from Scheme. We will come back to this later.

(prepend 1 some_list) returns a new list that looks like an old one with 1 inserted at its beginning. So, if we want to create a list of numbers 1 and 2 , we can write (prepend 1 (prepend 2 empty_list)) , or “add 2 to the result of adding 1 to the empty list”

(head some_list) returns the first item in the list. The result of the head from the empty list is not defined, so you need to be careful and do not do it!

(tail some_list) returns a new list that looks like the old one without the first element. And again, calling tail from an empty list will ruin everything.

(is_empty some_list) will return #t if the given list is empty and #f otherwise.

Once we have these four functions (plus a special value for the empty list), we can start building things based on them, so let's find out how to implement them!

1.1 Lists from If

You might think that you can use cons , car and cdr , but this article is an experiment to find what we really need, let's not use the built-in language features if this can be avoided.

So, if we do not want to use the possibilities of the language, what do we have left? Well, for now, we only have functions (and '() ), so let's try them!

Here is the first working version of the implementation of lists:

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

Paste it into your favorite Scheme interpreter and play around:

(define e empty_list) (display (is_empty e)) ; #t (define names (prepend "Alice" (prepend "Bob" (prepend "Candice" empty_list ) ) ) ) (display (is_empty names)) ; #f (display (head names)) ; Alice (display (tail names)) ; Some function representing the list of ("Bob", "Candice") (display (head (tail names))) ; Bob

var e = empty_list; console.log(is_empty(e)); // true var names = prepend("Alice", prepend("Bob", prepend("Candice", empty_list))); console.log(is_empty(names)); // False console.log(head(names)); // Alice console.log(tail(names)); // Some function representing the list of ("Bob", "Candice") console.log(head(tail(names))); // Bob

1.2 But where did the data go?

Have the definitions of these features surprised you? Lists seem to be such an important, object-oriented concept, but there are only functions!

Let's see how they actually work. For a start, the concept of an “empty list” is pretty straightforward:

(define empty_list '()) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var is_empty = function(list) { return list === null; };

You could choose any value. '() fits, so I used it.

Now to the most important prepend : prepend .

(define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) )

var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } };

This is where all the magic happens. Let's think it over.

First of all, we know that by adding something to the top of the list we get the (new) list back. Thus, the return value of prepend must be a list.

One glance at the code is enough to understand that the prepend function returns. So in our little thought experiment, the list is simply the (lambda) Scheme function!

So, what do we need to do with the lists (aside from checking for emptiness, which we have already covered)? Well, we need to get the head and tail. When we call (prepend ht) , we just pass the head and tail as arguments! So, in prepend we return a function that knows how to get its head or tail back on demand.

This means that the “list” is a function “that knows how to get your head or tail back on demand.” It turns out that our functions head and tail should only ask well!

(define (head lst) (lst "head") ) (define (tail lst) (lst "tail") )

var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); };

That's all! We made the list in 24 lines of code, using nothing but functions. Before you go any further, make sure you understand why this works. You can practice on a piece of paper.

1.3 Building on this foundation

Now that we have lists, let's practice and implement some common things based on them.

map

One of the frequent tasks on the lists is to create a new passage in the cycle of the old and apply some function to each element. This is called a " map ".

(define (map fn l) (if (is_empty l) empty_list (prepend (fn (head l)) (map fn (tail l))) ) )

var map = function(fn, l) { if (is_empty(l)) { return empty_list; } else { return prepend(fn(head(l)), map(fn, tail(l))); } };

If you are not used to recursive definitions of the type of such, you might want to spend a few minutes and write how it works. For example, like this:

(define (square x) (* xx)) (define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define squared_numbers (map square numbers)) ; (map square (1 2 3)) ; (prepend (square 1) (map square (2 3)) ; (prepend (square 1) (prepend (square 2) (map square (3)))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) (map square '())))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) '()))) ; (prepend (square 1) (prepend (square 2) (prepend 9 '()))) ; (prepend (square 1) (prepend (square 2) (9))) ; (prepend (square 1) (prepend 4 (9))) ; (prepend (square 1) (4 9)) ; (prepend 1 (4 9)) ; (1 4 9)

var square = function(x) { return x * x; } var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var squared_numbers = map(square, numbers); // map(square, [1, 2, 3]) // prepend(square(1), map(square, [1, 2, 3])) // prepend(square(1), prepend(square(2), map(square, [3]))) // prepend(square(1), prepend(square(2), prepend(square(3), map(square, [])))) // prepend(square(1), prepend(square(2), prepend(square(3), []))) // prepend(square(1), prepend(square(2), prepend(9, []))) // prepend(square(1), prepend(square(2), [9])) // prepend(square(1), prepend(4, [9])) // prepend(square(1), [4, 9]) // prepend(1, [4, 9]) // [1, 4, 9]

I write Scheme-style lists ( (1 2 3) ), but in fact there are functions returned from prepend .

If you still haven't completely figured it out, track the execution (map square empty_list) , and then the execution (map square (prepend 10 empty_list)) .

Recursive thinking in this style requires some practice. I have a bunch of notebooks written here . Experienced guitarists are learning new material slowly and methodically, and there is no reason for programmers not to do the same. Observing the proliferation and destruction of function calls can help you understand how these things actually work, while looking at the code for a long time will give nothing.

filter

Now we will start moving a little faster, but you still need to make sure that you understand absolutely everything before moving on. Spend a lot of time, write on paper, run the code, feel it.

The next function we build on the lists is filter . It takes a function and a list and returns a new list containing those elements of the source for which this function returns #t . Here is an example:

(define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define (is_odd x) (equal? (modulo x 2) 1)) (filter is_odd numbers) ; (1 3)

var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var is_odd = function(x) { return x % 2 === 1; } filter(is_odd, numbers); // [1, 3]

Now we implement the filter :

(define (filter fn l) (if (is_empty l) empty_list (if (fn (head l)) (prepend (head l) (filter fn (tail l))) (filter fn (tail l)) ) ) )

var filter = function(fn, l) { if (is_empty(l)) { return empty_list; } else if (fn(head(l))) { return prepend(head(l), filter(fn, tail(l))); } else { return filter(fn, tail(l)); } };

Take a break, check for some examples. Move on just by understanding this completely.

and, or, not

Deviate from the course and implement the "support" functions. They are not related to the lists, but we still need them.

(define (not x) (if x #f #t ) ) (define (and ab) (if a (if b #t #f ) #f ) ) (define (or ab) (if a #t (if b #t #f ) ) )

var not = function(x) { if (x) { return false; } else { return true; } }; var and = function(a, b) { if (a) { if (b) { return true; } else { return false; } } else { return false; } }; var or = function(a, b) { if (a) { return true; } else { if (b) { return true; } else { return false; } } };

Naturally, Scheme already has all of this, but we are trying to avoid using all the possibilities of the language if we can do without them. How far can we go only with functions and if ?

A small note: these are just the usual Scheme functions, so (and ab) does not use abbreviated computations, like an embedded macro. It does not hurt our goals, but do not forget about it.

1.4 Lists of lambda functions

Now, after a little practice, let us return again to the definitions of our functions:

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

In this implementation, I care about a few things. Our goal is to use as few features of the language as possible, but we have already used enough! I can count at least five:

• Functions
  
• if condition
  
• Strings
  
• Boolean values ​​( #f and #t , is_empty result)
  
• Test for equality ( equal? )
  

It turns out that we can get rid of almost all of this, but only at the cost of readability (and mental strain).

Let's first get rid of strings, equality tests, and even if :

(define (prepend el lst) (lambda (selector) (selector el lst) ) ) (define (head lst) (lst (lambda (ht) h)) ) (define (tail lst) (lst (lambda (ht) t)) )

var prepend = function(el, list) { return function(selector) { return selector(el, list); }; }; var head = function(list) { return list(function(h, t) { return h; }); }; var tail = function(list) { return list(function(h, t) { return t; }); };

You should have a snack before trying to figure it out! There are no lines, no equality checks, no if , but you still have lists!

The prepend function returns a function, just as in the previous version the “list” was actually a function that knows how to get its head and tail back on demand.

This time, we turned the "request" inside out. In this version, the “list” is “a function that will give another function both head and tail upon request.” Now the calling function receives both parts and decides which one to use.

Let's look at the head function:

• head accepts a list and calls (list ...) , which means "Hey, list, please give all your data to this little function that I give."
  
• The list calls (... el lst) , which means “Okay, little function, here's my head and tail”.
  
• The auxiliary function is actually (lambda (ht) h) , so when called with the head and tail, it returns the head as arguments.
  
• head takes the result and passes it directly to the calling function.
  

tail works in exactly the same way, only its helper function returns the second argument (tail), not the first.

That's all! Checks for equality and if disappeared. Can you tell where they are? What now instead of them?

Before proceeding further, let's clean up the implementation of the empty list. She still uses '() and equality tests. Remove them and make everything more or less similar.

In order to do this, you will need to change a little the other functions, but if you understand everything to this point, then this change will not be difficult.

(define (empty_list selector) (selector '() '() #t) ) (define (prepend el lst) (lambda (selector) (selector el lst #f) ) ) (define (head lst) (lst (lambda (hte) h)) ) (define (tail lst) (lst (lambda (hte) t)) ) (define (is_empty lst) (lst (lambda (hte) e)) )

var empty_list = function(selector) { return selector(undefined, undefined, true); }; var prepend = function(el, list) { return function(selector) { return selector(el, list, false); }; }; var head = function(list) { return list(function(h, t, e) { return h; }); }; var tail = function(list) { return list(function(h, t, e) { return t; }); }; var is_empty = function(list) { return list(function(h, t, e) { return e; }); };

We made the lists a little smarter. In addition to the ability to transfer the auxiliary function of the head and tail, they can now tell whether they are empty. We made the head and tail functions take into account (and ignore) the third argument, and also made the is_empty function the same as the others.

Finally, we redefined empty_list in the same way as everyone else, instead of a special magic value. The empty list is now the same as the usual one - this is a function that takes another one and tells it: "My head and tail are '() and I am an empty list."

I used '() , because I didn’t find anything better in Scheme, but you can use any other value at your discretion. Since we will be careful not to call head or tail from an empty list, these values ​​will never come up anyway.

In the end, we implemented the basic elements of lists with only two things:

• Functions
  
• #t and #f for empty lists.
  

If you want, think how you can get rid of the second (and in this case, do you really get rid of, or just use implicitly some Scheme feature?).

2 Numbers

The definitions of prepend , head and tail look pretty brainwashing. However, the definitions of map and filter are more straightforward.

The reason for this is that we have hidden the implementation details of the lists in those first four functions. We did all the dirty work of creating lists of almost nothing, and then hid it behind a simple prepend , head and tail interface.

The idea of ​​creating some things from simple components and abstracting them into “black boxes” is one of the most important ideas of computer science and programming, so let's go a little further and implement the numbers.

2.1 What is a Number?

In this article, we will consider only non-negative numbers. You can try to add support for negative numbers yourself.

How can we imagine a number? Well, obviously, you can use Scheme numbers, but this is not so cool, since we are trying to minimize the number of language features used.

One way of representing a number is a list whose length is equal to that number. We can say that (1 1 1) means "three", ("cats" #f) means "two", and '() means "zero".

The elements of this list do not in themselves have any meaning, so take something that already exists: an empty list! Feel it:

(define zero empty_list) ; '() (define one (prepend empty_list empty_list)) ; ( '() ) (define two (prepend empty_list (prepend empty_list empty_list))) ; ( '() '() )

var zero = empty_list; // [] var one = prepend(empty_list, empty_list); // [ [] ] var two = prepend(empty_list, prepend(empty_list, empty_list)); // [ [], [] ]

2.2 inc, dec

We would like to do something with our numbers, so let's write functions that work with the list representation of numbers.

Our main building material is inc and dec (increment and decrement).

(define (inc n) (prepend empty_list n) ) (define (dec n) (tail n) )

var inc = function(n) { return prepend(empty_list, n); }; var dec = function(n) { return tail(n); };

To add one to the number, we simply insert another item into the list. So, (inc (inc zero)) means "two."

To subtract one, we simply remove one of the elements: (dec two) means “one” (do not forget that we ignore negative numbers).

2.3 is_zero

At the beginning of working with lists, we often used is_empty , so it is worth doing the is_zero function:

(define (is_zero n) (is_empty n) )

var is_zero = function(n) { return is_empty(n); };

Zero is just an empty list!

2.4 add

Adding a unit is easy, but we probably want to be able to add arbitrary numbers. Now with inc and dec , it's pretty easy to do this:

(define (add ab) (if (is_zero b) a (add (inc a) (dec b)) ) )

var add = function(a, b) { if (is_zero(b)) { return a; } else { return add(inc(a), dec(b)); } };

This is another recursive definition. When adding numbers, there are two possibilities:

• If b is zero, the result is just a
  
• Otherwise, the addition of a and b is the same as the addition of a+1 and b-1
  

In the end, b “ends” and the answer becomes a (which increases as b decreases).

Please note that there is not a word about the lists! The information that “numbers are lists” turned out to be hidden behind is_zero , inc and dec , so that we can ignore it and work at the “number” abstraction level.

2.5 sub

Subtraction is similar to addition, but instead of increasing a as b decreases, we will reduce them both together:

(define (sub ab) (if (is_zero b) a (sub (dec a) (dec b)) ) )

var sub = function(a, b) { if (is_zero(b)) { return a; } else { return sub(dec(a), dec(b)); } };

Now we can write something like (add two (sub three two)) and the result will be the representation of the number "three" in our system (which, of course, is a list of three elements).

Stop for a minute and remember that inside numbers are actually lists, and inside lists there is nothing but functions.We can add and subtract numbers and, within all of this, just functions moving back and forth, expanding into other functions and contracting as you call, and this wriggling handful of lambdas somehow represents 1+1=2. Cool!

2.6 mul, pow

For training we realize the multiplication of numbers:

(define (mul ab) (if (is_zero b) zero (add a (mul a (dec b))) ) )

var mul = function(a, b) { if (is_zero(b)) { return zero; } else { return add(a, mul(a, dec(b))); } };

Availability addmakes the task quite simple. 3 * 4 is the same as 3 + 3 + 3 + 3 + 0. Trace the function on a piece of paper, if the meaning of what is happening begins to elude you, and come back when you feel you are ready.

pow(exponentiation) is similar mul, but instead of adding copies of a number, we will multiply them, and the “basis” of the recursion will be one, not zero.

(define (pow ab) (if (is_zero b) one (mul a (pow a (dec b))) ) )

var pow = function(a, b) { if (is_zero(b)) { return one; } else { return mul(a, pow(a, dec(b))); } };

2.7 is_equal

Another problem about numbers is a test for equality, so let's write it:

(define (is_equal nm) (if (and (is_zero n) (is_zero m)) #t (if (or (is_zero n) (is zero m)) #f (is_equal (dec n) (dec m)) ) ) )

var is_equal = function(n, m) { if (and(is_zero(n), is_zero(m))) { return true; } else if (or(is_zero(n), is_zero(m))) { return false; } else { return is_equal(dec(n), dec(m)); } };

There are three cases:

• If both numbers are zero, they are
  
  
• If one and only one of the numbers is zero, they are not equal
  
  
• Otherwise, subtract one from each and try again.
  
  

When this function is called with two non-zero arguments, both of them will decrease until one of them “ends” first, or they “end” at the same time.

2.8 less_than, greater_than

Similarly, you can implement and less_than:

(define (less_than ab) (if (and (is_zero a) (is_zero b)) #f (if (is_zero a) #t (if (is_zero b) #f (less_than (dec a) (dec b)) ) ) ) )

var less_than = function(a, b) { if (and(is_zero(a), is_zero(b))) { return false; } else if (is_zero(a)) { return true; } else if (is_zero(b)) { return false; } else { return less_than(dec(a), dec(b)); } };

In contrast is_equal, there are four cases:

• If both numbers are zero, then ano less thanb
  
• Otherwise, if a(and only a) is zero, then it is less thanb
  
• Otherwise, if b(and only b) is zero, then ait cannot be less than b(negative numbers are not considered)
  
• Otherwise, reduce both and try again.
  

And again, both numbers are decreasing, until at least one of them "ends", and the result of the comparison is determined by which of them "ended" first.

One could do something the same for greater_than, but there is a simpler way:

(define (greater_than ab) (less_than ba) )

var greater_than = function(a, b) { return less_than(b, a); };

2.9 div, mod

Now that we have less_than, we can implement the division and remainder:

(define (div ab) (if (less_than ab) zero (inc (div (sub ab) b)) ) ) (define (rem ab) (if (less_than ab) a (rem (sub ab) b) ) )

var div = function(a, b) { if (less_than(a, b)) { return zero; } else { return inc(div(sub(a, b), b)); } }; var rem = function(a, b) { if (less_than(a, b)) { return a; } else { return rem(sub(a, b), b); } };

These two are a bit more complicated than the first three basic operations, because we cannot use negative numbers. Be sure to understand how it works.

3 Closing the circle

By now, we already have a (very basic) working system of numbers, built on lists. Let's go back to the beginning and implement more list functions that use numbers.

3.1 nth

To get the n-th element of the list, we will simply delete the elements from it and decrease the number nuntil we reach zero:

(define (nth ln) (if (is_zero n) (head l) (nth (tail l) (dec n)) ) )

var nth = function(l, n) { if (is_zero(n)) { return head(l); } else { return nth(tail(l), dec(n)); } };

In fact, we now have two lists, the elements of which we delete as we iterate, since nthis is the number that is the list, and decremoves the element from it. But this is much more pleasant to read when the implementation of lists is abstracted, is it not?

3.2 drop, take

Let's make two useful functions for working with lists - dropand take.

(drop l three)will return the list without the first three items.

(take l three)returns the first three items in the list.

(define (drop ln) (if (is_zero n) l (drop (tail l) (dec n)) ) ) (define (take ln) (if (is_zero n) empty_list (prepend (head l) (take (tail l) (dec n))) ) )

var drop = function(l, n) { if (is_zero(n)) { return l; } else { return drop(tail(l), dec(n)); } }; var take = function(l, n) { if (is_zero(n)) { return empty_list; } else { return prepend(head(l), take(tail(l), dec(n))); } };

3.3 slice

The “slice” of the list becomes a very simple task, once implemented drop, takeand the subtraction of numbers:

(define (slice l start end) (take (drop l start) (sub end start)) )

var slice = function(l, start, end) { return take(drop(l, start), sub(end, start)); };

First, we drop everything before start, and then select the desired number of elements.

3.4 length

We can define length- the length of the list - recursively, like everything else:

(define (length l) (if (is_empty l) zero (inc (length (tail l))) ) )

var length = function(l) { if (is_empty(l)) { return zero; } else { return inc(length(tail(l))); } };

The length of the empty list is 0, and the length of a non-empty list is one plus the length of its tail.

If your thoughts have not yet become entangled in a strong knot, think about this:

• Lists are made of functions.
  
• Numbers are made from lists whose length represents a number
  
• length it is a function that takes a list and returns its length as a number (a list whose length is equal to this number)
  
• And only now we have determined length, although we use numbers (which use the length of the list to represent a number) for a long time!
  

Are you already dizzy? If not, look at this:

(define mylist (prepend empty_list (prepend empty_list empty_list ) ) ) (define mylistlength (length mylist))

var mylist = prepend(empty_list, prepend(empty_list, empty_list)); var mylistlength = length(mylist);

mylistThis is a list of two empty lists.

mylistlengththis is the length mylist...

what is the "two" ...

which is represented by a list of two empty lists ...

and this is it mylist!

4 Conclusion

If you like this little tangled story, I highly recommend you read The Little Schemer . This is one of the first books that actually changed my understanding of programming. Do not be afraid that Scheme is used there - the language doesn’t really matter.

I also created gist (original JavaScript examples here ) with all the code from the article. Feel free to fork it and use it for experiments.

Just to practice recursive functions, you can implement the following:

• append - add item to end of list
  
• concat - union of two lists
  
• minand max- finding the smaller (larger) of the two numbers
  
• remove- the same as filter, only returns a list of those elements on which the testing function (predicate) returns#f
  
• contains_number - verification of the number belonging to the list
  

Or, if you want something more serious, implement large concepts based on those already created:

• Negative numbers
  
• Non-negative rational numbers
  
• Negative rational numbers
  
• Associative Lists
  

Remember, the point is not to create something that works well on a real computer. Instead of thinking about how to make a particular combination of transistors and circuits accept the right voltages, think of “calculations” in a beautiful, perfect, abstract sense.