# Scala exercises for beginners (in FP)

Gabriel Claramunt
Ranch Hand
Posts: 375
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
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
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
Oh, and by the rules of the exercise, ::: is a prohibited function.

Gabriel Claramunt
Ranch Hand
Posts: 375
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
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
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
Here are my solutions with recursion and with fold/reduce

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?