## Using Scheme abstract list functions

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Rippy
Posts: 2101
Joined: Sun Jul 22, 2007 11:27 pm UTC
Location: Ontario, Can o' Duh

### Using Scheme abstract list functions

I am frustrated. My latest CS assignment mostly consists of solving previously-solved problems, except using nothing but abstract list functions (filter, foldr, foldl, and map primarily). No recursion allowed. I have been racking my brain for hours over this stuff, and have managed to pull through one problem. I can see how it's a great learning exercise, but damn it's tough to get into the mindset to do this kind of thing.

Anyway, as part of a permutations function (and helper functions) that I'm de-recursifying, I have a helper function, and as part of that helper function, I need a function that will do this:

'(2 3 4) -> '( empty (2) (2 3) (2 3 4) )

Despite having figured out more complex functions, I CANNOT get this one. As soon as I do, the whole function will fall into place. Could anyone give me some tips on how to accomplish this? I thought of having a map which went through each element and called a foldr operation which somehow stopped when it reached a value equal to that element. But that wouldn't work if there were duplicate numbers in the list. Foldr feels like it has the right behavior, but I can't think of an operation for it that would take advantage of that.

Thanks!

-RIppy

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Using Scheme abstract list functions

That's probably a bit difficult to grasp at first, because of the way that lists work - it's not often needed to get successive prefixes of a list.

However, the easiest way to solve this (though certainly not the most performant) is to translate it to a previously solved problem. Reverse the list, then collect the tails. I dunno scheme specifically, but in CL it'd be:

Code: Select all

`(cons nil (reverse (maplist 'reverse (reverse (list 1 2 3 4)))))`

Reverse the whole list, collect and reverse each tail to bring it back to the previous order, then reverse the result to get the tails into shortest-first order. Finally add nil to the front.

Since REVERSE copies the list first, you can swap the later two REVERSE calls with destructive versions for efficiency.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

### Re: Using Scheme abstract list functions

I'm going to be less than fully helpful and post an uncommented solution in haskell. Since it's for homework, I feel justified in doing so.

foldr (\e s -> []:map (e:) s) [[]]
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

littlebuddy
Posts: 43
Joined: Thu Jun 04, 2009 5:40 pm UTC

### Re: Using Scheme abstract list functions

Here is a version that does work, in scheme, and uses map and foldr, although the procedure that foldr applies is not strictly a list function, but it may help:

Code: Select all

`(define xkcd   (lambda (l)    (map reverse (foldr (lambda (x y)                     (cons (cdr (car y)) y))                 (list (reverse l))                 l))))`

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: Using Scheme abstract list functions

Obscure Clojure solution:

Code: Select all

`(defn xkcd [coll]  (let [mreverse (partial map reverse)        trans-fn #(cons (cons %2 (first %1)) %1)        core (partial reduce trans-fn '(()))]    (-> coll core mreverse reverse)))`

BrainMagMo
Posts: 185
Joined: Tue Jul 22, 2008 6:22 am UTC
Location: Southern California
Contact:

### Re: Using Scheme abstract list functions

Code: Select all

`;without folding(define (xkcd lst)  (cons ()      (reverse       (map reverse            (map (λ (num)                   (member num (reverse lst)))                 (reverse lst))))))`

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Using Scheme abstract list functions

Man I wish I had a lambda key on my keyboard. I never use the & symbol. I should remap it. And heck, lambda will serve as an ampersand in a pinch.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

BrainMagMo
Posts: 185
Joined: Tue Jul 22, 2008 6:22 am UTC
Location: Southern California
Contact:

### Re: Using Scheme abstract list functions

i don't have lambda, Dr Scheme does!
Ctrl+\

anhquang300722
Posts: 4
Joined: Tue Dec 01, 2009 2:59 am UTC

### Re: Using Scheme abstract list functions

Dear,

I am wondering how do write this code

using implicit function (map, foldr, foldl...)

(check-expect (list-of-permute ’(1 2 3)) ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1
2) (3 2 1)))

the other is not matter

and

(list-of-sub-set ’(1 2 3)) produce ’(() (1) (2) (3) (1 2)
(1 3) (2 3) (1 2 3)).

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Using Scheme abstract list functions

I am also wondering, anhquang300722. Perhaps you could tell me?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: Using Scheme abstract list functions

anhquang300722 wrote:Dear,

I am wondering how do write this code

using implicit function (map, foldr, foldl...)

(check-expect (list-of-permute ’(1 2 3)) ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1
2) (3 2 1)))

If you know how to pick and remove an item from a sequence, and you know how to recurse, this is easy. Making it use higher order functions can be a bit harder.
(list-of-sub-set ’(1 2 3)) produce ’(() (1) (2) (3) (1 2)
(1 3) (2 3) (1 2 3)).

The inductive proof that I'm familiar with on the size of the power set of a set makes this one easy too. Might be a bit easier than the previous one to do using higher order functions.

anhquang300722
Posts: 4
Joined: Tue Dec 01, 2009 2:59 am UTC

### Re: Using Scheme abstract list functions

cant figure out

anhquang300722
Posts: 4
Joined: Tue Dec 01, 2009 2:59 am UTC

### Re: Using Scheme abstract list functions

Code: Select all

`(define (cross1 lst1 lst2)  (foldr (lambda (x y)                     (append (foldr (lambda (z t)                                                        (cons (list x z) t)) empty lst2) y)) empty lst1))(cross1 (list 1 empty) (list 2 empty))>>>>>>>>>(list (list 1 2) (list 1 empty) (list empty 2) (list empty empty))(cross1 (list 3 empty)        (cross1 (list 1 empty) (list 2 empty)))>>>>>>>>>>>>>(list (list 3 (list 1 2)) (list 3 (list 1 empty)) (list 3 (list empty 2)) (list 3 (list empty empty)) (list empty (list 1 2)) (list empty (list 1 empty)) (list empty (list empty 2)) (list empty (list empty empty)))`

I have this one but cant handle the empty and cons cases
Last edited by phlip on Tue Dec 01, 2009 7:41 am UTC, edited 1 time in total.

anhquang300722
Posts: 4
Joined: Tue Dec 01, 2009 2:59 am UTC

### Re: Using Scheme abstract list functions

(define (my-sub-set L)
(foldr (lambda (z t)
(foldr (lambda (x y)
(append (list x)
(list (cons z x))
y))
empty
t))
(list empty) L))

(my-sub-set (list 1 2 3))
>>>(list empty (list 1) (list 2) (list 1 2) (list 3) (list 1 3) (list 2 3) (list 1 2 3))
(my-sub-set empty)
>>>>(list empty)

basically, i am done with Subset.

just permutation left...help !