Coursera Functional Programming Principles in Scala

[Toby Corkindale]

Hi,
I've been following the Coursera.org course by Odersky, Functional
Programming Principles in Scala.
It's been interesting enough so far.. I don't feel like it's
introduced anything I didn't already know so far (week 2) but it's
been giving me a better understanding of some functional concepts.

Actually, I did learn something new, the arrow symbol here: def fn(x: => int)
Which means, substitute the variable into the body, rather than
calculating it and substituting the result, which is useful for cases
where that variable may not end up being evaluated inside the
function.

If you're following it too, I'm curious to know what you are thinking
of the course so far?

cheers,
Toby

--
Turning and turning in the widening gyre
The falcon cannot hear the falconer
Things fall apart; the center cannot hold
Mere anarchy is loosed upon the world

[Toby Corkindale]

On 28 September 2012 10:01, Ishaaq Chandy <ish...@gmail.com> wrote:
> Am doing it too. It's been interesting, though am hoping that something more
> challenging comes up in upcoming weeks.
>
> Did you manage to come up with a tail-recursive implementation of the
> money-change problem?

No, but I was rushing for time on that one. Took me ages to get the
basic algorithm for money changing correct; I went off chasing down
the wrong path for a while, then yesterday I caved and googled around
for the right algo, then it was trivial to write a Scala
implementation.

> I've always though of x:=>Int as syntax sugar for the anonymous function:
> x:()=>Int (or x:Unit=>Int) - passing in a function as a parameter has
> similar call-by-name repercussions.

Agreed, but it does result in neater looking code.

>> --
>> You received this message because you are subscribed to the Google Groups
>> "Melbourne Scala User Group" group.
>> To post to this group, send an email to scala...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> scala-melb+...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/scala-melb?hl=en-GB.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Melbourne Scala User Group" group.
> To post to this group, send an email to scala...@googlegroups.com.
> To unsubscribe from this group, send email to
> scala-melb+...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/scala-melb?hl=en-GB.

[Travis Dixon]

I'm doing it and finding similar things.  

Mostly stuff I know, well presented and reinforces some good concepts.

Didn't know about the call-by-name feature.

I found the calculate change problem really fun, found a paper on it: https://subjoin.net/misc/m496pres1.nb.pdf and quite liked how the formula at the bottom of page one translates almost 1:1 into a scala program.

[Jem]

I loved the week two work - declaring Set as Int => Boolean and then implementing various set operations using hofs. Super good fun.

[Lachlan O'Dea]

I found the change problem quite challenging. I managed to nut out a pure functional recursive solution, but did not manage to make it tail recursive. I also had to cheat a bit by sorting the list of available coins up front. The grading robot still gave me 10/10 though, so I gave in to laziness and stopped working on it.

Lachlan.

[Ishaaq Chandy]

Am doing it too. It's been interesting, though am hoping that something more challenging comes up in upcoming weeks.

Did you manage to come up with a tail-recursive implementation of the money-change problem?

I've always though of x:=>Int as syntax sugar for the anonymous function: x:()=>Int (or x:Unit=>Int) - passing in a function as a parameter has similar call-by-name repercussions.

Ishaaq

On 28 September 2012 09:17, Toby Corkindale <to...@dryft.net> wrote:

[Ken Scambler]

I feel kinda reassured you guys had as much trouble as I did with that damn money change problem, it took me hours!   It was fun though.

I don't think it had to be tail-recursive did, it?  I managed to eventually get it working purely with no sorting, non-tail recursive. 

The lesson I learnt from it was that the correctness of a recursive algorithm depends entirely on the degenerate case to unravel it all at the right point; the first algorithm I thought of was correct, but because I didn't focus on the degenerate cases up front, it produced rubbish results.  After cycling through a few different algorithms, it all fell into place once I put in the right behaviour for trivial inputs.

[Tony Morris]

I didn't sign up for the course, but I helped a lot of people asking
about the "balanced parentheses?" problem. To me, it is clearly a
problem that is best solved using forallM on the State monad, where the
state value denotes the number of opened left-parentheses. So I went
ahead and solved it that way.

The forallM function is the same as forall, except there is an
"environment" on each type in return position. Here is regular forall:

def forall[A](x: List[A], p: A => Boolean): Boolean

Here is forallM:

def forallM[M[_], A](x: List[A], p: A => M[Boolean]): M[Boolean]

We can denote "the number of opened parentheses" with a natural number
type, which is just List[Unit]. That is, we cons a Unit value each time
we see ( and we tail each time we see ). This is quite similar to many
solutions that I saw, except they used Int instead of List[Unit]. I like
especially-safe type-safety :)

