Using Scheme abstract list functions
Moderators: phlip, Moderators General, Prelates
Using Scheme abstract list functions
I am frustrated. My latest CS assignment mostly consists of solving previouslysolved 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 derecursifying, 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
Anyway, as part of a permutations function (and helper functions) that I'm derecursifying, 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
 Location: The Googleplex
 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:
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 shortestfirst 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.
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 shortestfirst 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) [[]]
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.

 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))))
Re: Using Scheme abstract list functions
Obscure Clojure solution:
Code: Select all
(defn xkcd [coll]
(let [mreverse (partial map reverse)
transfn #(cons (cons %2 (first %1)) %1)
core (partial reduce transfn '(()))]
(> 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
 Location: The Googleplex
 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+\
Ctrl+\

 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...)
(checkexpect (listofpermute ’(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
(listofsubset ’(1 2 3)) produce ’(() (1) (2) (3) (1 2)
(1 3) (2 3) (1 2 3)).
I am wondering how do write this code
using implicit function (map, foldr, foldl...)
(checkexpect (listofpermute ’(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
(listofsubset ’(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
 Location: The Googleplex
 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)))
Re: Using Scheme abstract list functions
anhquang300722 wrote:Dear,
I am wondering how do write this code
using implicit function (map, foldr, foldl...)
(checkexpect (listofpermute ’(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.
(listofsubset ’(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.

 Posts: 4
 Joined: Tue Dec 01, 2009 2:59 am UTC
Re: Using Scheme abstract list functions
cant figure out

 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.
Reason: Added [code] tags
Reason: Added [code] tags

 Posts: 4
 Joined: Tue Dec 01, 2009 2:59 am UTC
Re: Using Scheme abstract list functions
(define (mysubset L)
(foldr (lambda (z t)
(foldr (lambda (x y)
(append (list x)
(list (cons z x))
y))
empty
t))
(list empty) L))
(mysubset (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))
(mysubset empty)
>>>>(list empty)
basically, i am done with Subset.
just permutation left...help !
(foldr (lambda (z t)
(foldr (lambda (x y)
(append (list x)
(list (cons z x))
y))
empty
t))
(list empty) L))
(mysubset (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))
(mysubset empty)
>>>>(list empty)
basically, i am done with Subset.
just permutation left...help !
Who is online
Users browsing this forum: No registered users and 8 guests