Book Chat: Learn You a Haskell for Great Good

Haskell was the white whale of functional programming in my mind, something that is the definitive form of functional programming but with such a steep learning curve that it put off all but the most determined students. I had been recommended Learn You a Haskell for Great Good a while ago but kept putting it off because of the intimidating nature of the material. I eventually had a big block of time where I was going to be home and didn’t have many responsibilities so I figured this would be a great opportunity to take a crack at it.

I sat down with it with an expectation that it would be mentally taxing like Functional Programming in Scala was, however having put in the work already reading that and Scala with Cats I was way ahead of the curve. While the Haskell syntax isn’t exactly friendly to beginners I understood most of the concepts; type classes, monads, monoids, comprehensions, recursion, higher order functions, etc. My overall expectation of the difficulty of the language was unfounded. Conceptually it works cleanly, however, coming from a C style language background the syntax is off putting. Added to the basic syntax issues most of the operators being used do give it an aura of inscrutability, especially being difficult to search as they are. I did find this PDF that named most of them which helped me look for additional resources about some of them.

The book explained some of the oddities around some of the stranger pieces of Haskell I had seen before. Specifically the monad type class not also being applicatives, it’s a historical quirk that monads were introduced first and they didn’t want to break backwards compatibility. The other fact that I had not fully appreciated Haskell dates from 1990 which excuses a lot of the decisions about things like function names with letters elided for brevity.

The other differentiating fact about the book is that it tries to bring some humor, rather than being a strictly dry treatment of the material. The humor made me feel a stronger connection with the author and material. A stupid pun as a section header worked for me and provided a little bit of mental break that helped me keep my overall focus while reading it.

Advertisements

Property Based Testing

When I moved into Scala programming I hoped to find out more about the world of functional programming first hand. The style of Scala everyone uses at work is more functional than anything else I had worked with before, but it wasn’t all the way towards functional since it uses exceptions and an object oriented architecture. I had been expecting more monads and such, however there was an idea from functional programming I did get an exposure to for the first time: property based testing.

Property based testing is a style of writing unit tests where you define rules that always hold for the function being tested. It pairs well with functional programming since the immutable nature of data in functional programming makes writing the rules significantly easier. It is a simple concept but there is a lot of nuance around constructing the data to be used and the rules. The example rules in this post use the ∀ symbol which means ‘for all.’

The rules are interesting since you effectively need to be able to describe a set of rules that covers a function’s behavior and define the output in terms of some other logic. Consider this set of rules for doing string concatenation:

∀ strings A and B: (A+B).startsWith(A)

∀ strings A and B: (A+B).endsWith(B)

∀ strings A and B: (A+B).length == A.length + B.length

This set of rules assumes you have these three other working functions. Then when you go to define the rules for those function you can’t assume that + works. So you end up with the next set of rules for startsWith.

∀ strings A: for(int i=0; i< A.length; i++)

 A.startsWith(A.dropRight(i))

∀ strings A, characters B: for(int i=0; i< A.length; i++)

 Not A.startsWith(A.dropRight(i) + B)

 

This then leads you to the rules for dropRight

∀ strings A, int B such that B < A.length: A.dropRight(B).length + B = A.length

∀ strings A, int B such that B < A.length: C = A.dropRight(B)

      for(int i=0; i< C.length; i++)

A[i] == C[i]

This eventually gets you back to a closed set of rules, however you effectively rewrote startsWith in the rules for dropRight. You can reorganize the rules but for most non-trivial systems you end up with asort of looping logic in the rules defining how everything works. You can break the loop like the above example where you essentially reimplement a small portion of logic in the tests, you can set up some traditional example based unit tests to cover the area where the property based tests have looped back, or you can define multiple sets of rules for the same function to increase your confidence in the solution. For the last option, in this example, we would define an additional rule for +.

∀ strings A and B: (A+B).splitAt(A.length) == (A, B)

This rule tackles the same concept from a different direction. It adds an additional layer of confidence that the system is working as intended.

