[Raynes]

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

[Dogstopper]

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

Spoiler

(defn mymap [fn s]
	    (if (not (empty? s))
		(conj (mymap fn (rest s)) (fn (first s)))))

edited: fixed formatting

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

[YamNad]

Clojure, of course.

Spoiler

(defn map [f coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (cons (f (first s)) (map f (rest s))))))

(defn filter [pred coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (let [[first & more] s]
        (if (pred first)
          (cons first (filter pred more))
          (filter pred more))))))

(defn reduce
  ([f coll] (let [[first & more] coll] (reduce f first more)))
  ([f val coll] (if-let [s (seq coll)]
                  (recur f (f val (first s)) (rest s))
                  val)))

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

[AdamSpeight2008]

vb.net's functional side

Spoiler

over ienumerables.
Map -> Enumerable.Select
Filter -> Enumerable.Where
Reduce -> Enumerable.Aggregate
Bind -> Enumerable.SelectMany

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

Spoiler

 <Extension()>
  Iterator Function Bind(Of T, R)(ByVal src As IEnumerable(Of T), ByVal sel As Func(Of T, IEnumerable(Of R))) As IEnumerable(Of R)
    Dim e = src.GetEnumerator
    If e Is Nothing Then Exit Function
    While e.MoveNext
      Dim ie = sel(e.Current).GetEnumerator
      If ie Is Nothing Then Continue While
      While ie.MoveNext
        Yield ie.Current
      End While
    End While
  End Function
  <Extension()>
  Iterator Function Map(Of T, R)(ByVal src As IEnumerable(Of T), ByVal f As Func(Of T, R)) As IEnumerable(Of R)
    Dim e = src.GetEnumerator
    If e Is Nothing Then Exit Function
    While e.MoveNext
      Yield f(e.Current)
    End While
  End Function
  <Extension()>
  Function Reduce(Of T, R)(ByVal src As IEnumerable(Of T), ByVal seed As R, ByVal f As Func(Of R, T, R)) As R
    Dim e = src.GetEnumerator
    If e Is Nothing Then Return seed
    While e.MoveNext
      seed = f(seed, e.Current)
    End While
    Return seed
  End Function
  <Extension()>
  Iterator Function Filter(Of T)(ByVal src As IEnumerable(Of T), ByVal pred As Func(Of T, Boolean)) As IEnumerable(Of T)
    Dim e = src.GetEnumerator
    If e Is Nothing Then Exit Function
    While e.MoveNext
      If pred(e.Current) Then Yield e.Current
    End While
  End Function

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

[GWatt]

Scheme's the only one I know.

map:

Spoiler

(define map
  (lambda (func ls)
    (let map-loop
      ([ls ls])
      (if (null? ls)
        `()
        `(,(func (car ls)) . ,(map-loop (cdr ls)))))))

filter:

Spoiler

(define filter
    (lambda (pred? ls)
      (let filter-loop
        ([ls ls])
        (cond
          [(null? ls) `()]
          [(pred? (car ls)) `(,(car ls) . ,(filter-loop (cdr ls)))]
          [else (filter-loop (cdr ls))]))))

reduce:

Spoiler

