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.
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)
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)
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.
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.
(I'll be around later today for questions. I'm actually going to be taking off for a while rather immediately after posting this.)