The nuance in creating the data comes from the distribution of data among a data type. Generating random integers is pretty good, but some integers are more likely than others to generate interesting data. Numbers like min, max -1, 0 and 1 are all more likely to trigger a case than whatever numbers you pick at random. Similarly for strings the empty string and odd symbols are more likely to produce interesting cases. Most property based testing frameworks allow you to define interesting cases for your own more complex data types.

I’ve been doing property based testing using the ScalaCheck library which is derived from the Haskell QuickCheck. There are QuickCheck derivative testing frameworks available for most major programming languages. If this sort of logic based testing appeals to your sensibilities give it a try and see if you can craft properties to augment or even replace your existing test suites.

Book Chat: Scala With Cats

Scala with Cats is a free ebook put together to help introduce the Cats library and it’s programming style to developers. It is targeted to Scala developers with about a year of experience with the language, but if you were using the language in a very Java-like way you may not be prepared for this book. That caveat aside, it brings an accessible introduction to the library and it’s style of programming.

I can’t go back and have read this before having read Functional Programming in Scala but it seems like either order would work fine. They both talk about the same basic concepts around purely functional programming. They come at it from two different perspectives; Scala with Cats is about how the category theory-inspired structures in the library can be used to solve problems, whereas Functional Programming in Scala is leading you towards those same category theory-inspired structures but getting you to find the patterns yourself.

I really appreciated the last set of exercises in Scala with Cats where it had you implement this concept. It starts out out as a fully concrete class then converting it into more and more generic structures. First, by adding some type classes to become generic to the specific types. Then, by abstracting over the intermediate data structure and converted the structure to its own type class. Finally, by abstracting over the data structure even further by replacing it with another type class.

I think this style of programming has some definitive pros. The idea behind the vocabulary is good, even if the terms chosen obscure some of the intent. The extensive usage of type classes adds an additional layer of polymorphism that lets a library author abstract over portions of the implementation to make it future-proof. The Scala implementation of type classes makes this feel awkward at points since the imports around implicit instances are less obvious around what is happening. I feel like I need to spend some time with a real application written in this style to try to see what the negatives are to working with it. I can see the issues with learning to work in this style, but I’m uncertain about what the negatives are once you’ve gotten used to this style.

Type Aliases in Scala

I had an interesting conversation recently with one of the junior engineers on my team about when to use type aliases. Normally when I get asked for advice I’ve thought about the topic or at least have a rule of thumb I use for myself. Here all I could manage to express was that I don’t use type aliases but not for any particular reason. I felt I should do better than that and promised to get some better advice and see what we can do with that.

Having thought it through a little, here’s the guidance I gave. You can use type aliases to do type refinement to constrain an existing type. So, you could constrain that integer to only positive integers. Instead of assuming that some arbitrary integer is positive, or checking it in multiple places you can push that check to the edge of your logic. This gives you better compile time checks that your logic is correct and that error conditions have been handled.

They can also be used to attach a name to a complex type. So instead of having an

Either[List[Error], Validated[BusinessObject]]

being repeated through the codebase you can name it something more constructive to the case. This also allows hiding some of the complexities of a given type. So if, for example, you had a function that returns multiply nested functions itself like

String => (Int, Boolean) => Foo[T] => Boolean

it can wrap all that up into a meaningful name.

None of this is really a good rule for a beginner but it feels like it wraps up the two major use cases that I was able to find. I ended up going back to the engineer that prompted the question, with “use type aliases when it makes things clearer and is used consistently.” Neither of us were really happy with that idea. There are clearly more use cases that make sense but we weren’t able to articulate them. We’re both going to try it in some code and come back around to the discussion later and see where that gets us.

Scala Varargs and Partial Functions

I ran into a piece of code recently that looked like

foo(bar,
   {case item:AType => …}
   {case item:AnotherType => …}
{case item:YetAnotherType => …}
// 10 more cases removed for simplicity
)

I was immediately intrigued because that was a very odd construction and I was confused why someone would write a function accepting this many different partial functions and what they were up to. I went to look at the signature and found the below.

def foo(bar: ADTRoot, conditions: PartialFunction[ADTRoot, Map[String, Any]]*):  Map[String, Any]

It was using the partial functions to pick items from the algebraic data type (ADT) and merge them into the map. More interestingly it used the the ability of the partial function to identify if it can operate on the type that bar happened to be. Overall it was interesting combination of language features to create a unique solution.

Part of is that the ADT was missing some abstractions that should have been there to make this sort of work easier, but even then we would have had three cases not a dozen. I’m not sure if this pattern is a generalizable solution or even desirable if it is, but it got me thinking about creative ways to combine language features provided by Scala.

Book Chat: Functional Programming in Scala

I had been meaning to get a copy of this for a while, then I saw one of the authors, Rúnar Bjarnason, at NEScala 2017 giving a talk on adjunctions. Before seeing this talk I had been trying to wrap my head around a lot of the Category Theory underpinning functional programming, and I thought I had been making progress. Seeing the talk made me recognize two facts. First, there was a long way for me togo. Second, there were a lot of other people who also only sort of got it and were all there working at understanding the material. At the associated unconference he gave a second talk which was much more accessible than the linked one. Sadly there is no recording, but I started to really feel like I got it. Talking with some of the other attendees at the conference they all talked about Functional Programming in Scala in an awe inspiring tone about how it helped them really get functional programming, and the associated category theory.

The book is accessible to someone with minimal background in this, so I came in a somewhat overqualified for the first part but settled in nicely for the remaining three parts. It’s not a textbook, but it does come with a variety of exercises and an associated repo with stubs for the questions and answers to the exercises. There is also a companion pdf with chapter notes and hints about how to approach some of the exercises that can help you get moving in the right direction if stuck.

Doing all of the exercises while reading the book is time consuming. Sometimes I would go read about a half a page and do the associated exercises and spend more than an hour at it. The entire exercise was mentally stimulating regardless of the time I committed to the exercise, but it was draining. Some of the exercises were even converted to have a web-based format that is more like unit testing at Scala Exercises.

I made sure I finished the book before going back to NEScala this year. Rúnar was there again, and gave more or less the same category theory talk as the year before, but this time around I got most of what was going on in the first half of the talk. In fact, I was so pleased with myself, that I missed a key point in the middle when I realized how much of the talk I was successfully following. I ended up talking with one of the organizers who indicated he encouraged Runar to give this same talk every year since it is so helpful to get everyone an understanding of the theoretical underpinnings of why all this works.

This book finally got me to understand the underlying ideas of how this works as I built the infrastructure for principled functional programming. It leaned into the complexity and worked through it whereas other books (like Functional Programming in Java) tried to avoid the complexity and focus on the what not the why. This was the single best thing I did to learn this information.

NEScala 2018

I attended NEScala 2018 recently for the second time and wanted to discuss the experiences I had there. It’s three loosely affiliated conferences across three different days. The first day was an unconference, the second was NEScala proper, and the third day was a Typelevel summit. I saw a bunch of great talks and met other practitioners who all brought a different perspective to the same sorts of problems I work with every day, as well as some people who have radically different problems.

There were a pair of talks from presenters at Twitter on how they deal with their monorepo using Scalafix and Pants. These were interesting solutions to the problems of the monorepo. During the transition to the microservices at my current job the code base has shattered into hundreds of repositories, which comes with problems, and you sometimes look and wonder if doing this another way would solve those problems. This was a clear reminder that there are problems on the other side that are just as difficult – just different.

The sections on Http4s(talk) and sttp were especially interesting to see the way they tackled HTTP servers and clients as purely functional structures. HTTP was in my mind difficult to describe purely functionally because it is all about referentially untransparent actions. Sttp was especially interesting because we had built a similar abstraction at work in the last year and seeing how others made different tradeoffs was interesting.

The big takeaway for me was that functional programming purity is a pragmatic thing. Functional programming is a tool to tackle complexity in software, but it’s not the only tool available to do that. There are ways to use local effects to wrap small bits of imperative code, but outside of the function where the imperative code lives, none of the callers can tell. You have a thin imperative wrapper on the outside and possibly little imperative nuggets on the inside that resolve performance issues and occasionally improve algorithmic readability, but the whole program retains the composability and readability of an immutable program.

