## Addition as an example {#addition} Let us start with a very simple example that should be clear to a majority, namely addition of integers[^overflow]. In the discussion below we prefer `add` instead of the universally accepted `+` because some languages don’t allow symbols and others already provide a `+`. All code in this section is psuedo-code. In the rest of the text we always indicate the language before the code appears. [^overflow]: We ignore [integer overflow](http://en.wikipedia.org/wiki/Integer_overflow) Addition of two integers is defined as ``` 1 add 2 = 3 ``` Another notation[^polish] for addition is [^polish]: [Polish notation](http://en.wikipedia.org/wiki/Polish_notation) should be very familiar to lispers “(add 1 2 )” ``` add 1 2 = 3 ``` We prefer this notation as this resembles, very closely, how functions are defined in most languages. Now if we take the integers to be represented by the type `Int`[^bounded] then the above definition can be generalized into [^bounded]: Int is bounded in [Haskell](http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Int.html) and [Scala](http://www.scala-lang.org/api/current/index.html#scala.Int). ``` add Int Int = Int ``` or ``` add Int, Int = Int ``` We introduce the `comma` to again resemble declaration of functions in many languages (exceptions includes Haskell). One way of reading the expression above is `add takes two Ints and maps them to an Int`[^add]. Let me add another thing to the notation: [^add]: Domain : ℤ × ℤ→ℤ : Co-domain (here the domain is a [product type] (http://en.wikipedia.org/wiki/Product_type) ) ``` add :: Int, Int = Int ``` This just sets the name apart from the actual type. Functions are typed too so `add` has a type[^fntyp]. Right now the type appears to take two/pair/tuple of `Int`s and returns an `Int`. [^fntyp]: [Function type](http://en.wikipedia.org/wiki/Function_type) Before we continue to the next step; let us see how we can declare `add` in a few languages to get a feel for it. ```scala def add(a: Int, b: Int) : Int // In Scala ``` ```hs add a b -- In Haskell given the implementation the compiler will infer the types ``` ```java int add(int a, int b) // Java ``` We don’t provide the implementations as they aren’t very important for understanding the type signatures. The definitions as they stand in Scala and Java are methods and not functions. We will drop Java from further discussion because (despite lambdas) Java doesn’t have first class support for function literals. In Haskell, the function `add` defined above is curried[^curry], i.e. it can be `partially applied`, and resembles more closely our first attempt at understanding the type signature of addition namely `add :: Int Int = Int`. Any `tupled` version can be converted to a `curried` version of a function and vice versa, we talk about this in detail later. Curried version of a function converts a function with multiple arguments into a chain of function applications with each argument introduced one by one until no more arguments are left and we get the final result. The curried add can be applied in stages [^curry]: [Currying](http://en.wikipedia.org/wiki/Currying) ```psuedo {.lang-pseudocode} (add 1) = add’ //partially apply add to 1 and capture that as add’ (add’) 2 = 3 //apply add’ to 2 to get the final result of 3. add’ is different from add. (add’) 3 = 4 // we can apply add' repeatedly to always mimic +1 ``` So we can re-define ``` add(1, 2) = 3 ``` to ``` add(1)(2) = 3 //with the advantage that we can capture add(1) and apply it again and again ``` Which takes us back to the `add :: Int Int = Int` the form before we introduced the comma. One of the reasons I prefer the curried version is that it makes type signatures simpler. Finally, let us introduce a type signature that resembles them in modern languages. ```hs add :: Int→Int→Int ``` The way I read it: `add` is a function that maps an `Int` to a function that takes another `Int` to return an `Int`. The following makes it even more explicit ```hs add :: Int→(Int→Int) ``` From this definition we calculate 3 with ```hs add 1 = add1 -- gives us a result of type (Int→Int) let us call it add1 add1 2 = 3 -- we drop add' and use add1 as the former isn't a valid syntax in most modern languages ``` The tupled version of the function can be captured as ```hs add: (Int, Int) → Int ``` Would you agree with me that the definitions involving only the arrow/map `→` is simpler than the one which also uses a comma? That comma somehow hides the true structure of a function and might interfere with coming up with candidates valid for function composition. ## Multiplication {#multiplication} Let us define a function in two different languages where we start with the type signatures first and then implement them. We know integer multiplication, like addition, maps two `Int`s into an `Int`. So `mult` can be defined as ```hs mult :: Int→Int→Int // mult’s type signature is the same as add’s. ``` In Scala, one uses `⇒` or `=>`, instead of `→` ```scala type Mult = Int => Int => Int // type alias: gives the entire function type a name val mult : Mult = a => b => a * b // a functional value that follows the type ``` or alternatively as a single line with declaration and implementation ```scala val mult : Int => Int => Int = a => b => a * b // the ‘=’ separates declaration from definition ``` In Haskell, `→`[^haskuni] or `->` ```hs {.linenums} mult :: Int -> Int -> Int -- can be left out as the compiler will infer the types for us but that inference will be different in this case `mult :: Num a => a -> a -> a` mult a b = a * b -- much simpler ``` [^haskuni]: Requires the [unicode syntax extension](http://www.haskell.org/haskellwiki/Unicode-symbols) Usage in Scala ```scala mult(1)(2) val mult1 = mult(1) //partial application, note we have swapped the result unlike what we saw above in psuedo-code mult1(2) //same as mult(1)(2) or 2 the end result ``` Usage in Haskell ```hs mult 1 2 let mult1 = mult 1 mult1 2 ``` Here are some exercises for you to test your present understanding 1. What type would a function that concatenates two strings have?[^con] 2. What type would a factorial of integers have?[^funct] [^con]: String → String → String [^funct]: Int → Int ## Currying {#currying} ### Equivalence {#currying-equiv} **Q.** Are the tupled `((Int, Int) → Int)`[^alttup] and the curried `(Int→Int→Int)` versions equivalent? **A.** Yes, the tupled and the curried versions are equivalent. “Under the Curry–Howard correspondence, the existence of currying and uncurrying is equivalent to the logical theorem (A ∧ B) →C ⇔ A → (B →C), as tuples (product type) corresponds to conjunction in logic, and function type corresponds to implication.”[^curry-howard] [^alttup]: Alternatively, Int x Int → Int [^curry-howard]: [Curry-Howard_correspondence](http://en.wikipedia.org/wiki/Curry-Howard_correspondence) ### Choosing a Form {#currying-choosing-a-form} Choosing a form of definition might depend on the language. In Haskell “...all functions are considered curried”[^haskcurr]. In Scala, you choose one form knowing that the other form (like in Haskell, using `curry` and `uncurry`) is just another call away. [^haskcurr]: http://www.haskell.org/haskellwiki/Currying ```scala val add: (Int, Int) => Int = _ + _ // type (Int, Int) => Int and _ + _ is terser as the equivalent a => b => a + b val addCurried: Int => Int => Int = add.curried // type Int => Int => Int val addUncurried = Function.uncurried(addCurried) //can you guess the type? ``` Does your language of choice provide this flexibility? In Scala, as type inference has its limits, choosing currying can help type inference. Here is the curried version of function whose type we alias to Map, it should also exercises your type reading skills ```scala type Map[A, B] = List[A] => (A => B) => List[B] ``` Can you read this? Or is the following, in Haskell, easier to read? ```hs map :: [a]→(a→b)→[b] -- where [a] is a list of a’s ``` I read them as: `Map` is a function that takes a List of type `A`s and returns a function that takes a function from `A`s to `B`s to return a list of `B`s.[^poly] [^poly]: `A` and `B` are type variables and stand for any one of all possible types. This makes the function polymorphic. [Parametric polymorphism]( http://en.wikipedia.org/wiki/Polymorphism_%28computer_science%29#Parametric_polymorphism) Using the equivalence we can shorten this to: `Map` is a function that takes a List of type `A`s and a function that takes `A`s to `B`s to return a list of `B`s. And here is the implementation ```scala def map[A, B] : Map[A, B] = l => f => l.map(f) //ok we cheat and reuse the map defined on a list map(List(1,2,3))(_ * 2) // res0: List[Int] = List(2, 4, 6) ``` <hr> **Aside**: *Why did we introduce the brackets?* Without the brackets the definition is ```scala type MapWithImpliedBrackets[A, B] = List[A] => (A => (B => List[B])) ``` which can be read as : `MapWithImpliedBrackets` is a function that takes a List of type `A`s and returns a function that takes an `A` to return another function that takes a `B` to return a list of `B`s. Can we even implement such a definition? Can it be equivalent to the Map defined above? <hr> Back to our original query: **How does currying help with type inference in Scala?** To answer this let us declare the uncurried version and try and implement it. ```scala {.lang-scala} type MapUncurried[A,B] = (List[A], A => B) => List[B] //can you read this type? def mapUncurried[A, B] : MapUncurried[A,B] = (l, f) => l.map(f) //the implementation hasn't changed ``` Can you use it like this? ```scala {.lang-scala} mapUncurried(List(1,2,3), _ * 2) mapUncurried(List(1,2,3), x => x * 2) ``` No, you need to use the more verbose ```scala {.lang-scala} mapUncurried(List(1,2,3), (x:Int) => x * 2) // compare that to the curried map(List(1,2,3))(_ * 2) ``` **Note**: This is a limitation of Scala’s compiler and not type definitions. Here is a similar example in Haskell ```hs {.lang-haskell .linenums} mapX :: ([a], a -> b) -> [b] -- map is already taken and we make tuple it explicitly mapX (x : xs, f) = f x : mapX(xs, f) mapX ([ ],f) = [ ] mapX([1,2,3], \x -> x * 2) -- [2,4,6], no type declaration for x needed ``` ## Programming with type signatures {#programming-type-signatures} Let us get ambitious. How would you define a program that takes a path to a file and returns the count of chars in that file? We can do some type driven program design (don't forget to read the type signatures along the way) ```scala {.lang-scala .linenums } //the following is our main type that declares our intention type CountCharsInAFile = String => Int //it is better to divide the program into more manageable parts achieving our end result in stages (somewhat like the principle of currying - applying a function in stages) type PathToFile = String => File //assuming we have imported java.io.File def pathToFile : PathToFile = ??? // we can fill in the implementation later type FileToLines = File => List[String] def fileToLines: FileToLines = ??? type CountCharsInLines = List[String] => List[Int] // we can decompose this further into type CountCharsInALine = String => Int def countCharsInLines: CountCharsInLines = ??? type Total = List[Int] => Int def total: Total = ??? ``` Even before you have implemented the parts you can check if the types line up. ```scala def countCharsInAFile: CountCharsInAFile = (total compose countCharsInLines compose fileToLines compose pathToFile)(_) ``` Go ahead and implement the undefined portions indicated by `???` in the code above and see how things just work[^soln]. [^soln]: [Gist charscounter.scala]( https://gist.github.com/ppurang/4f81d31e38c8673b4882) You’d be correct to point out that we haven’t talked about efficiency or resource and error handling. They were indeed skipped to keep things simple. We just demonstrated how you can think in types and compose in functions to deliver a program. ## Class constraints {#bounded-parametric-poly} In one of the code examples above we mentioned a type signature in haskell `mult :: Num a => a -> a -> a`. What's that `Num a`? In this case `mult` is a polymorphic function whose type variable `a` is constrained by a typeclass `Num`, i.e. only those types that have a `Num` instance are valid parameters for this function. This is an example of _Bounded Parametric Polymorphism_[^bpp]. [^bpp]: [Bounded Parametric Polymorphism](http://en.wikipedia.org/wiki/Parametric_polymorphism#Bounded_parametric_polymorphism)