PROBLEM SCHEME

[emerald123]

Well it isn't exactly a homework...

But since I started learning scheme , I am finding it very tough to solve the problem which is a below;

I tried for 7 days , but I am unable to decide how I would tackle this scheme problem.

(f ’((y g r) (5 3 1) (p q e )))
should give output ’((y 5 p) (g 3 q) (r 1 e))

limitation is input is always assumed to be a proper list.
it can be v proper lists , my function should create v such outputs

like for 3 pairs it generated 3

I learnt using pair? I can detect if its a proper list.
Then car can give me 1st pair , further car gives me 1 st element.

cdr gives me rest of list.

I do not want to use any ! function since I want to understand recursion.
but here I cannot decide for k lists , how to make it work.


Basically, for finite say 10 pairs , I can do it , but don't know how to for k pairs and return exactly k such results.

[emerald123]

So far I tried but find it really hard ...
I understood car and cdr ... So as per my concept , I guess this can be a valid example...


input list is say '((s t) (5 6) (o j)) given to my f(tuples) then I should get a
new list '((s 5 o) (t 6 j)) like this apply same logic for k lists containing k elements...

;> (car(car '((s t) (5 6) (o j)))) gives me 's
;> (car(car(cdr '((s t) (5 6) (o j))))) gives me 5
;> (car(car(cdr(cdr '((s t) (5 6) (o j)))))) gives me 'o
--------------------------------------------------------------------
;> (car(cdr(car '((s t) (5 6) (o j))))) gives me 't
;> (car(cdr(car(cdr '((s t) (5 6) o j))))) gives me 6
;> (car(cdr(car(cdr(cdr '((s t) (5 6) (o j))))))) gives me 'j –

-----------------------------------------------------------------------

I am so unclear since I tried a function but it always gives me empty list '() .
Maybe somebody can help me solve this difficult problem.

[Goheeca]

I do not want to use any ! function

Do you mean not using functions with side effects? The short solution:

Code: Select all

(define (transpose data)
  (apply map list data))

since I want to understand recursion.

Let's define own map, list:

Code: Select all

(define my-list (lambda elems elems))

(define (single-map fn lst)
    (if (null? lst)
        '()
        (cons (fn (car lst))
              (single-map fn (cdr lst)))))

(define my-map
    (lambda args
        (let ((fn (car args))
              (lsts (cdr args)))
            (if (member '() lsts)
                '()
                (cons   (apply fn (single-map car lsts))
                        (apply my-map (cons fn
                                            (single-map cdr lsts))))))))

That was written quickly, I'm not sure if it's reduced or not, if there are any redundancies. Well, you can get the idea from that.

[emerald123]

I came across this solution but cannot understand it at all ... If only someone could explain me step wise ...............

; helper procedure for filling a list with arbitrary values at the end
(define (fill lst val num)
(append lst
(build-list num (const val))))

; helper procedure for transposing a list of lists
(define (transpose lsts)
(apply map list lsts))

; main procedure
(define (list-tuples lsts)
(let* ((lengths (map length lsts)) ; obtain the length of each sublist
(max-length (apply max lengths))) ; find out the maximum length
(transpose ; build new sublists element-wise
(map (lambda (lst len) ; build sublists of the right length
(fill lst '() (- max-length len))) ; fill sublists with '()
lsts
lengths))))





Expected sample output :

(list-tuples '((m n o) (1) (x y)))
=> '((m 1 x) (n () y) (o () ()))


This works beautifully , But I want to know is there a way I can get more simpler elegant solutions ?

Asking since I am a beginner but I am obsessed with above problem for 2 months

[Goheeca]

As OP requested, I'm providing here a detailed explanation of my solution.

First of all I'm versed in Common Lisp not so much in Scheme. But let's go:

I'd been looking for &rest counterpart from CL and find this neat construction, where in place of the argument list you put just one symbol/variable, you end up with all of the arguments in that variable.

Code: Select all

(define my-list (lambda elems elems))

single-map is just only a special case of map function, which maps a function over only one list. single-map is a helper function used in the general map function (my-map). That's necessary, because it's used for extracting first elements from lists given to the my-map. If the my-map was used itself in those places instead of single-map we would achieve infinite recursion!

Code: Select all

(define (single-map fn lst)
    (if (null? lst)
        '()
        (cons (fn (car lst))
              (single-map fn (cdr lst)))))

Finally, my-map itself. It's using the same construcion as my-list for slurping all of the lists handed over together with the function which is going to be applied. The condition for termination is whether any list is null (in CL: some #'null ...). In the solution I'm testing (by member) whether the list of lists contains an null list.

Code: Select all

(define my-map
    (lambda args
        (let ((fn (car args))
              (lsts (cdr args)))
            (if (member '() lsts)
                '()
                (cons   (apply fn (single-map car lsts))
                        (apply my-map (cons fn
                                            (single-map cdr lsts))))))))

For completeness, I'm presenting an implementation of member function:

Code: Select all

(define (my-member elem lst)
    (cond ((null? lst) #f)
          ((eq? elem (car lst)) elem)
          (else (my-member elem (cdr lst)))))

[emerald123]

Well I am trying to debug single map, which I feel is vital to understand my-map function

I tried my-member too but get lots of errors when trying to trace it.

Also, it needs some examples where some input is traced stepwise as it happens in actual recursion.

It would be the most helpful for many scheme beginners like me.

Like say (single-map car '((a b) (c d))) &

(single-map cdr '((a b) (c d))).
I get correct results.

But I don't know how to debug.
Like in C , C++ & java esp on Netbeans I could debug , use watches see values as they are changing and getting updated step by step.
I am unable to do so on scheme.

Tried repl.it scheme editor but cannot see any debugging option.

Whenever I try to put say car / cdr instead of fn & I try it in editor , I get a list without " ' " and when I try to apply same logic recursively on that I get errors.

My efforts so far to debug it on repl.it ...

Code: Select all

 (single-map car '((a b) (c d)))
=> (a c)
   (car(car '((a b) (c d))))
=> a
   (cdr '((a b) (c d)))
=> ((c d))
   (car(car ((c d))))
Error: execute: unbound symbol: "d" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (car(car '((c d))))
=> c
   (cons (a) (c))
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons '(a) '(c))
=> ((a) c)
   (cons a '(c))
Error: execute: unbound symbol: "a" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons a c)
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons a c '())
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons (a c) '() )
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons (a) (c))
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]

Tried few more now ................

Code: Select all

 (cons a b)
Error: execute: unbound symbol: "b" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons]
   (cons 'a 'b)
=> (a . b)
   (cons (car(car '((a b) (c d)))))
Error: cons: wrong number of arguments (expected: 2 got: 1) [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons]
   (car(car '((a b) (c d))))
=> a
   (car(cdr(car(car '((a b) (c d))))))
TypeError: undefined is not an object (evaluating 'this.initialize.apply') [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr]
   (cdr '((a b) (c d)))
=> ((c d))
   (car ((c d))) 
.. 
Error: execute: unbound symbol: "d" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr]
   (car '((c d)))
=> (c d)
   (car '(c d))
=> c
   (cons 'a 'c)
=> (a . c)
   (single-map car '((a b) (c d)))
=> (a c)
   (cons '(a (c)))
Error: cons: wrong number of arguments (expected: 2 got: 1) [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (cons a '())
Error: execute: unbound symbol: "a" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (cons 'a '())
=> (a)
   (cons 'c '())
=> (c)
   (cons (a) (c) )
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (cons '(a) '(c))
=> ((a) c)
   (cons 'a '(c))
=> (a c)
   (cdr '((a b) (c d))) 
.. 
=> ((c d))
   (car(car ((c d))))
Error: execute: unbound symbol: "d" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (car(car '((c d)))) 
.. 
=> c
   (cdr '((c d))) 
.. 
=> ()
   (cons c '())
Error: execute: unbound symbol: "c" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (cons a '(c))
Error: execute: unbound symbol: "a" [my-map, (anon), single-map, cdr, single-map, cdr, single-map, (anon), single-map, cdr, single-map, cdr, (anon), cons, cons, cons, cdr, cons]
   (cons 'a 'c)
=> (a . c)
   (cons 'c '())
=> (c)
   (cons 'a '(c))
=> (a c)

I cannot understand how I get lists using single-map since as per scheme editor I get lists without ' and program should give error when I reach to cons!

[emerald123]

Say if I give my-map a list '((d c f g) (4 5) (l m n)) then output is '((d 4 l) (c 5 m) (f () n) (g () ())).

Basically if I give it a list such as '((d c) (6 7) (l p))

I should get output as '((d 6 l) (c 7 p)) which isn't happening.
In fact i debugged a lot in vain & realized this.

I tested member function too.

I think '(a b) is a member of '((a b) ( c d)) but I guess it works differently.

Since car '((a b) (c d)) gives me '(a b) & cdr gives me '(c d)).

Code: Select all

> (car '((a b) (c d)))
'(a b)
> (my-member '(a b) '((a b) (c d)))
#f
> (my-member 'b '(a b c d))
'b
> (my-member  3 '(a s d f  1 2 3 4))
3

I was testing my-map too , so far , only single map works as expected.

(my-map '((d g) (6 9) (w r)))

I should get '((d 6 w) (g 9 r)) as output as per single map logic.

Also for below code , I should get '((a c) (b d)) but I get errors only.

Code: Select all

> (my-map car '((d c) (6 7) (l p)))
'(d 6 l)
> (my-map cdr '((d c) (6 7) (l p)))
'((c) (7) (p))
> (my-map car '((c) (7) (p)))
'(c 7 p)
> 

I think this is what needs to be added to my-map function to make it work as expected ...

Code: Select all

> (my-list '(d 6 l) '(c 7 p))
'((d 6 l) (c 7 p))

Tried a few things more now .........

Code: Select all

> (my-list 'a 'b 'c 'd)
'(a b c d)
> (my-list '(a b) '(c d))
'((a b) (c d))


> (single-map car '((a b) (1 2) (x y)))
'(a 1 x)
> (single-map car '((a b) (1 2) (x y)))
'(a 1 x)
> (cdr '((a b) (1 2) (x y)))
'((1 2) (x y))
> (single-map cdr '((a b) (1 2) (x y)))
'((b) (2) (y))
> (single-map car '((b) (2) (y)))
'(b 2 y)
> (single-map cdr '((b) (2) (y)))
'(() () ())
> 

[emerald123]

Finally a rather complex expression but what my-map is supposed to do .

I guess my-list might do as below :

Code: Select all

> (my-map car '((d c) (6 7) (l p)))
'(d 6 l)

> (my-map car (my-map cdr '((d c) (6 7) (l p))))
'(c 7 p)

(my-list (my-map car '((d c) (6 7) (l p))) (my-map car (my-map cdr '((d c) (6 7) (l p)))))
'((d 6 l) (c 7 p))

[Goheeca]

(my-map '((d g) (6 9) (w r)))

I should get '((d 6 w) (g 9 r)) as output as per single map logic.

my-map don't solve your problem, it's an implementation of standard map function. It's a part of solution, which still is:

Code: Select all

(define (transpose data)
  (apply my-map my-list data))

I think '(a b) is a member of '((a b) ( c d)) but I guess it works differently.

If you want the my-member function to work with non-trivial values, you have to change eq? to equal? in its definition.

[emerald123]

Thanks so much!!!

Only one issue , if I change it to equals ? its working great.

But if I get it a list such as '((a b c) (1) ( x y z)) , I only get '((a 1 x)) where I should be getting '((a 1 x) (b () y) (c () z)).
So if it doesn't have a mapping , it should put ().

I really want learn scheme programming from you sir.
And debugging too.

Issue is I am still not able to think recursively in scheme