• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Scala exercises for beginners (in FP)

 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Scala exercises for beginners
I had a lot of fun solving them, particularly trying to use a minimal set of operations (pattern matching, recursion,::, Nil).
Solving them with fold/reduce helped to clarify some details, though
 
Marc Peabody
pie sneak
Sheriff
Posts: 4727
Mac Ruby VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the link - this is great fun, Gabriel!

Here's my first pass. I haven't learned folding of lists yet, so that's my next priority and then I'll give another crack at it. Any helpful opinions welcome!


results:
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The seminal treatise on folds in functional programming is the very readable: A tutorial on the universality and expressiveness of fold.

All the functions in the exercise save the add function can be solved using left and right folds.



I find the symbollic /: and :\ difficult to mentally translate, but I guess if I used them more I'd get used to them.
[ July 21, 2008: Message edited by: Garrett Rowe ]
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oh, and by the rules of the exercise, ::: is a prohibited function.
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Garrett Rowe:
Oh, and by the rules of the exercise, ::: is a prohibited function.

Yes, ':::' is prohibited, but is the list concatenation operator. In Marc's case, it can be easily replaced by the '::' ("cons") operator.
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Marc Peabody:


I did the list recursion using Nil and '::'

Nil is the empty list and the operator '::' appends an element to the beginning.
I found quite interesting the fact the pattern matching can match and split the pattern 'element::list'
Of course, with a fold is a lot easier:

def map[A, B](x: List[A], f: A => B): List[B] =
x.foldRight(Nil: List[B])((x,xs)=>f(x)::xs)


My fold/reduce 'cheat sheet' is something like:

For the list (a,b,c,d) ,

reduceLeft(f) => f(f(f(a,b),c),d)

foldLeft(Z)(f) => f(f(f(f(Z,a),b),c),d)

("starts from the left")


reduceRight(f) => f(a,f(b,f(c,d)))

foldRight(Z)(f) => f(a,f(b,f(c,f(d,Z))))

("starts from the right")

[ July 21, 2008: Message edited by: Gabriel Claramunt ]
[ July 21, 2008: Message edited by: Gabriel Claramunt ]
 
Marc Peabody
pie sneak
Sheriff
Posts: 4727
Mac Ruby VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Gabriel Claramunt:

Yes, ':::' is prohibited, but is the list concatenation operator. In Marc's case, it can be easily replaced by the '::' ("cons") operator.

Totally missed that ::: was in the illegal list. Oops!

I suppose if I were to take it out of my append() then I could just use my append method everywhere else...

Fold is starting to make sense a bit (basically seems to be a tiny DSL for recursion) but I get the feeling that most programmers would rather put their brain through a meat grinder than try to wrap their head around this.
[ July 21, 2008: Message edited by: Marc Peabody ]
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here are my solutions with recursion and with fold/reduce
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic