Functional Challenge #1

  • (2 Pages)
  • +
  • 1
  • 2

29 Replies - 3718 Views - Last Post: 17 January 2011 - 09:35 AM

#1 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Functional Challenge #1

Post icon  Posted 03 January 2011 - 02:37 PM

*
POPULAR

Hello, World! Welcome to the Functional Programming forum's first challenge. I'm sure everybody has noticed how very little I've actually done to raise activity levels in the forum I lead, but I was mostly just waiting for today so that I could get maximum attention by users (it being a Monday and all).

I know not everybody on the forum is all that introduced to functional programming. And I know that, if I'm careful, I can make challenges that everybody can have fun doing. See, lot's of languages support functional programming on some level, so I'm not always (and probably not very often) going to limit my challenges to languages like Clojure and Haskell, though I will always make challenges where they will apply.

Todays challenge will be around forever, but the challenge officially ends on the 17th, and that's when I will select a winner. This challenge will be reasonably trivial, and thus there will be no prizes. However, expect there to be prizes for upcoming more difficult challenges.



What do I do!?!

This challenge is easy. I want you to implement three of the most fundamental higher order functions that almost every functional programming language provides: map, reduce, and filter.

Higher order functions are functions that either take one or more functions as arguments or return a function. They are a fundamental part of functional programming, because they make it easy to compose together very small functions to accomplish very large tasks.

Now, let's talk about what each of these functions do so that you know how to implement them. Each of these functions do something with a sequential collection, such as a list. I'd like for all of the challenge entries to be immutable. I'll explain this at the end.



map
The 'map' function takes a single function as it's argument and then at least one sequential collection. It applies the function to each element of the collection in turn, replacing that element with the result of the function. Here are some examples from my Clojure REPL:

user=> (map inc [1 2 3 4])
(2 3 4 5)
user=> (map dec [1 2 3 4])
(0 1 2 3)
user=> (map (fn [x] (+ x 5)) [1 2 3 4])
(6 7 8 9)



Simple enough?



filter
The 'filter' function takes a predicate and a collection. A predicate is a function that returns either true or false. It applies the function to each element of the collection and removes any elements that the function returns 'false' on, keeping the ones that return true. Examples:

user=> (filter odd? [1 2 3 4 5 6])
(1 3 5)
user=> (filter even? [1 2 3 4 5 6])
(2 4 6)





reduce
This is the big one. reduce is awesome because a bunch of other higher order functions (including map) can be written in terms of it.

The 'reduce' function takes a function, an optional 'starter' value, and a sequential collection. If your language doesn't support multiple arities (or function overloading on arguments) or something similar, and you can't work around it easily, don't worry about it.

If no starter element is supplied, reduce takes the first and second element of the collection and applies the function to them. It then applies the function to the result of that and the next element of the collection, and then to the result of that and the next and so on until the collection is depleted, in which case it returns this 'accumulated' value. If you do supply a starter value, then that starter value and the first element of the collection are given to the function on the first run rather than the first two elements of the collection.

Was that a lot to take in? Well, here are some examples:

user=> (reduce + [1 2 3 4]) ; An easy way to implement a function that 'sums' a collection.
10
user=> (reduce + 10 [1 2 3 4]) ; Same as above but with a starter value.
20



I can't provide more in-depth examples because I'd pretty much give away how you could implement 'map' in terms of reduce. Just keep in mind that the starter value *could* be an empty collection, and thus your function could add to that collection.




Rules
Use any language you like that supports the things necessary to complete the challenge. That should be pretty much any modern language.

Do not piggyback on core implementations in your language. If your language already has these functions, don't use them. Implement them yourself.

Be immutable. Immutability in this context essentially means that you never change a collection in place. Instead, when you need to change a collection, you create an entirely new collection instead. Thus, rather than have map return the same collection, only molested, it should return an entirely new collection with the changes made. This is slower than just changing the collection in most languages, because it requires a whole copy of the old structure when you create the new one. Clojure is an exception because it has persistent immutable collections that share structure, and thus do not have to make an entire copy every time a change is made.

Please use spoiler tags around your code so as to not give away implementations.