type Nat = List[Unit]

Now we can define state over this thing like so:

case class State[S, +A](run: S => (A, S)) {
// todo: def map, flatMap, etc.
}

type NatState[+A] = State[Nat, A]

Now the problem is as easy as using forallM on the input data, while
carrying a Nat state to decide on our current position with regard to
opened parentheses. In the event that we find unbalanced, we break out
(forall/forallM do this for us!).

Some protest against this solution in that it is "too complex." However,
it is simply taking existing solutions and abstracting out the common
recursion patterns and code repetition.

Since I don't know the exact rules for the problem, I expect this
solution is not completely within the guidelines. I just chose to
demonstrate how library support and abstraction looks and works in the
context of the problem.

https://gist.github.com/3768490

I don't know the details of the other problems ("coin counting"), but I
am curious.

Tony Morris
http://tmorris.net/

[Ken Scambler]

On 28 September 2012 08:58, Tony Morris <tonym...@gmail.com> wrote:

I didn't sign up for the course, but I helped a lot of people asking
about the "balanced parentheses?" problem. To me, it is clearly a
problem that is best solved using forallM on the State monad, where the
state value denotes the number of opened left-parentheses. So I went
ahead and solved it that way.

Thanks for that Tony.  It's interesting to see how problems can be expressed using these kind of abstractions. 

I understand, though, that a (the?) use-case for State is to avoid the repetition of manually threading lots of parameters through recursive functions without the horror of mutable globals.   In this case there are only two parameters to thread through the function, so does using the State monad really pay for itself here?  Your solution looks less clear than a straight recursive function call to me, although I concede this might just be a symptom of unfamiliarity on my part.

We can denote "the number of opened parentheses" with a natural number
type, which is just List[Unit]. That is, we cons a Unit value each time
we see ( and we tail each time we see ). This is quite similar to many
solutions that I saw, except they used Int instead of List[Unit]. I like
especially-safe type-safety :)

type Nat = List[Unit]

...except that knowing what value the number is will take effort proportional to the size of the number, at least for List.  Which is fine if we're just checking for empty/non-empty, but the trivial step of knowing how many excess parentheses there are becomes unacceptably expensive.  So I'm not sure the extra type-safety pays for itself here either.

[Branko Juric]

The money challenge was a real gem.  Took me ages but I was determined to do no googling to nut it out on my own.  It felt so good when I finally got it :) I will remember that one forever.

[Tony Morris]

On 28/09/12 11:20, Ken Scambler wrote:
> ...except that knowing what value the number is will take effort
> proportional to the size of the number, at least for List. Which is
> fine if we're just checking for empty/non-empty, but the trivial step
> of knowing how many excess parentheses there are becomes unacceptably
> expensive. So I'm not sure the extra type-safety pays for itself here
> either.

This is not required to solve the problem. Only cons/tail is required.

[Tony Morris]

On 28/09/12 11:20, Ken Scambler wrote:

> ...except that knowing what value the number is will take effort
> proportional to the size of the number, at least for List. Which is
> fine if we're just checking for empty/non-empty, but the trivial step
> of knowing how many excess parentheses there are becomes unacceptably
> expensive. So I'm not sure the extra type-safety pays for itself here
> either.

On second thought, perhaps I should point out that List[Unit] is (of same form as) a
church-encoded natural number.

What would it mean to "check the size" of such a thing?

http://en.wikipedia.org/wiki/Church_encoding#Computation_with_Church_numerals

As far as poor efficiency goes, compared to a machine integer,
operations such as addition run in time proportional to the first
operand. Multiplication builds on addition and exponentiation on that.

If the only operations you are doing are:
* isEmpty: Nat => Bool
* +1: Nat => Nat
* -1: Nat => Nat (invariant: not compose isEmpty)

...then where is the problem?

[Ken Scambler]

Obviously for the sake of this problem that will work fine, but what I meant was that if I were writing it for any other purpose the Church-Encoding wouldn't recommend itself because of its limitations.
 

