DrBoolean's Mostly Adequate Guide to Functional Programming

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

DrBoolean's Mostly Adequate Guide to Functional Programming

Postby Xanthir » Sat Jul 25, 2015 4:37 pm UTC

I stumbled across a *wonderful* newb-friendly introduction to functional programming, using JS as the base language, recently. Here's the (partially-completed) book, and here's the GitHub repo.

It finally teaches functional programming in the way I, personally, taught myself, and reading it strengthened my intuitions in a great way (that is, I still learned something!). He's got a great explanatory style, provides tons of examples, has useful exercises at the end of the later chapters, and is all around a good tech writer.

Currently the book covers up through Functors and Monads, hitting pureness, currying, HM types, and composition along the way. Next chapter should be on Applicatives, which I'm excited about, as I haven't developed great intuitions for them yet. I hope he does Traversable soon, too.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Dr. Willpower » Fri Jul 31, 2015 1:01 pm UTC

Hey thanks for this. I've been looking for a good place to learn functional programming for a while now.
Image
Hat me, bro

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Fri Jul 31, 2015 3:31 pm UTC

And based on my upgraded intuition from this guide, I went back and reread Typeclassopedia for Applicative and Traversable, and understood *them* too. Wooooo!

As a result, I realized yesterday that Promise.all() is just a fancy name for sequenceA() (the function from the Traversable typeclass) applied to an Array<Promise> - it swaps you to a Promise<Array>. (Assuming the reasonable default Applicative implementation for Promise. I think that the success behavior of Promise.all(), at least, is required for Promise to satisfy the Applicative laws; you could use different failure behavior, as the laws don't care about failure, but the Promise.all() behavior of immediately returning the first rejection is the easiest and most reasonable, and so I think the best candidate for "default" behavior.)

I also finally understood both the free monoid and the free monad, and the concept of "free" structures in general, which previously slightly eluded me.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ubik
Posts: 1016
Joined: Thu Oct 18, 2007 3:43 pm UTC

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Ubik » Sat Aug 29, 2015 2:24 pm UTC

I slowly went through the book in the past several weeks, and did the exercises too. In the last set of exercises (currently the monad chapter) two things happened:

1) I think I got bit by the simplicity of the example implementation of join() in the exercise two.

Here's the exercise for reference
Spoiler:

Code: Select all

// Exercise 2
// ==========
// Use getFile to get the filename, remove the directory so it's just the file, then purely log it.

var getFile = function() {
  return new IO(function(){ return __filename; });
}

var pureLog = function(x) {
  return new IO(function(){
    console.log(x);
    return 'logged ' + x; // for testing w/o mocks
  });
}

var ex2 = undefined;
I mostly solved it by trying things around, and ended up with this:

Code: Select all

var ex2 = _.compose(pureLog, chain(_.compose(_.last, _.split('/'))), getFile);
The official answer is this:

Code: Select all

var ex2 = _.compose(chain(_.compose(pureLog, _.last, _.split('/'))), getFile);
I only realized I'm having a problem once I saw it. As you can see, I have pureLog outside the chain(), which according to my understanding shouldn't work. If the join function only reduces two nested monads into one, and if I'm understanding it right, it shouldn't return the bare contents when there's only one "monad layer" around the content. Still, my code relied on the unconditionality of the unwrapping. Maybe I should open an issue and suggest adding some parameter checking.


2) The final exercise. Again I just tried stuff around - pretty obvious sign I still don't really grasp what I'm doing - and ended up with a lot simpler answer compared to the official one. Here's the exercise:
Spoiler:

Code: Select all

// Exercise 4
// ==========
// Use validateEmail, addToMailingList and emailBlast to implmeent ex4's type signature.
// It should safely add a new subscriber to the list, then email everyone with this happy news.

//  addToMailingList :: Email -> IO [Email]
var addToMailingList = (function(list){
  return function(email) {
    return new IO(function(){
      list.push(email);
      return list;
    });
  }
})([]);

//       emailBlast :: [Email] -> IO String
function emailBlast(list) {
  return new IO(function(){
    return 'emailed: ' + list.join(','); // for testing w/o mocks
  });
}

//  validateEmail :: Email -> Either String Email
var validateEmail = function(x){
  return x.match(/\S+@\S+\.\S+/) ? (new Right(x)) : (new Left('invalid email'));
}