Have fun!

(I'll be around later today for questions. I'm actually going to be taking off for a while rather immediately after posting this.)

Is This A Good Question/Topic? 8
  • +

Replies To: Functional Challenge #1

#2 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,050
  • Joined: 15-July 08

Re: Functional Challenge #1

Posted 03 January 2011 - 03:30 PM

Here's the first one. I probably butchered it, but it's my first freely written function ever:

Spoiler


edited: fixed formatting

This post has been edited by Dogstopper: 03 January 2011 - 03:42 PM

Was This Post Helpful? 1
  • +
  • -

#3 YamNad  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 9
  • View blog
  • Posts: 120
  • Joined: 11-July 09

Re: Functional Challenge #1

Posted 03 January 2011 - 03:51 PM

Clojure, of course. :)

Spoiler

This post has been edited by YamNad: 03 January 2011 - 06:21 PM

Was This Post Helpful? 2
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2270
  • View blog
  • Posts: 9,496
  • Joined: 29-May 08

Re: Functional Challenge #1

Posted 03 January 2011 - 04:29 PM

vb.net's functional side
Spoiler

Or you could write your own using the Iterator in the AsyncCTP
Spoiler

This post has been edited by AdamSpeight2008: 03 January 2011 - 04:29 PM

Was This Post Helpful? 1
  • +
  • -

#5 GWatt  Icon User is offline

  • member icon

Reputation: 278
  • View blog
  • Posts: 3,078
  • Joined: 01-December 05

Re: Functional Challenge #1

Posted 03 January 2011 - 05:24 PM

Scheme's the only one I know.

map:
Spoiler


filter:
Spoiler


reduce:
Spoiler

This post has been edited by GWatt: 03 January 2011 - 07:15 PM

Was This Post Helpful? 1
  • +
  • -

#6 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Functional Challenge #1

Posted 03 January 2011 - 05:54 PM

View PostDogstopper, on 03 January 2011 - 09:30 PM, said:

Here's the first one. I probably butchered it, but it's my first freely written function ever:

Spoiler


edited: fixed formatting


You actually butchered the formatting more than anything there. Unless lining up arguments, you should only indent two spaces. Check out the Lisp formatting guide that is pinned here. If you're using Emacs, it ought to be formatting it properly for you in the first place. Bizarre.

If you do reduce, keep in mind that map can be implemented in terms of reduce. I might even give bonus points for implementing map in terms of reduce. ;)

View PostYamNad, on 03 January 2011 - 09:51 PM, said:

Clojure, of course. :)

Spoiler


Fun stuff! I see you finally got into Clojure a bit. Cool! Your reduce example is tail recursive, so you might want to switch out your reduce calls with 'recur' so that Clojure can optimize the tail call. Clojure doesn't have tail call optimization because the JVM doesn't have it. However, it can optimize tail calls with recur and keep it from overflowing.

Good work everybody!

Interesting implementations there, Adam. They're pretty cool, even if they do make my eyes bleed. :P
Was This Post Helpful? 1
  • +
  • -

#7 YamNad  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 9
  • View blog
  • Posts: 120
  • Joined: 11-July 09

Re: Functional Challenge #1

Posted 03 January 2011 - 06:19 PM

Raynes, on 04 January 2011 - 12:54 AM, said:

Fun stuff! I see you finally got into Clojure a bit. Cool!


A bit?! A lot! :P (YamNad = MayDaniel) ;)

Raynes, on 04 January 2011 - 12:54 AM, said:

Your reduce example is tail recursive, so you might want to switch out your reduce calls with 'recur' so that Clojure can optimize the tail call.


Ah, indeed! I imagine I'd forgot to use 'recur' because I'd just wrote map/filter, which can call itself fine, and blindly continued the trend with reduce. Thanks for pointing that out. :)
Was This Post Helpful? 0
  • +
  • -

#8 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Functional Challenge #1

Posted 03 January 2011 - 06:29 PM

Oh, duh. There is another guy on here that I always get you confused with. Sorry! :P