[Ben Hutchison]

Ive been doing the course too - from the side of a pool in Noosa Heads :)

Pretty similar experience as everyone else, I found money change
tricky, and map() over a Set. Hoping it gets more advanced in later
weeks.

I don't think the money change _can_ be tail recursive in a simple
way, because it requires backtracking. You need to explore 2 lines of
enquiry (a) more of the same coin, and (b) using a different coin. If
one dries up, you go back and continue the other.

-Ben

[Ishaaq Chandy]

Yup, the coin-change problem was the most fun to work out, once the insight finally dawned it was all blindingly obvious and elegant. Though with large numbers it becomes quite sluggish.

No, I know it didn't have to be tail-recursive, I was just curious if anyone worked out how to make it so. My best guess would be that it would have to rely on some sort of memoisation technique, but then you'd be just replicating having a stack so perhaps you don't gain that much other than the guarantee that you won't blow the stack, you'll just trade that in for memory blowouts (possibly).

Ishaaq

[Tony Morris]

Ha! I will be up that way on the weekend, writing FP in Scala.

[Ishaaq Chandy]

Yeah, that's what I would have said too except that after I implemented it I headed over and read up the relevant section in the SICP book [1] that introduced the problem, where my pleasure at having coming with the exact same solution independently was short-lived when I saw that the section finishes off with an intriguing statement that a tail-recursive implementation is non-obvious and they left it to the reader as a challenge - that's what I've been mulling over in the background the past few days with no good insight.

Ishaaq

[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_idx_728

[Ben Hutchison]

Actually, I have some further thoughts on this course:

One of the exercises in week 2 requires you to generalize Sum and Product methods. 

Then the week 2 problems highlighted the difference in capabilities of Sets defined via a membership test ("intensionally") or via enumerating it's members ("extensionally"). Especially in the problem where you have to define a map() method across a Set.

All this is done without mention of Monoid or Functor. The course teaches the concepts, but then omits the commonly recognised name for the concepts that it introduces. Is this helpful? Is there a risk that student's do the problems, but miss out on a deeper understanding of, and language for, the patterns they encounter? Or is the important learning in the doing, and the names of patterns a distraction?

-Ben

PS can an intensionally-defined Set be a Functor?

[Jem]

Interesting!

On one hand, sharing a common language provides a lot of leverage and lets us communicate on a higher level. On the other hand, if the course mentioned these terms many would groan from fatigue and write it off. Perhaps Martin will retrospectively label these concepts.

[Tony Morris]

Hiding terminology is of limited use. Some beginners protest about this.
They are wrong and will probably stay beginners for a while longer.

On 30/09/12 09:45, Ben Hutchison wrote:
> Actually, I have some further thoughts on this course:
>
> One of the exercises in week 2 requires you to generalize Sum and Product
> methods.
>
> Then the week 2 problems highlighted the difference in capabilities of Sets
> defined via a membership test ("intensionally") or via enumerating it's
> members ("extensionally"). Especially in the problem where you have to
> define a map() method across a Set.
>
> All this is done without mention of Monoid or Functor. The course teaches
> the concepts, but then omits the commonly recognised name for the concepts

> that it introduces. Is this helpful?* *Is there a risk that student's do

[Branko Juric]

From a learning perspective I think it's important to first grasp the
core concepts and then discover the patterns and abstractions through
practice. Much more enlightening that way than to merely have someone
point them out. Those who seek and discover will be so much better
for it when they have that 'aha, so that's what a Monoid is' moment.
Martin's style of teaching I think promotes this style of learning.

Loved week 2 btw.

[Tony Morris]

I agree e.g.
https://github.com/tonymorris/course/blob/master/src/L04/Misty.hs

However, it is of extremely limited use. Almost always it is better to
tell the student what they are really doing.

[Toby Corkindale]

On 30 September 2012 17:23, Tony Morris <tonym...@gmail.com> wrote:
> I agree e.g.
> https://github.com/tonymorris/course/blob/master/src/L04/Misty.hs
> However, it is of extremely limited use. Almost always it is better to
> tell the student what they are really doing.

I'm not convinced, but then, I haven't studied teaching. A couple of
friends are teachers. I could ask them?

[Malcolm Gorman]

Yes, context is very important. Even a cursory mention of the associated concepts
and their pedigree. An example might be teaching logic without mentioning truth
tables.

[Tony Morris]

I am only a teacher to the extent that I have done teaching. I remember believing that hiding terminology from students was a good idea. I was partly influenced by students themselves. Some students still insist. We were all wrong and not just a bit. I must remember to dismiss their demands, for everyone's benefit.

[King Lung Chiu]

Just to say I've been following the course too and it's been
interesting to have to think purely recursively and forego mutable
values.

As a personal exercise, I've also been trying out the assignments
before watching the videos to see how much I already know - both Scala
syntax and data structures / algorithms - so far so good, though not
sure how long this will last :-)