Functional Programming Katas

Based upon my success with the F# koans I went looking for some more covering the functional side of Scala programming. I’ve found a couple so far, which I’ve completed with varying levels of success.

First was the Learn FP repo is a github repo to checkout and has some code to fill in to make some tests pass. The exercise asks you to provide the implementations of various type classes for different types. There were some links to other articles about the topics but otherwise it was just code. The first part of this was fairly straightforward; I had some trouble with State and Writer but otherwise persevered until I hit the wall at Free. I ended up breaking down and looking up the completed solutions provided in a different branch to find that IntelliJ indicates that the correct solution doesn’t compile (Turns out the IntelliJ Scala plugin has an entire scala compiler in it, and it’s rough around the edges). That frustrated me for a while but I eventually managed to power through, and thankfully the rest of the exercises didn’t suffer from the same problem.

Next was the Cats tutorial. I had done some of the other exercises here when first learning Scala and that had been pretty helpful. This has a neat interactive website to run the code you fill in, but it makes it harder to experiment more with the code. This seemed like a reasonable place to start to cover a lot of the major type classes in Cats. It has you look at sample code and fill in what it would evaluate to. It was good but I had two issues with it. First, there are multiple blanks to fill in some of the sections and it evaluates all of them as a group and doesn’t provide any feedback helping you know which one you got wrong. Second, it’s a lot of looking at other code and describing what it does, no writing of code in this style yourself. Overall it helped me feel more comfortable with some of the terminology, but didn’t produce that “ah ha” moment I was looking for regarding the bigger picture.

Then I went to the Functional Structures Refactoring Kata, which is an application to be refactored into a more functional style with samples in multiple languages.The authors provide a ‘solution’ repo with refactored code to compare to. The issue I had with this exercise is that other than going to look at the solution there isn’t a real way to tell when you’re done.  Even then, some of the ways they factored their solution are opinion based. While seeing that opinion is interesting they don’t really explain the why of their decisions.

The last tutorial I tried was the Functional Programming in Scala exercises. It’s from the same people as the Cats tutorial above and is based on the exercises in the book Functional Programming in Scala. I managed to get about halfway through it without having read the book. While there is some prose in between exercises, it doesn’t adequately explain all of the concepts. While I’m reading the book I will come back to this and do the rest of the exercises.

Overall I would strongly recommend the Learn FP repo, and recommend the Cats tutorial. I would pass on Functional Structures Refactoring Kata. I’ll hold judgment on Functional Programming in Scala until I can try it with  the book. While these were largely good starts, I still haven’t had that conceptual breakthrough I’m looking for on how to use all of these pieces in practice.

Type Classes

I have been trying to understand type classes for a while and having a hard time figuring out exactly what they mean or how to effectively use them. The idea that they are a means to extend the behavior of a class in a consistent matter makes sense in an abstract way. But I’m not sure how exactly they accomplish that goal, or what a type class is or isn’t. A coworker had offhandedly referred to a type class as “a trait with a type parameter,” but it feels like there has to be more to it than that. This post is a sort of journal of my efforts to figure out exactly what a type class is.

The wikipedia page wasn’t that helpful to me since it defines type classes in terms of other unknown terms. It had one useful tidbit of information from my perspective: in Scala, type classes are implemented with implicits. Following some more links I ended up at the Cats documentation, which has a bunch of example type classes and code using them that I found useful. This got me thinking about whether I had seen anything that had a signature that looked like it might be using a type class. I remembered the sum method on List, which had stuck in my mind because it was unclear as to how it knew how to sum the items and what types it would be legal to sum.

This definitely looks like a type class given our definition so far. We have an implicit argument that is a trait with a type parameter. It is being used to extend numeric types to give them orderings and perform arithmetic operations, but it also signals that the type is numeric. The type class is also being used to constrain what types the sum method is available for, since if the implicit is not available it won’t compile. This constraint also plays nicely with the context bound syntax.

