Regis Kuckaertz 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)

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

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.

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

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:

Prelude

In order to run your program and get some meaningful statistics:

download this list of Sudoku puzzles
set up a simple main that will run your sudoku against each line of the file:

main = do
  matrices <- lines <$> getContents

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

	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(_))
	}

	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

	module Sudoku where

	type Row a = [a]
	type Matrix a = [Row a]
	type Digit = Char
	type Grid = Matrix Digit

	-- sample3 is unsolvable
	sample1, sample2, sample3 :: Grid
	sample1 = ["2....1.38"