A friend pointed out that you can also implement filter in terms of reduce. I'm not sure why I didn't mention that as well, but that's also something interesting you guys might choose to do.

Looking forward to more submissions. :>

This post has been edited by Raynes: 03 January 2011 - 06:31 PM

Was This Post Helpful? 0
  • +
  • -

#9 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,050
  • Joined: 15-July 08

Re: Functional Challenge #1

Posted 03 January 2011 - 07:00 PM

Raynes, my formatting got butchered because of the way DIC handles tabs. The copy and paste from Emacs had tabs in it. (At least the windows version did). I did that in like 5 minutes on my laptop. :P

YamNad, I really liked looking at yours. I learned a ton of generally WHAT I was not doing right. I tried implementing it lazy, but did it wrong. I'll try reduce next, to see if I can figure out the other two in terms of it.
Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2270
  • View blog
  • Posts: 9,496
  • Joined: 29-May 08

Re: Functional Challenge #1

Posted 03 January 2011 - 07:24 PM

View PostRaynes, on 04 January 2011 - 01:29 AM, said:

A friend pointed out that you can also implement filter in terms of reduce.


A Reduce-Based Filter
Spoiler


A Tidy Up of Iterator based implementations.
Spoiler

"Infinite" - Enumerations
Spoiler

Was This Post Helpful? 0
  • +
  • -

#11 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Functional Challenge #1

Posted 03 January 2011 - 08:47 PM

I'll go ahead and post my implementations:

Spoiler


I implemented reduce first and then implemented the other functions in terms of it. One disadvantage of this compared to something like YamNad's version (which was excellent, by the way) is that it's slower than it could be and instead of working with seqs, you're working with vectors instead. Reason being, you can't conj onto the end of a seq but only to the front, which is what I would have had to do to implement a version that worked with seqs. Thus, as a side effect of implementing the latter two functions in terms of reduce, they always return vectors. They can take any sequential collection just like the normal map and filter, but they'll always return a vector.

If you don't know Clojure, none of what I just said will make sense to you. Clojure has an abstraction for working with sequential collections called 'seq', and that's what its sequence library works on. Clojure's filter and map are both lazy, meaning they return lazy sequences like YamNad's examples did. Mine are not. Because of the nature of Clojure's sequences and lazy sequences, you wont find implementations like mine in Clojure's core.

My examples are mostly just for fun and to demonstrate how one can implement filter and map in terms of reduce. It really demonstrates the power of higher order functions, that one simple function like reduce can be used to abstract over such common tasks. Isn't functional programming beautiful?

This post has been edited by Raynes: 03 January 2011 - 08:51 PM

Was This Post Helpful? 0
  • +
  • -

#12 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2270
  • View blog
  • Posts: 9,496
  • Joined: 29-May 08

Re: Functional Challenge #1

Posted 03 January 2011 - 08:57 PM

I've implemented a few more (see latest blog entry)
Was This Post Helpful? 0
  • +
  • -

#13 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,050
  • Joined: 15-July 08

Re: Functional Challenge #1

Posted 03 January 2011 - 10:34 PM

I don't know if I've actually implemented reduce correctly. I get the correct answers for what I try, but I cannot find a way to feed it a function for map or filter, so that leads me to believe I haven't done it correctly.
Was This Post Helpful? 0
  • +
  • -

#14 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Functional Challenge #1

Posted 04 January 2011 - 12:42 AM

View PostDogstopper, on 04 January 2011 - 04:34 AM, said:

I don't know if I've actually implemented reduce correctly. I get the correct answers for what I try, but I cannot find a way to feed it a function for map or filter, so that leads me to believe I haven't done it correctly.


If you want, PM me and I'll talk you through it. You could make a new topic, but that would kind of kill the surprise. :P
Was This Post Helpful? 0
  • +
  • -

#15 dom96  Icon User is offline

  • D.I.C Regular

Reputation: 4
  • View blog
  • Posts: 256
  • Joined: 29-December 08

Re: Functional Challenge #1

Posted 04 January 2011 - 06:04 AM

All implemented with recursion :

Spoiler


Implementing filter and map in terms of reduce is too complicated for me, i'll try it again later though.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2