The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages - More
> Other Programming Languages
|
Scheme. Reduce & filter
Discuss Scheme. Reduce & filter in the Other Programming Languages forum on Dev Shed. Scheme. Reduce & filter A place for discussing programming languages not covered in specific forums such as Assembler, COBOL, etc. - you get the idea.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

January 11th, 2006, 12:57 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
|
Scheme. Reduce & filter
Hi all,
I'm just learning Scheme in my spare time while at Uni. Currently trying to write a simplementation of filter & reduce. I think I have filter working pretty well, maybe not like I said I'm new. Here's my code:
Code:
(define filter
(lambda (fn values)
"This function is a tail recursive implementation of the filter function
found in other Lisp dialect."
(let loop ((v values)
(rest '()))
(let ((item (car v))
(next (cdr v))) ; Saves the car and cdr for efficiency.
(if (fn item)
;; Add the current 'item to 'rest if 'fn returned #t, then continue
;; though the list. Return 'this AND 'rest revsered.
(if (pair? next)
(loop next (cons item rest))
(reverse (cons item rest)))
;; Don't add the 'item to the 'rest list but continue on though the
;; list.
(if (pair? next)
(loop next rest)
(reverse rest)))))))
If anyone has any comments or tips please let me know I'd be very happy to hear them.
Mark.
__________________
programming language development: www.netytan.com – Hula
|

January 11th, 2006, 01:01 PM
|
 |
fork while true;
|
|
Join Date: May 2005
Location: England, UK
|
|
|
car and cdr are equivalent to first and rest right?
wouldn't it make more sense to choose one standard and stick with it?
EDIT: apart from that, looks good
Last edited by LinuxPenguin : January 11th, 2006 at 01:15 PM.
|

January 11th, 2006, 01:28 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
They are but it's not common to use first and rest for some reason, go figure  .
I'm happy migrating between them right now because they all seem to teach something different or better, I'm playing with Scheme to improve my recursion, which sucks to be fair  .
Plus I love how tidy it is, CL wins out for real world dev. Though only because of the massive number of library functions it includes. Quantity over quality, I haven't decided.
It'll get better,
take care and loves LP.
Mark.
|

January 11th, 2006, 01:32 PM
|
 |
fork while true;
|
|
Join Date: May 2005
Location: England, UK
|
|
Quote: | Originally Posted by netytan They are but it's not common to use first and rest for some reason, go figure  . |
Well, i blame all the old hippies who grew up when they were still registers... Miserable buggers
>>I'm happy migrating between them right now because they all seem to teach something different or better, I'm playing with Scheme to improve my recursion, which sucks to be fair  .
Recursion is reasonably well done in C, but i guess in lisp where there's not much choice, it could improve some more.
>>Plus I love how tidy it is, CL wins out for real world dev. Though only because of the massive number of library functions it includes. Quantity over quality, I haven't decided.
Well net effect is you'll end up writing your own library if you go the scheme route, CL is there in one package.
--James
|

January 11th, 2006, 02:19 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
Quote: | Originally Posted by LinuxPenguin Recursion is reasonably well done in C, but i guess in lisp where there's not much choice, it could improve some more.
Well net effect is you'll end up writing your own library if you go the scheme route, CL is there in one package. |
Recursion in Lisp if it's done correctly is as efficient as iteration, on a decent implementation with a native machine-code compiler you can in theory get better than C performance or even without depending on task  .
Note: with a Lisp -> C compiler you would obviously get C's speed also.
Can't fault you there though, Scheme by its very nature in minimal. There are few large libraries for different tasks but not included by default i.e. SLIB
Mark.
|

January 11th, 2006, 04:41 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
With a little help from Jens on comp.lang.scheme I came up with a revised version of the function based on a peice of code he posted. This looks a lot cleaner and should run as fast if not faster  .
Code:
(define filter
(lambda (fn values)
"This function is a tail recursive implementation of the filter
function found in other Lisp dialect."
(let loop ((v values)
(rest '()))
;; If there are items in v then CAR and CDR are saved; return
;; rest after reversing.
;;
;; Checks if fn => #t -> add item to rest & repeat.
;; => #f -> loop without adding item.
(if (pair? v)
(let ((item (car v))
(next (cdr v)))
(if (fn item)
(loop next (cons item rest))
(loop next rest)))
(reverse rest)))))
This simply involved moving the if to the outside and then everything fell into place, as you can see there is no duplicate code here  .
Mark.
|

January 12th, 2006, 12:16 PM
|
 |
fork while true;
|
|
Join Date: May 2005
Location: England, UK
|
|
problem with lisp in general, sometimes it's a bitch to work around the logic 
|

January 12th, 2006, 01:10 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
Just means you have to be more intelegent LP  or practice more, the latter being my approach.
Lisp really isn't hard to read once you know what you're looking at, else it's just looks like masses off odd words and symbols – like any other programming language You Don't Understand  .
Anyway back to the awesomeness of Scheme macro programming.
Later,
Mark.
|

February 9th, 2006, 05:27 AM
|
 |
Commie Mutant Traitor
|
|
Join Date: Jun 2004
Location: Norcross, GA (again)
|
|
You might want to take a look at the Scheme Request For Implementations (SRFIs), which are a system for defining semi-official libraries and extensions. The SRFI developers are working closely with the group working on R6RS, so there is some close collaboration on the direction Scheme will go in the future. Most current Scheme implementations support at least some SRFIs.
As for Scheme compilers, I usually use Dr Scheme for development (it has what I consider one of the best IDEs around), but if I were looking to ship the result I'd switch to a native-code compiler first (after compatibility checking against the MIT reference implementation and perhaps a few other such as SCM, Scheme-48 and STK if the code doesn't use any R5RS-specific code). Chicken, Gambit-C , Bigloo and Scheme->C (the last of which is only R4RS, though) are each supposed to be quite efficient. For real crunch, though, the winner has to be STALIN , which may well be the most heavily optimizing compiler for any language to date. Though it does take a while to finish a build  and it doesn't support the hygenic macros. If you still want to do one of your own, though, you might want to check out the "90 Minute Scheme to C Compiler" article that was mentioned on Lambda-The-Ultimate a couple years back.
Last edited by Schol-R-LEA : February 9th, 2006 at 05:32 AM.
|

February 9th, 2006, 12:03 PM
|
 |
Hello World :)
|
|
Join Date: Mar 2003
Location: Hull, UK
|
|
Quote: | Originally Posted by Schol-R-LEA You might want to take a look at the Scheme Request For Implementations (SRFIs), which are a system for defining semi-official libraries and extensions. The SRFI developers are working closely with the group working on R6RS, so there is some close collaboration on the direction Scheme will go in the future. Most current Scheme implementations support at least some SRFIs.
As for Scheme compilers, I usually use Dr Scheme for development (it has what I consider one of the best IDEs around), but if I were looking to ship the result I'd switch to a native-code compiler first (after compatibility checking against the MIT reference implementation and perhaps a few other such as SCM, Scheme-48 and STK if the code doesn't use any R5RS-specific code). Chicken, Gambit-C , Bigloo and Scheme->C (the last of which is only R4RS, though) are each supposed to be quite efficient. For real crunch, though, the winner has to be STALIN , which may well be the most heavily optimizing compiler for any language to date. Though it does take a while to finish a build  and it doesn't support the hygenic macros. If you still want to do one of your own, though, you might want to check out the "90 Minute Scheme to C Compiler" article that was mentioned on Lambda-The-Ultimate a couple years back. |
  thanks Schol, I'm going to look at the links you posted. Just downloading the movies. You're signature is actually what first took me too schemers.org what seems like a Very long time ago.
Didn't actually get into it until recently, after learning CL  .
Thanks again!
Mark.
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|