var ex4 = undefined;
This is what I came up with, seemed strangely obvious looking when I got it to work. So far the later exercises have actually been more complex.

Code: Select all

var ex4 = _.compose(_.map(emailBlast), _.map(addToMailingList), validateEmail);
The official one has three levels of nesting within the compose():

Code: Select all

var ex4 = _.compose(_.map(_.compose(chain(emailBlast), addToMailingList)), validateEmail);
Before trying to do it the simple way, I too was attempting something slightly along those lines but didn't find the right combination. Looking at the code it sort of makes sense to compose the IO functions together and then the chain call makes sense too. What bothers me is that I'm not seeing what's wrong with using just map like I ended up doing, and am doubting I'm again inadvertently abusing the lack of strictness of the supporting code.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Sun Aug 30, 2015 7:12 am UTC

Your answer for 4 is definitely wrong. emailBlast() expects an [Email], but you have an Either String (IO [Email]). That's two levels of wrappers between the value you have and the one you want, and you're only map()ing once, so there's no way it works correctly. Even if you'd called it right somehow, you need a chain() rather than a map(), because you're inside of an IO and want to return another IO; you don't want to stack those. So to do it right, you first need to map() emailBlast (to get it through the Either wrapper) and then chain() it (to get it through the IO wrapper and merge the results). (And by "first" and "then" I mean "outer" and "inner", of course - map(chain(emailBlast)).)

The official answer can be done in a slightly different way, depending on how much mapping you want to do:

Code: Select all

compose( map(chain(emailBlast)), map(addToMailingList), validateEmail )


This might be more obvious to you. The official answer just lifts the map from the first two functions out, because compose(map(a), map(b)) is equivalent to map(compose(a,b)), but the latter is more efficient due to the single map().
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ubik
Posts: 1016
Joined: Thu Oct 18, 2007 3:43 pm UTC

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Ubik » Sun Aug 30, 2015 10:36 am UTC

The strange thing is that while I agree it's wrong, the code works. When I did the exercises, I ran the tests repeatedly (lots of "mocha monad_exercises_spec.js" calls) and the wrong solution goes through fine too.

But I think I finally got how it works!

tl;dr: Both IO and [] (=JavaScript list) have a join method, I misused the accidental compatibility.

I augmented the code a bit by adding console.log calls, and added calls to my own advanced inspection function to the composition:
Spoiler:

Code: Select all

//  addToMailingList :: Email -> IO [Email]
var addToMailingList = (function(list){
  return function(email) {
    return new IO(function(){
      console.log("Adding", email, "to following list:", list)
      list.push(email);
      return list;
    });
  }
})([]);

//       emailBlast :: [Email] -> IO String
function emailBlast(list) {
  return new IO(function(){
    console.log("Emailing using following list:", list)
    return 'emailed: ' + list.join(','); // for testing w/o mocks
  });
}

//  validateEmail :: Email -> Either String Email
var validateEmail = function(x){
  console.log("Validating email" + x)
  return x.match(/\S+@\S+\.\S+/) ? (new Right(x)) : (new Left('invalid email'));
}

var huh = _.curry(function(n, x) {
  console.log(n, x.inspect());
  return x;
})

var ex4 = _.compose(huh("3"), _.map(emailBlast), huh("2"), _.map(addToMailingList), huh("1"), validateEmail);
So now I know a lot of what's happening inside when it runs. When running the tests, the following is what gets printed (I've cut out some irrelevant lines relating to the other exercises):

Code: Select all

Validating emailnotanemail
1 Left(invalid email)
2 Left(invalid email)
3 Left(invalid email)
Validating emailsleepy@grandpa.net
1 Right(sleepy@grandpa.net)
2 Right(IO(function (){
      console.log("Adding", email, "to following list:", list)
      list.push(email);
      return list;
    }))
3 Right(IO(function (){
    console.log("Emailing using following list:", list)
    return 'emailed: ' + list.join(','); // for testing w/o mocks
  }))
Emailing using following list: IO(function (){
      console.log("Adding", email, "to following list:", list)
      list.push(email);
      return list;
    })