So we’ve got an example and some rules, but that’s not really a definition. I went looking for some more examples in the Cats codebase since that is full of type classes. Each of the individual type classes in Cats definitely follows the pattern of a trait with a type parameter. I think the missing piece for my understanding, lay in what the methods on the type class are. The methods all seem to take at least one argument of the type parameter so that appears to be a reasonable constraint on the functions.

Type classes are different than an implicit class since you can constrain type signatures with it, but they both let you add new functionality to an existing type. The implicit lookup progress imposes some constraints on the implicit class, such as only taking one non-implicit argument, which the type class methods can bypass. You could write an implicit class to expose the type class in a more fluent way like.

 implicit class NumericWrapper[T:Numeric](x: T) {
  def plus(b: T): T = {
    val n = implicitly[Numeric[T]]
    n.plus(x, b)
  }
}

Type classes seem like they would be more useful in a language without multiple inheritance. Since in Scala I can have a type implementing multiple traits that already have implementation associated with them, just mixing in more code seems like an easier way around the extension problems. I found this proposal for adding type classes to C#, which seems very cool and in line with the sorts of powerful abstractions they’ve been trying to add to the language. Seeing a different syntax for using type classes without implicits being involved helped me understand what they really are.

Going back to my initial goal of figuring out what a type class is and how it works, I think I’ve figured out both. It is a generic type that adds functionality to that type but defers the implementation of that functionality. Then you specify something that expects the type class and brings the implementation of the functionality and the data together. In Scala it accomplishes this using type bounds to specify the type class and implicit parameters to pass the type class into the implementation. I’m still not sure when I would want to write my own type class as opposed using other polymorphic concepts, but I’m now confident about using existing type classes and even breaking out some of the Cats-based ones as opposed to just some of the inbuilt ones.

Monads for the Working Programmer

The monad is a backbone of functional programming. However, the mathematical definition of what a monad is highly inaccessible. I want to try and describe a monad for a programmer who is new to functional programming. This isn’t intended to be a precise definition, it is intended to be enough to help understand what the monad is, how to use it, and why it’s a helpful construct.

Consider the monad as a box. The box can be empty and the box doesn’t really care what’s in it. You can go get a box and put something in it. Someone can open up the box, take out what’s in there, work with it, then put their output back in the box. That’s really all there is to it.

Sometimes the box is less tangible than other boxes. For instance, Future in Scala or IO in Haskell don’t have an actual value yet, but the promise of a value later. Think of it like a package in the mail, the box may not be here yet but you can make plans for when it gets to you. You can plan to open the box and combine it with another value you have and put it back in the box. In programming terms it’s a continuation, you take the first box and attach some code to it so that when the value in the box does show up you run the continuation with it.

Sometime the box is a bit bigger than others, like the List monad. The List monad has more than one thing in the box like an egg carton, but they’re all of the same type. You can still open up the box and take out an egg and do something with it, or you can process each of the eggs in turn.

When you want to use a monad it’s as easy as that – your functions all start wrapping their return types in that monad. Their callers then open the box and do their work and return the new value to the box. So instead of pseudo code that looks like


values = [3, 4, 5]

for(int i =0; i<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>< values.length; i++) {

	values[i] = values[i] * 2;

}

 

 

You get pseudo code that looks like


values = [3, 4, 5]

doubled = values.map(value => value * 2)

But what’s the point of this programming style, what does it get you? First, it helps you work with immutable data. In the first example above you are mutating whatever values is. That’s fine in object oriented or procedural programming, but functional programming sacrificed mutable data for thread safe composability. Second, it produces code that is easily composable. If I wanted to subtract one before doubling the values in the above monad example, I could add another map statement entirely, separating the two concerns. In the initial example the two concerns would be mixed into the same control flow. Third, the monad itself can contain a fair bit of logic to enrich the programming experience. The ability to interact with a Future, an Option, a List, or any other monad in the same way simplifies a lot of refactorings. If you want to replace an Option with a List application logic doesn’t need to change much. Hopefully all of this helps demystify the Monad and helps you to write better code.