Using Scheme abstract list functions

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

Moderators: phlip, Moderators General, Prelates

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

Using Scheme abstract list functions

Postby Rippy » Sat Oct 17, 2009 1:37 pm UTC

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

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Using Scheme abstract list functions

Postby Xanthir » Sat Oct 17, 2009 3:27 pm UTC

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)))

User avatar
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

Postby Berengal » Sat Oct 17, 2009 3:46 pm UTC

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

Postby littlebuddy » Sat Oct 17, 2009 7:16 pm UTC

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

Postby qbg » Sun Oct 18, 2009 8:43 pm UTC

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)))

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

Re: Using Scheme abstract list functions

Postby BrainMagMo » Thu Oct 29, 2009 10:00 am UTC

Code: Select all

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

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Using Scheme abstract list functions

Postby Xanthir » Thu Oct 29, 2009 1:47 pm UTC

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)))

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

Re: Using Scheme abstract list functions

Postby BrainMagMo » Tue Nov 03, 2009 5:21 pm UTC

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

Postby anhquang300722 » Tue Dec 01, 2009 3:15 am UTC

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)).

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Using Scheme abstract list functions

Postby Xanthir » Tue Dec 01, 2009 3:40 am UTC

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

Postby qbg » Tue Dec 01, 2009 4:06 am UTC

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

Postby anhquang300722 » Tue Dec 01, 2009 6:00 am UTC

cant figure out

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

Re: Using Scheme abstract list functions

Postby anhquang300722 » Tue Dec 01, 2009 6:11 am UTC

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

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

Re: Using Scheme abstract list functions

Postby anhquang300722 » Thu Dec 03, 2009 1:10 am UTC

(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 !


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests