regiskuckaertz

/*

L :== integer
    | L + L
    | L * L
    | (L)
    | L / L

 */

regiskuckaertz

val hosts: List[HttpHost] = ???
val client = new RestHighLevelClient(
  RestClient.builder(hosts: _*)
    .setHttpClientConfigCallback(new RestClientBuilder.HttpClientConfigCallback {
      def customizeHttpClient(httpClientBuilder: HttpAsyncClientBuilder): HttpAsyncClientBuilder =
        httpClientBuilder.addInterceptorLast(new RequestAcceptEncoding())
      })
)

regiskuckaertz

Thirty years ago, Jon Bentley wrote "Programming Pearls", a collection of great (imperative) algorithms. One of them was to find the maximum segment sum:

Given a list of numbers, the task is to compute the largest possible sum of a consecutive segment.

The "pearls" schtick caught on in the FP community, which came up with a research paper (of course) called "Functional pearls". In his book "Pearls of functional algorithm design", Richard Bird calculates an efficient version by derivation.

It starts with the specification:

regiskuckaertz

Derivations are the bread and butter of functional programming. It is easy to fall into the trap of thinking it is a pointless academic exercise, which is the reason why a lot of people struggle with FP. Functional programs are not so much written, they're calculated. It is here that the true power of equational reasoning (i.e. being able to swap the left and right parts of an equation everywhere in the code) help us.

So, getting comfortable reading and doing derivations is a must for any FP practitioner.

Below are the ones we did in the previous sessions, plus a couple of exercises.

Fold fusion

regiskuckaertz

module Levenshtein where

pairs :: [a] -> [(a,a)]
pairs [x,y] = [(x,y)]
pairs (x:y:xs) = (x,y) : pairs (y:xs)

vowels :: String
vowels = "aeiou"

cost :: Rational -> Rational -> Rational -> Char -> Char -> Rational

regiskuckaertz

object PlayJsonDynamoFormat {
  implicit val format: DynamoFormat[JsValue] = DynamoFormat.xmap[JsValue, String](
    x => Try(Json.parse(x)) match {
      case Success(y) => Right(y)
      case Failure(f) => Left(TypeCoercionError(t))
    }
  )(Json.stringify(_))
}

regiskuckaertz

We saw that every data type is inhabited by a value ⊥ pronounced "bottom". It is very important in a non-strict language such as Haskell to represent how much knowledge you have about a value. You can either know exactly what the value is, know only a part of it, or know nothing at all. Bottom represents the latter, but you could as well only know that a list starts with 1, i.e. 1 : ⊥.

In fact, all data types in Haskell respect an approximation function ⊑, where x ⊑ y means "x is an approximation of y". For example with booleans, x ⊑ y iff ⇔ x ≡ ⊥ or x ≡ y in other words either you don't know anything about a particular boolean, or you know exactly what it is. This approximation ordering is important when reasoning about recursive algorithms, which is why it is important to understand the notion of "nothingness" in Haskell.

regiskuckaertz

Let's see what Wolfram Alpha has for us:

RTA is the sequence obtained from reversing the digits of a number n and adding the result to the original number. The 196-algorithm operates RTA iteratively until a palyndromic number is obtained.

Let's define alg196 then. We can take the definition above literally and get the following script:

alg196 :: Integer -> [Integer]
alg196 n = takeWhile palyndromic . rtaseq n

regiskuckaertz

Today we did two derivations to flex our type muscles.

From type to expression

What is the definition of foo given its type:

foo :: Functor f => a -> f (x, b) -> f (x, a)

Well, we know that it takes two arguments, a value which we know nothing about, and another which has two qualities: (1)

regiskuckaertz

> module Anagrams where

Here is our specification:

Describe how you would go about designing `anagrams :: Int -> [Word] -> String` so that anagrams n 
takes a dictionary (a sorted list of English words), extracts the n-letter ones and prints a string
that gives a list of the anagram entries for the n-letter words. Assume `type Word = String`.

Because `Word` is a type in the Prelude, we need to hide it from scope. That's how it's done: