Functional Challenge #2

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1676 Views - Last Post: 06 March 2011 - 01:25 PM

#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 #2

Post icon  Posted 17 January 2011 - 09:56 AM

This week's challenge to achieve polymorphism in a functional language.

A lot of people incorrectly assume that polymorphism is an Object Oriented thing. This is not true. Polymorphism is an important and generally useful thing, and the vast majority of functional languages provide facilities to accomplish polymorphism.

The challenge itself is simple: write a polymorphic 'range' function that works for more than one type of thing.

Some languages already have ranges, especially numeric ranges. 'range' takes a lower bound and an upper bound and generates a sequence from the lower bound up to the upper bound. Here is an example using Clojure's range function:

user=> (range 1 10)
(1 2 3 4 5 6 7 8 9)



As you can see, I generated a range of numbers from 1 to 10 (10 isn't inclusive, so we only get 9 numbers).

Generating a range of numbers is usually easy. Once you've got that implemented, you'll need a version of range that works on something else. An idea for this 'something else' could be characters. You could have it generate a sequence of characters, such as from a to z.

The most important thing is that it be polymorphic. In Clojure you'd use protocols or multimethods, in Haskell you'd use type classes, in Common Lisp, CLOS, etc. You have to write range for at least two different types. I suggested numbers and characters, but feel free to be creative.

There are no specific languages that you have to use, but keep in mind that this challenge doesn't make a lot of sense for *every* language. For example, Java and C# submissions wouldn't be very interesting, because they're predominately object oriented languages. Languages like Scala, OCaml, and Common Lisp that aren't predominately object oriented but support object orientation are fair submissions. Use your best judgement.

This challenge will end on the 31st of this month, at which time it will be unpinned from this forum. The thread wont, however, be deleted.

Have fun, and if you have any questions, feel free to ask them. If you need help with anything that doesn't regard specifics of this challenge but in individual implementations, please ask in a new topic rather than this one.

This post has been edited by Raynes: 17 January 2011 - 10:02 AM


Is This A Good Question/Topic? 2
  • +

Replies To: Functional Challenge #2

#2 efcasado  Icon User is offline

  • New D.I.C Head

Reputation: 5
  • View blog
  • Posts: 2
  • Joined: 08-January 11

Re: Functional Challenge #2

Posted 17 January 2011 - 01:49 PM

Here I post my Erlang approach.

Spoiler


I've tested it with the following test cases:

1> ranges:range(1,10).
[1,2,3,4,5,6,7,8,9,10]
2> ranges:range(10,1).
[10,9,8,7,6,5,4,3,2,1]
3> ranges:range(a,z).
"abcdefghijklmnopqrstuvwxyz"
4> ranges:range(z,a).
"zyxwvutsrqponmlkjihgfedcba"
5> ranges:range(1,z).  
** exception throw: {error,"Types does not match."}
     in function  ranges:range/2
6> ranges:range(aa,bb).
** exception throw: {error,"Type do not supported."}
     in function  ranges:range/2
7> ranges:range(65,90).
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"


This post has been edited by efcasado: 17 January 2011 - 01:56 PM

Was This Post Helpful? 2
  • +
  • -

#3 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 #2

Posted 17 January 2011 - 02:31 PM

Nice submission. I'm not all that introduced to Erlang. Nice to see something you aren't used to every now and then.
Was This Post Helpful? 0
  • +
  • -

#4 YamNad  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: Functional Challenge #2

Posted 17 January 2011 - 05:08 PM

I've hacked a submission in Clojure w/ protocols and type extensions. I dislike the use of assertions, and I can't decide whether the final line should be 'apply str' or 'map str'. (I think the former makes more sense, despite non-laziness.) It's not incredibly idiomatic, and I prefer your implementation. I'm not sure that a String range makes much sense, but I wrote one anyway, for fun.


Spoiler


> (range 10)
(0 1 2 3 4 5 6 7 8 9)

> (range \a \j)
(\a \b \c \d \e \f \g \h \i \j)

> (range "a" "j")
"abcdefghij"

This post has been edited by YamNad: 18 January 2011 - 06:37 AM

Was This Post Helpful? 1
  • +
  • -

#5 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 #2

Posted 18 January 2011 - 07:14 AM

What might be interesting is doing string ranges the way Ruby does them: insane. :P

My implementation wasn't much different than yours. Mine was just more low-level. Unfortunately, it's still quite a bit slower than the built in range. I and my friend Alan might conspire to make it faster later today, so before I allow him to molest my code, here is my implementation:

Spoiler

Was This Post Helpful? 0
  • +
  • -

#6 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 02:56 AM

Thought I'd give this a try, seeing as I'm just starting to learn functional programming, and it's always fun to test your new skills. Here's what I came up with in Haskell.

For integers alone, I defined it like this:
Spoiler


In order to include characters, too, I used the succ and pred functions - I know, it's a boring way to do it, but I'm new to this - I only started learning Haskell four days ago ;) Give me some good advice, then I'll give it another go.

Spoiler


Tested it in ghci, and it seems to work:

ghci> range' 1 10
[1,2,3,4,5,6,7,8,9,10]
ghci> range' 'a' 'q'
"abcdefghijq"
ghci> range' 17 8
[17,16,15,14,13,12,11,10,9,8]
ghci> range' 'F' 'E'
"FE"


Was This Post Helpful? 0
  • +
  • -