(define-syntax reduce
    (syntax-rules ()
      [(__ func start ls) (let reduce-loop
                            ([value start]
                             [l ls])
                            (if (null? l)
                                value
                                (reduce-loop (func value (car l)) (cdr l))))]
      [(__ func ls) (if (null? ls)
                        `()
                        (reduce func (car ls) (cdr ls)))]))

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

[Raynes]

Dogstopper, 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

(defn mymap [fn s]
	    (if (not (empty? s))
		(conj (mymap fn (rest s)) (fn (first s)))))

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.

YamNad, on 03 January 2011 - 09:51 PM, said:

Clojure, of course.

Spoiler

(defn map [f coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (cons (f (first s)) (map f (rest s))))))

(defn filter [pred coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (let [[first & more] s]
        (if (pred first)
          (cons first (filter pred more))
          (filter pred more))))))

(defn reduce
  ([f coll] (let [[first & more] coll] (reduce f first more)))
  ([f val coll] (if-let [s (seq coll)]
                  (reduce f (f val (first s)) (rest s))
                  val)))

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.

[YamNad]

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

[Raynes]

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

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

[Dogstopper]

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.

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.

[AdamSpeight2008]

Raynes, 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

  <Extension()>
  Function ReduceBasedFilter(Of T)(ByVal src As IEnumerable(Of T), ByVal pred As Func(Of T, Boolean)) As IEnumerable(Of T)
    If src Is Nothing Then Return Enumerable.Empty(Of T)()
    Return Reduce(src,
                Function(_a, _c)
                  Return Enumerable.Concat(_a, If(pred(_c), Enumerable.Repeat(_c, 1), Enumerable.Empty(Of T)))
                End Function, Enumerable.Empty(Of T))
  End Function

A Tidy Up of Iterator based implementations.

Spoiler

  <Extension()>
  Public Function Reduce(Of T)(ByVal src As IEnumerable(Of T), ByVal f As Func(Of T, T, T)) As T
    Dim seed As T : For Each x In src : seed = f(seed, x) : Next
    Return seed
  End Function

  <Extension()>
  Public Function Reduce(Of T, R)(ByVal src As IEnumerable(Of T), ByVal f As Func(Of R, T, R), Optional ByVal seed As R = Nothing) As R
    For Each x In src : seed = f(seed, x) : Next
    Return seed
  End Function

  <Extension()>
  Iterator Function Bind(Of T, R)(ByVal src As IEnumerable(Of T), ByVal sel As Func(Of T, IEnumerable(Of R))) As IEnumerable(Of R)
    If src Is Nothing Then Exit Function
    For Each x In src
      For Each xx In sel(x)
        Yield xx
      Next
    Next
  End Function

  <Extension()>
  Iterator Function Filter(Of T)(ByVal src As IEnumerable(Of T), ByVal pred As Func(Of T, Boolean)) As IEnumerable(Of T)
    If src Is Nothing Then Exit Function
    For Each x In src
      If pred(x) Then Yield x
    Next
  End Function

  <Extension()>
  Public Iterator Function Map(Of T, R)(ByVal src As IEnumerable(Of T), ByVal f As Func(Of T, R)) As IEnumerable(Of R)
    If src Is Nothing Then Exit Function
    For Each x In src
      Yield f(x)
    Next
  End Function
 

"Infinite" - Enumerations

Spoiler

 Iterator Function Natural() As IEnumerable(Of Integer)
    Dim x As Integer = 0
    While True
      Yield x
      x += 1
    End While
  End Function

Alongside a Zip Function.

  Iterator Function Zip(Of T1, T2, R)(
    ByVal first As IEnumerable(Of T1), ByVal second As IEnumerable(Of T2),
    ByVal f As Func(Of T1, T2, R)) As IEnumerable(Of R)
    Dim se = second.GetEnumerator
    For Each x In first
      If se.MoveNext Then
        Yield f(x, se.Current)
      Else
        Exit For
      End If
    Next
  End Function

Now it is possible to have a map function that includes the index

 <Extension()>
  Public Iterator Function Map(Of T, R)(ByVal src As IEnumerable(Of T), ByVal f As Func(Of T, Integer, R)) As IEnumerable(Of R)
    If src Is Nothing Then Exit Function
    For Each x In Zip(Of T, Integer, R)(src, Natural, f)
      Yield x
    Next
  End Function

Take & Skip
May not be the best way, but it works.

 <Extension()>
  Iterator Function _Take(Of T)(ByVal src As IEnumerable(Of T), ByVal number As Integer) As IEnumerable(Of T)
    If number <= 0 Then Throw New ArgumentOutOfRangeException
    For Each x In Zip(src, Natural, Function(_x, _i) New Tuple(Of T, Integer)(_x, _i))
      If x.Item2 > number Then Exit For
      Yield x.Item1
    Next
  End Function

  <Extension()>
  Iterator Function _Skip(Of T)(ByVal src As IEnumerable(Of T), ByVal number As Integer) As IEnumerable(Of T)
    If number <= 0 Then Throw New ArgumentOutOfRangeException
    For Each x In Zip(src, Natural, Function(_x, _i) New Tuple(Of T, Integer)(_x, _i))
      If x.Item2 <= number Then Continue For
      Yield x.Item1
    Next
  End Function

[Raynes]

I'll go ahead and post my implementations:

Spoiler

(defn my-reduce
  ([f [top & bottom]] (my-reduce f top bottom))
  ([f start [top & more :as all]]
     (if (seq all)
       (recur f (f start top) more)
       start)))

(defn my-map [f coll] (my-reduce #(conj % (f %2)) [] coll))

(defn my-filter [f coll] (my-reduce #(if (f %2) (conj % %2) %) [] coll))

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

[AdamSpeight2008]

I've implemented a few more (see latest blog entry)

[Dogstopper]

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.

[Raynes]

Dogstopper, 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.

[dom96]

All implemented with recursion :þ

Spoiler

map' :: (a -> B)/> -> [a] -> [b]
map' _ []     = []
map' f (x:xs) = (f x) : map' f xs

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' f (x:xs) =
  if x1 then x : (filter f xs) else filter' f xs
  where x1 = f x
  
reduce :: (a -> b -> a) -> a -> [b] -> a
reduce _ s []     = s
reduce f s (x:xs) = reduce f (f s x) xs

Implementing filter and map in terms of reduce is too complicated for me, i'll try it again later though.