Monoids in the category of endofunctors

Kaare Nilsen

Definition functional programming?

We construct our programs using only pure functions. In other words, functions that have no side effects. What does this mean exactly? Performing any of the following actions directly would involve a side effect:

Reassigning a variable
Modifying a data structure in place
Setting a field on an object
Throwing an exception or halting with an error Printing to the console or reading user input Reading from or writing to a file
Drawing on the screen

Pure function

f(x)

A function with input type A and output type B (written in Scala as a single type: A => B) is a computation which relates every value a of type A to exactly one value b of type B such that b is determined solely by the value of a.

For example, a function intToString having type Int => String will take every integer to a corresponding string. Furthermore, if it really is a function, it will do nothing else.

In other words, a function has no observable effect on the execution of the program other than to compute a result given its inputs; we say that it has no side effects. We sometimes qualify such functions as pure functions to make this more explicit. You already know about pure functions. Consider the addition (+) function on integers. It takes two integer values and returns an integer value. For any two given integer values it will always return the same integer value. Another example is the length function of a String in Java, Scala, and many other languages. For any given string, the same length is always returned and nothing else occurs.

We can formalize this idea of pure functions by using the concept of referential transparency (RT). This is a property of expressions in general and not just functions. For the purposes of our discussion, consider an expression to be any part of a program that can be evaluated to a result, i.e. anything that you could type into the Scala interpreter and get an answer. For example, 2 + 3 is an expression that applies the pure function + to the values 2 and 3 (which are also expressions). This has no side effect. The evaluation of this expression results in the same value 5 every time. In fact, if you saw 2 + 3 in a program you could simply replace it with the value 5 and it would not change a thing about your program. This is all it means for an expression to be referentially transparent—in any program, the expression can be replaced by its result without changing the meaning of the program. And we say that a function is pure if its body is RT, assuming RT inputs.

En funksjon er ikke pure om den endrer tilstand (global tilstand)

Referential Transparency

We can formalize this idea of pure functions by using the concept of referential transparency (RT). This is a property of expressions in general and not just functions. For the purposes of our discussion, consider an expression to be any part of a program that can be evaluated to a result, i.e. anything that you could type into the Scala interpreter and get an answer. For example, 2 + 3 is an expression that applies the pure function + to the values 2 and 3 (which are also expressions). This has no side effect. The evaluation of this expression results in the same value 5 every time. In fact, if you saw 2 + 3 in a program you could simply replace it with the value 5 and it would not change a thing about your program. This is all it means for an expression to be referentially transparent—in any program, the expression can be replaced by its result without changing the meaning of the program. And we say that a function is pure if its body is RT, assuming RT inputs.

SIDEBAR Referential transparency and purity An expression e is referentially transparent if for all programs p, all occurrences of e in p can be replaced by the result of evaluating e, without affecting the observable behavior of p. A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x.1

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.[1] Some programming language theorists require support for anonymous functions as well.[2]

    import collection.mutable

    case class Person(name: String, age: Int, postCode: String)

    object HigherOrder extends App {
      val kaare = Person("Kaare", 29, "0770")
      val kjell = Person("Kjell", 30, "0770")
      val anne = Person("Anne", 17, "0770")

      val people = kaare :: kjell :: anne :: Nil


      val myndigePersoner: Person => Boolean = .age >= 18
      val ropende: (Person) => String = .name.toUpperCase


      def foreach(ps: Seq[Person])(f: Person => Unit): Unit = {
        for (p <- ps) yield {
          f(p)
        }
      }

       foreach(people){ p =>
         println(p)
       }

      val eachPerson = foreach(people) _

      eachPerson(println)

      val myndige = people.filter(myndigePersoner).map(ropende)

      println(myndigePersoner(anne))

    }
    

Monomorphic functions

Polymorphic functions

def writerA{println(a)}

def numWriterA:Numeric{println(a)}

Endofunction

A => A

Currying

(A,B)=>C

A => B => C

Ta case class Person(name:String, age:Int) i repl

så en (Person(,))

så en (Person(,)).curried

Every function that takes more than one argument has a kind of normal form, called its curried form. Instead of a function taking a single tuple of n arguments, a curried function is a chain of n functions that take one argument each. For example, a function of a type like (A,B) => C can be transformed into a function of type A => (B => C). The resulting (curried) function takes the first argument of type A and then returns another function that receives the second argument of type B. The arrow (=>) in function types actually associates to the right, so the parentheses in this case are superfluous. You may often see a type like this written A => B => C. Footnote 2mThis is named after the mathematician Haskell Curry, who discovered the principle. It was independently discovered earlier by Moses Schoenfinkel, but "Schoenfinkelization" didn't catch on.

Partial application

def multiply(x:Int,y:Int):Int = x y def double:Int=>Int = multiply(2,_) println(multiply(4,4)) println(double(3))

Partial application is straightforward. It's simply the act of passing a function some of its arguments and leaving the rest unspecified. The result is a function that takes the rest of the arguments. For example:

Here we have partially applied the function by passing 2 as one of its arguments. The result is a function that multiplies its argument by 2.

Partial function

Dette ligna jo i ord iaff. Men ikke i betydning

A function works for every argument of the defined type. In other words, a function defined as (Int) => String takes any Int and returns a String.

A Partial Function is only defined for certain values of the defined type. A Partial Function (Int) => String might not accept every Int.

isDefinedAt is a method on PartialFunction that can be used to determine if the PartialFunction will accept a given argument.

Note PartialFunction is unrelated to a partially applied function that we talked about earlier. See Also Effective Scala has opinions about PartialFunction. scala> val one: PartialFunction[Int, String] = { case 1 => "one" } one: PartialFunction[Int,String] = <function1>

scala> one.isDefinedAt(1) res0: Boolean = true

scala> one.isDefinedAt(2) res1: Boolean = false

You can apply a partial function. scala> one(1) res2: String = one

PartialFunctions can be composed with something new, called orElse, that reflects whether the PartialFunction is defined over the supplied argument.

scala> val two: PartialFunction[Int, String] = { case 2 => "two" }

scala> val three: PartialFunction[Int, String] = { case 3 => "three" }

scala> val wildcard: PartialFunction[Int, String] = { case _ => "something else" }

scala> val partial = one orElse two orElse three orElse wildcard

scala> partial(5)

res24: String = something else

scala> partial(3)

res25: String = three

scala> partial(2)

res26: String = two

scala> partial(1)

res27: String = one

scala> partial(0)

res28: String = something else

Function Composition

Function Composition Let’s make two helpful functions: val addUmm: (String) => String = {x=> x + " umm"} val addAhem: (String) => String = {x=> x + " ahem"}

compose compose makes a new function that composes other functions f(g(x)) addAhem(addUmm("Yo")) val ummThenAhem = addAhem compose addUmm

andThen andThen is like compose, but calls the first function and then the second, g(f(x)) addUmm(addAhem("Yo")) val ummThenAhem = addAhem compose addUmm