Multiply in Scheme for cons lists

Question

I was able to make a scheme code to add two cons lists in scheme. say , list1 - '( p . d) list 2 ' ( p p p . d) my custom add function using cdr & car concepts , can do ( p p p p . d) as is expected.

However, I now want to multiply both & based on number of p's , I have a custom function that gives me list count . say , for list1 -> 1 list2-> 3

I also can manage to detect if any one of two lists is empty , so I output 'd.

But the real issue is when it comes to multiplication. list1 - '(p p . d) list2 - '(p p p p p . q) result expected - (2 * 5 = 10 p's) so '(p p p p p p p p p p . z)

I tried using while loop , do while , add custom function , but I cannot seem to figure out how to do it. Maybe some guidance can help me :)

I want to build a custom function since I don't wish to use a set ! or anything that makes process easier but want to understand recursion the way it could work in this case :).

What is d and z? Usually the sum of two lists are the standard procedure append but it cannot do dotted lists since (a . b) appended to (a . b) is (a a . b) according to you, but what about the first lists b?? You have written code you say, but where is it? If you want help you need to show some effort. — Sylwester
Your logic is good but the problem lies in in the details of your code, hence with only the logic and no code it's hard for us to guess what you are doing wrong... Why don't you rewrite it (it would take no more then 2 minutes if you know the logic you are following) so we can check it ? — Kevin

Daniel Jour Daniel Jour · Accepted Answer · 2015-10-05T00:52:04

I'm adding this as an answer since it seems to address your original issue, trying to implement Peano numbers using cons lists in scheme.

For that one starts with the zero value and functions to increment and decrement numbers.

;; We define our abstraction for zero
(define zero 'D)

;; Increment a number, i.e. get its successor
(define (inc number)
    (cons 'P number))

;; Decrement a number, i.e. get its predecessor
(define (dec number)
    (cdr number))

This allows to traverse all (positive) integers. Upon these functions we can build an add function of recursive nature, exploiting:

a + 0 = a
a + b = (a + 1) + (b - 1)

Similarly an multiplication function can be build upon the add function, using:

a * 0 = 0
0 * b = 0
a * 1 = a
a * b = a + (a * (b - 1))

This leads to the following, though highly inefficient code:

;; Adding two numbers is done by "shifting" from one to the other, one by one.
;; a + b = (a + 1) + (b - 1)
(define (add lhs rhs)
    (if (eq? rhs zero)
        lhs
        (add (inc lhs) (dec rhs))))

;; Multiplying the dumb way:
;; a * b = a + (a * (b - 1))
(define (mul lhs rhs)
    (if (or (eq? rhs zero) (eq? lhs zero))
        zero
        (if (eq? rhs (inc zero))
            lhs
            (add lhs (mul lhs (dec rhs))))))

(Live example)

Multiply in Scheme for cons lists

1 Answers