#7 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 #2

Posted 20 January 2011 - 09:10 AM

That is actually parametric polymorphism. You can't easily extend it for other types, and it's all defined in the same function. The challenge calls for an ad-hoc polymorphic solution that would have one definition of the range' function for each Rangeable type.

Not to discourage you or anything. Once you get to typeclasses in your Haskell adventure, how to do this challenge should become clear to you.

This post has been edited by Raynes: 20 January 2011 - 02:57 PM

Was This Post Helpful? 1
  • +
  • -

#8 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 09:28 AM

Hmm.. Guess I'm not all that surprised.. Thanks, anyways, I'll be doing some more reading on it :)

This post has been edited by Raynes: 20 January 2011 - 02:59 PM

Was This Post Helpful? 0
  • +
  • -

#9 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 09:47 AM

Oh, and by the way, you can't discourage me just like that - I'm here to learn, and so you won't get rid of me that easily :P
Was This Post Helpful? 0
  • +
  • -

#10 LaFayette  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 43
  • View blog
  • Posts: 326
  • Joined: 24-November 08

Re: Functional Challenge #2

Posted 20 January 2011 - 11:57 AM

Quote

A polymorphic solution would have one definition of the range' function for each Rangeable type.


There are actually several kinds of "polymorphisms".

What I personally think of first when just hearing "polymorphism" is whats called
parametric polymorphism. In short this is a feature that lets us write a function with a generic typing (instead of a specific) so that it can handle values of different types in a uniform way. An example of how what this looks like in Haskell is

append :: [a] -> [a] -> [a]
append xs ys = xs ++ ys



What we are asked to do in the challenge is usually called Ad-hoc polymorphism in the literature and is a feature to allows us to have a function that can behave differently depending on the types of the values of it's arguments (think of a piecewise function in mathematics). Another way to think of is that it allows several functions to have the same name as long as their input parameters differ. An example of ad-hoc polymorphism in the OO world is method overloading.


:)

This post has been edited by LaFayette: 20 January 2011 - 12:01 PM

Was This Post Helpful? 1
  • +
  • -

#11 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 12:55 PM

Wauw, thanks, LaFayette! I mean, that was really, really helpful to little me who hadn't really heard of this until a few days ago. So what I made was actually just a range function with parametric polymorphism, right? So what I'd want is different functions for each type, that will treat them differently, and then depending on what type you put in, the program has to know what function to call. Am I understanding it right?

This post has been edited by Tayacan: 20 January 2011 - 01:01 PM

Was This Post Helpful? 0
  • +
  • -

#12 LaFayette  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 43
  • View blog
  • Posts: 326
  • Joined: 24-November 08

Re: Functional Challenge #2

Posted 20 January 2011 - 01:36 PM

Yes and yes! :)

To achieve this in Haskell we use (as Raynes has mentioned) type classes. Type classes is a way defining a behavior and saying that a type can only be a member of the class if it has that behavior.

In your range' function your are actually using type classes with out perhaps knowing it - (Ord a, Enum a) means that the type the parameter a represents must be a member of the type classes Ord and Enum. This in turn guarantees that values of that type can be used with the ">" and "<" functions and the "pred" and "succ" functions resp.

">", "<", "pred" and "succ" are therefore (ad-hoc) polymorphic in the sense that they might have different implementations for different members of the two type classes.

Anyway Learnyouahaskell is a good beginners resource on type classes : Link

This post has been edited by LaFayette: 20 January 2011 - 01:48 PM

Was This Post Helpful? 0
  • +
  • -

#13 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 01:41 PM

I know what type classes is, and I'm at chapter 6 of LYAH ;) I just misunderstood the thing with polymorphism. I generally try to avoid using code that I don't know what does, so if I didn't know about type classes, I would either read about them or ignore them until later (I say "until later" because I'm a curious person, who doesn't like to leave knowledge alone. Ignoring something that might be interesting will make me.. frustrated).
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 #2

Posted 20 January 2011 - 02:54 PM

View PostLaFayette, on 20 January 2011 - 06:57 PM, said:

Quote

A polymorphic solution would have one definition of the range' function for each Rangeable type.


There are actually several kinds of "polymorphisms".

What I personally think of first when just hearing "polymorphism" is whats called
parametric polymorphism. In short this is a feature that lets us write a function with a generic typing (instead of a specific) so that it can handle values of different types in a uniform way. An example of how what this looks like in Haskell is

append :: [a] -> [a] -> [a]
append xs ys = xs ++ ys



What we are asked to do in the challenge is usually called Ad-hoc polymorphism in the literature and is a feature to allows us to have a function that can behave differently depending on the types of the values of it's arguments (think of a piecewise function in mathematics). Another way to think of is that it allows several functions to have the same name as long as their input parameters differ. An example of ad-hoc polymorphism in the OO world is method overloading.


:)


Indeed. I was being a little unspecific in my wording. Thanks for pointing that out.

I edited my original post to reflect this, so as to not confuse other participants.

This post has been edited by Raynes: 20 January 2011 - 02:57 PM

Was This Post Helpful? 0
  • +
  • -

#15 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Functional Challenge #2

Posted 20 January 2011 - 03:27 PM

Hmm... I'll probably not be here at all in the weekend... But I'll be working on the subject of polymorphism, and thank you for your help, both of you :) Hoping to figure something out before the challenge ends :D
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2