On 2 October 2012 08:57, Dean Budd <dean...@gmail.com> wrote:
> (Un)fortunately I've been reading Structure and Interpretation of Computer
> Programs in parallel with the course (highly recommended!) and saw (and
> analysed) the algorithm before I saw the problem in the course :(
>
> The Scala Course is pretty much a mirror of the book. I find it very
> valuable. My problem is now juggling two new languages in my head.

Could be interesting to try out the exercises in Scala, and use the
book just for the generic concepts.

cheers,

King

>
> On Friday, September 28, 2012 11:38:12 AM UTC+10, Branko Juric wrote:
>>
>> The money challenge was a real gem. Took me ages but I was determined to
>> do no googling to nut it out on my own. It felt so good when I finally got
>> it :) I will remember that one forever.
>>

> --
> You received this message because you are subscribed to the Google Groups
> "Melbourne Scala User Group" group.

> To view this discussion on the web, visit
> https://groups.google.com/d/msg/scala-melb/-/FWovFQP4-kMJ.

[Ben Hutchison]

Speaking of the course, I feel that last week and this week have drifted towards "Object-oriented Programming Principles in Scala".

For example, last week's Rational example demonstrated a textbook OO implementation. You could just use a tuple containing a Numerator and a Denominator field to model a rational, alias it as Rational, and write a bunch of functions that worked over Rationals. That would be simpler, in the sense that you wouldn't need to invent/understand classes or OO at all.

My impressions is that the course is more about teaching Scala than teaching functional programming, which is a slight surprise because I'd been expecting the opposite emphasis. But for a lot of people this could be ideal.

-Ben

[Travis Dixon]

I got the impression that Martin was going with the line that OO is not mutually exclusive with FP

Didn't he use the first lecture to describe FP as being primarily about immutable variables and contrasted with imperative style, which is a sequence of machine instructions that update state?

[Travis Dixon]

it just occurred to me that immutable variable is a total oxymoron, but I think you get what I mean :P

[Ben Hutchison]

Hi Travis,

Yeah, you remind me that there are 2 different spectrums or axes where the word "Functional" is used. They are often mixed up, because it *is* confusing to have one word mean at least two different things

One is the mutable <-> immutable axis (aka imperative<-> declarative) axis, and this is probably the one where Martin uses the word Functional to describe the immutable/declarative direction. Fair enough.

A somewhat orthogonal axis is the Object-oriented <-> uh, "Functional" (maybe "Type Class"?) spectrum. At the OO end, the data is tightly bound to related behavior  and polymoprhic dispatch is implemented by heap pointers to method vtables, associated with the first special "self" parameter to each function.

At the , er "functional" end, data and behavior are kept separate. Polymoprhic dispatch is implemented via type-classes, which use the compile-time type system to invoke the appropriate type-class instance for the data types in context. Obviously, this paradigm requires a static type system to get past Go.

Support for the typeclass model is not "native" to scala, the way OO is. It was kind of engineered post-hoc, as people (a) understood the capabilities of implicits, (b) ported Haskell code over and (c) recognized how powerful it was. 

The big "wins" of the typeclass model vs the OO model are:

- It doesn't require the asymmetry of dispatching purely on the first "self" parameter to the method. This asymmetry looks to me like an artificial implementation-artefact when critically examined, and has lots of negative consequences, eg implementing Object.equals(other) [http://www.artima.com/lejava/articles/equality.html].

- It allows the behavior to vary in different contexts. Look at java.util.Comparable as example of why you need this; you just cannot just weld one ordering onto a piece of data and expect this to suffice for all clients. Hence, java.util.Comparator came into being, which is essentially a type class, except in Java you must do the dispatch manually by hand.

-Ben

[Andrew Conway]

At the risk of getting into a debate about the meaning of words...

When one talks about a "pure" functional language, it means (to me) referential transparency.

So I think of the mutable/immutable axis you were talking about as the functional style, especially in Scala where you have options. To me, OO and type class dispatch are "merely" convenient ways of doing various things in the mutable / immutable styles.

[Ishaaq Chandy]

well, without proper value data types in the JVM if you lived solely on Ben's non-OO orthogonal axis you'd be relegated to resorting to use tuples for everything - which would feel clunky IMO. I guess you could still declare classes as purely data structures and not give them any methods at all - I guess you throw away traits then as well?

Ishaaq

--
You received this message because you are subscribed to the Google Groups "Melbourne Scala User Group" group.

To view this discussion on the web, visit https://groups.google.com/d/msg/scala-melb/-/Cgx-9Edv8uAJ.

[Tony Morris]

Immutable variables are common. Many people, especially logicians, use the term variable to mean "free variable." It has been argued that using the term variable to imply an updating register should be discouraged. http://existentialtype.wordpress.com/2012/02/01/words-matter/

I have no idea what OO is (and as an aside, I argue, nobody does), but imperative programming is not in conflict with functional programming. Indeed, Haskell is a purely functional language that does imperative programming extremely well. http://apocalisp.wordpress.com/2011/05/30/imperative-vs-functional-programming/

-- 
Tony Morris
http://tmorris.net/

[Ben Hutchison]

On Thu, Oct 11, 2012 at 1:14 PM, Ishaaq Chandy <ish...@gmail.com> wrote:

well, without proper value data types in the JVM if you lived solely on Ben's non-OO orthogonal axis you'd be relegated to resorting to use tuples for everything - which would feel clunky IMO. I guess you could still declare classes as purely data structures and not give them any methods at all

I think you answered your own concern here :)  - yes, use case classes without methods for data, which are relatives of tuple in that they share a common superclass Product.

But to put it another way: ignoring inheritance, any class def can be mechanically transformed into 2 classes: one pure data, one pure behaviour that operates over the data class, with any significant performance impacts.

 

- I guess you throw away traits then as well?

I don't think type-class style amount to a deprecation of traits. They can still be used to compose either the behaviour classes ("modules") or less commonly the data classes. Unless it's changed radically in 7, type-class library Scalaz uses traits extensively.

Finally, I don't think the typeclass style can address all the use-cases for OO-style dispatch, and hence some kind of OO-like mechanism will always be needed. In Haskell, a similar effect is achieved with Existential Types, which are the underpinnings for OO.

For example: Imagine I have a TrafficLight type with Red and Green subtypes, and I want to dispatch to different methods per color, light.speedOfACarAt perhaps. If I throw a heterogeneous collection of light colors together in a List[TrafficLight], I've lost the specific type information I'll need to dispatch typeclass-style over the elements.

You can do this, trivially, using OO. But you can also do this by pairing Existential Types + Typeclasses. I'll try to express the idea in english, since my Scala existential syntax is too rusty: a List of pairs, each containing a value of some hidden (existential) type, paired with a CanFindSpeedOf instance for that same hidden type.

I asked Simon Peyton-Jones about this topic at YOW last year. His reply was that this encoding was essentially objects, but that "you only pay for objects when you need them", rather than being on-by-default. Makes sense to me...

-Ben

[Bernie Pope]

On 12/10/2012, at 1:00 AM, Ben Hutchison wrote:

> I asked Simon Peyton-Jones about this topic at YOW last year. His reply was that this encoding was essentially objects, but that "you only pay for objects when you need them", rather than being on-by-default. Makes sense to me...

This relates to my biggest complaint about OOP is that it conflates too many semantic features (each potentially useful in their own right) into one conglomeration.

Cheers,
Bernie.

[Tony Morris]

On 12/10/12 00:00, Ben Hutchison wrote:
> Unless it's changed radically in 7, type-class
> library Scalaz uses traits extensively.

It still uses traits heavily. To some extent, you don't have to.

case class Semigroup[A](op: (A, A) => A)
case class Monoid[A](id: A, Semigroup[A])
case class Reducer[X, M](unit: X => M, m: Semigroup[M])
...

You run into problems though, in the absence of rank-2:

case class Functor[F[_]](fmap: [A, B](A => B) => F[A] => F[B]) // No.