# Partiality*

Controversial? Perhaps; Opinionated? Certainly.

##### `f :: Int→Int→Int`, f is a function that takes two `Int`s and returns an `Int`, that’s the short story.
Reading type signatures is the first step to understanding what a function does or how a complex program is composed together. It took me some time to get my head around them and I have seen people struggle with them, especially developers coming from dynamic languages. Even for developers from strongly typed languages like Java they are alien. The text makes them more accessible. My recommendation would be to plough through it without accessing the references in footnotes and then re-read it more slowly with references. If something is still unclear or could be improved - do reach out (@ppurang).

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

```
```

[^polish]: [Polish notation](http://en.wikipedia.org/wiki/Polish_notation) should be very familiar to lispers “(add 1 2 )”

```
```

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

```
```
or

```
```

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’) 3 = 4      // we can apply add' repeatedly to always mimic +1
```

So we can re-define

```
```
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
```

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
```
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
```

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
```

```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
```

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
```

```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.

```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
```

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]
```

```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

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)