Adding sleepy@grandpa.net to following list: []
The tests first try how the function works with an invalid email, and there the map() of Left just keeps the error message so it works. When testing with a valid email, the two IO-returning functions don't form an IO(IO(...)) because the map() is called against the Right obtained in the beginning. Instead, the IO returned by addToMailinglist get passed to emailBlast as the list parameter. The trick is that the only thing emailBlast does to the list is to call the join method. The IO that has been passed to it has join too, and it happens to cause the evaluation of the contained function, returning the actual list. The line "return 'emailed: ' + list.join(',');" ends up working properly by accident, because the list stringifies automatically exactly the same way as if join(',') had been called on it. (And the list having only one element makes it even less reliant on that.)

Now I'm thinking what the code needs is some kind of strict type checking decorators...even though it's me who is actually causing the errors.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Mon Aug 31, 2015 5:18 pm UTC

This is why most heavy-functional code is written in static languages with good type support. ^_^
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ubik
Posts: 1016
Joined: Thu Oct 18, 2007 3:43 pm UTC

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Ubik » Mon Aug 31, 2015 5:46 pm UTC

Yep. Though today I was thinking that it shouldn't be terribly complicated to make a function that takes a function and bunch of types as its parameters, and then returns a version that checks the parameter and return types upon evaluation. Well, a very naive version wouldn't be too difficult. Testing that a list contains only strings or that the returned IO returns a string when unsafePerformIO is called - and what if there's even more nested levels? (Though the internal type could maybe be checked by mapping through the contents...)

Anyway, the tenth chapter is out now.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Tue Sep 01, 2015 4:48 pm UTC

Yeah, it's not hard, and it's been done several times - one of my coworkers wrote a library that took a function and a string containing a Haskell-style type declaration, and produced an auto-curried function that did typechecking for you.

I'll see if I can rustle one up for you, so you don't have to do the work yourself. ^_^

Anyway, woo! 10th chapter! Now I can check how good my self-taught Applicative intuition is.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Tue Sep 01, 2015 9:55 pm UTC

Ubik: Now I'm really curious as to how your intuition let you type our your Ex4 program. I find type signatures very intuitive and easy to reason with, and like to think of a lot of higher-order programming as working on type signatures rather than actual functions, so certain things become very obvious to me.

In particular, map() upgrades an A->B function to a Container(A)->Container(B) function. This makes it super-obvious, to me, that map(emailBlast) doesn't work, as it turns it from [Email]->IO(String) into Container([Email])->Container(IO(String)). But the input is Either(IO([Email])), two containers thick, and even if you double-map(), you still end up with it returning Either(IO(IO(String))).

I'm too far into this to know how understanding can go wrong at this point, so I'd really appreciate it if you could explain where your thinking took you. Hopefully, it'll help me explain this stuff to other people in the future.

(I wish I knew the name for the signature (Container(A)->Container(B)), because it's my preferred way to think of these things. map() upgrades an (a->b) to an (M a->M b), chain() upgrades an (a->M b) to an (M a->M b), ap() upgrades an M(a->b) to an (M a->M b), etc.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Ubik
Posts: 1016
Joined: Thu Oct 18, 2007 3:43 pm UTC

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Ubik » Wed Sep 02, 2015 6:24 am UTC

Sadly I can't anymore remember what was my original attempt at solving ex4, but it was different than what I ended up with. It definitely had the general structure of compose(compose(emailBlast, addToMailingList), validateEmail), with some map and chain calls around or inside the inner compose. (Can't remember where but obviously in the wrong places.) Having that inner compose around interestingly gives me the feeling of having been closer to the right solution, even though it's the maps and chains that really matter.

Anyway, while doing the exercise, I just couldn't find the right combination by reasoning, so ended up playing "try all permutations and see what sticks" before looking into the answers section. That's where I ended up trying the version with just two maps.

What I can remember from my reasoning is that because I'm trying to make an Either with an IO in it (in the case of Right variant), I probably should have the IO handling composed together. The map and chain would be used to intentionally wrap into one IO but having an implied join there too to avoid double-wrapping. I can't remember what I thought about having a map or chain outside the inner compose. I may have redone same thing as with the earlier exercise where I mentioned I removed some monad completely instead of properly just joining two nested IOs into one, but on the other hand I might have specifically been looking for not doing that again.

What I admittedly didn't do, was to think more in terms of types or type signatures. I'm not completely lost with them, but still not very comfortable with them either.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: DrBoolean's Mostly Adequate Guide to Functional Programm

Postby Xanthir » Wed Sep 02, 2015 3:23 pm UTC

That's helpful, thanks for the explanation!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests