Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Monthly Archives: June 2018

214: Orthogonal Matrices

In linear algebra, an orthogonal matrix is a square matrix A such that

AT^T = A^T A = I.

Equivalently, the rows and columns of A are, respectively, orthonormal vectors: vectors which are all unit length and orthogonal to one another.

Also equivalently, A^{-1} = A^T.

A fun fact about orthogonal matrices is that their determinants are always \pm 1.

Advertisements

213: B-trees

A B-tree is a type of balanced search tree which is well-suited and commonly used for storing large amounts of data, such as in a database system. It is described using a positive constant m \in \mathbb{Z}, which defines the maximum number of children a single node can have. (Take BSTs as a specific example with m = 2.) Using m the tree is defined by the following properties:

  • Every leaf node is at the same depth in the tree
  • Where a node has b children, it has b - 1 values. The values are used as ‘bookmarks’ sandwiched in between the children in a manner generalized from BSTs: the values are sorted, and a child in between 2 values contains all values between them in the tree.
  • Every node except possibly the root is at least half-full, having between \frac{m}{2} and m values.
  • Each leaf node obviously has no children, but can still hold multiple values up to some arbitrary maximum (usually defined by disk block size or some other sensible constraint, depending on the setting).

As an example, below is an example of a B-tree with m = 5 and where leaves have enough room for 3 values each:

Upon inspection one can see that the sorting invariant similar to that used in BSTs is satisfied, e.g. all leaf values in between 15 and 20 are found by going to the child to the left of ’20’ in the root node, then to the child to the right of ’15’.

For obvious reasons, B-trees result in log-time operations. Lookup is straightforward, although insertions and deletions are more involved and difficult to implement. However, B-trees offer advantages over other search trees such as being optimized for reading/writing large blocks of data without too much unnecessary disk access.

212: fromIntegral (Haskell)

In Haskell, fromIntegral is a handy function for getting ints and floats (or other Num types) to play nice together. (Ints can automatically be converted to floats in some cases, such as evaluating the expression 3 + 0.0 which returns the float 3.0, but this is not always the case.)

The type declaration of fromIntegral is

fromIntegral :: (Num b, Integral a) => a -> b.

That is, as long as a is an Integral type (a number that acts like an integer), it returns it as the equivalent Num object, the type of which the compiler infers from context. This enables you to safely evaluate expressions like fromIntegral (length [0, 1, 2]) + 0.0, which again returns the float 3.0.

211: Typeclasses (Haskell)

In Haskell, typeclasses are roughly the equivalent of interfaces in languages like Java.

Consider what happens when we inspect the type of the < operator with :t (<). We get

(<) :: Ord a => a -> a -> Bool.

The Ord a => bit coming before the type of the operator is called a class constraint, and just means that the type a which the less-than operator operates on must be in the Ordinal typeclass. That is, it must have some sort of interface for determining whether one element of the class is less than another.

A type can belong to many different typeclasses (similarly to interfaces in Java), so for other functions you might instead see multiple typeclass constraints for a function, e.g. (Ord a, Num a) => if the type a is required to be an ordinal number type.

Here are some common typeclasses in Haskell:

  • Eq: types whose members can be tested against each other for equality
  • Show: types whose members can be represented as strings
  • Enum: types whose members can be enumerated (and thus can be used in list ranges)
  • Num: types whose members can act like numbers

 

210: Type Variables (Haskell)

In Haskell, type variables are roughly the equivalent of generics in languages like Java. They enable a function to operate on and return different types, so long as the function doesn’t depend on any specific behavior of the types involved. (These are called polymorphic functions.)

For instance, if in GHCI we use :t head to examine the type of the head function which returns the first element of a list, we see it has the type head :: [a] -> a. a is a type variable, meaning it could be any type. This just means head takes a list with elements of any type a and returns a single element of that same type.

As another example, :t fst gives fst :: (a, b) -> a. Since pairs in Haskell aren’t homogenous, it’s possible that a pair’s first and second elements have different types a and b respectively (although they could be the same). fst just returns a single element of type a.

209: Intro To Haskell Types

In Haskell, everything’s an expression, and every expression has a type.

Haskell has a static type system, so it knows everything’s type at compile time. In GHCI, you can use :t expr to get the type of expr. For instance, the :t (True, 'a') gives (True'a') :: (BoolChar) . (The notation ‘::’ is read as “has type”.)

Haskell also has type inference, meaning the Haskell compiler infers the type from context, unlike languages like Java where you have to explicitly state the type of everything. Despite this, you can still explicitly declare the type of functions, which is considered good practice. The type is typically declared on the line before the function definition, also using ‘::’ notation.

As an example, this line would go before a function removeNonUppercase which filters a string to include only uppercase characters:

removeNonUppercase :: [Char] -> [Char].

To clarify, [Char] -> [Char] is itself the type of the function: that of functions which map lists of Chars to lists of Chars.

As a less trivial example, the following could be the definition of a function which adds 3 numbers:

addThree :: Int -> Int -> Int -> Int

addThree x y z = x + y + z

The last Int refers to the return type and the first 3 are the input parameters. (The notation seems to imply currying, but I’ll have to get into the details of that another time.)

 

208: The Einstellung Effect

The Einstellung Effect is a cognitive phenomenon wherein an agent attempting to solve a problem fails to think outside the box, where the ‘box’ results from its previous experience solving problems.

More specifically, the agent working on a problem is predisposed to attempt solutions similar to those it’s had success with in the past — even though these may be sub-optimal or not viable solutions at all for the problem at hand — rather than go in with an “open mind” and experiment with other approaches. Previous experience is overly relied on or mistaken to be more useful than it is, so the area of the possible solution space the agent examines is narrow/specific to a fault.

Perhaps unsurprisingly, studies have implied the effect seems to increase with age in humans, which goes along with stereotypes of younger minds being more flexible and open to possibilities while older minds have a stronger tendency to “stay on the tracks”.

The Einstellung Effect is one of the obstacles to good problem-solving which can be effectively avoided in many cases by periodic reminders to the problem solver to simply take a step back and re-examine things.

207: Haskell Tuples

Continuing with learning Haskell, here are some of the basic points defining the behavior of tuples.

  • Unlike lists in Haskell, tuples are not homogenous structures and can contain elements of different types. That is, (5, "five") is a valid tuple.
  • The type of a tuple depends on its number of elements. To illustrate this point, since lists are homogenous [(0, 1), (1, 0)] is a valid list, since all its elements are pairs (tuples with 2 elements), but [(0, 1), (1, 0, 0)] is not, since it contains both a pair and a triple.
  • The type of a tuple also depends on the type of its elements. This means [(0, 1), ("one", 0)] is not a valid list either.
  • Singleton tuples and empty tuples aren’t allowed.

Two methods which are specific to 2-tuples are fst and snd, which respectively return the first and second elements of a pair.

Finally, a list method which involves tuples in its return type is zip. The expression zip a b, where a and b are lists, returns a list of 2-tuples containing the lists respective 1st elements, 2nd elements, and so on. For instance, zip [1, 2, 3] ["one", "two", "three"] returns the list [(1, "one"), (2, "two"), (3, "three")]. If the two lists aren’t the same length, the method behaves true to the lazy nature of Haskell and stops with the last element of the shorter list, meaning you can safely use zip when one of the lists is infinite.

206: Haskell List Methods

Continuing with learning Haskell, here are some functions you can operate on lists with:

  • head returns the first element of a list
  • tail returns everything except the first element
  • last returns the last element
  • init returns everything except the first element

[Note: all 4 of the above methods give errors when handed empty lists.]

  • null xs returns True iff xs is empty (i.e. length xs == 0)
  • take n xs returns the sublist of the first n elements of xs . (If length xs < n the function call is still valid and just returns xs itself.)
  • drop n xs returns the sublist of xs without the first n elements
  • elem x xs or equivalently x `​elem` xs returns True iff x is an element of xs
  • ranges have convenient notation in Haskell: [1..5] is equivalent to the list [1, 2, 3, 4, 5]. Note that 2 dots are used, not 3, and also that the endpoints of the range are inclusive.
  • You can also use step sizes other than the default 1 in ranges. For instance, [1, 4 .. 20] is equivalent to the list [1, 4, 7, 10, 13, 16, 19]. This comes in handy when you want to specify a range in descending order, e.g. [5, 4..1] gives [5, 4, 3, 2, 1].
  • Since Haskell evaluates things like ranges lazily, you can also specify finite subsets of infinite ranges, e.g. take 3 [1, 2..] gives [1, 2, 3].
  • One possible use of the above is using it on the infinite list range cycle xs which just concatenates xs onto itself indefinitely.
  • List comprehensions have a very set-builder-notation-inspired syntax in Haskell. For instance, the comprehension [2*x | x <- [1..10], 2*x >= 12] is equivalent to the Python list comprehension [2*x for x in range(1, 11) where 2*x >= 12]and gives the list [12, 14, 16, 18, 20].

 

205: More Haskell Syntax

Continuing to familiarize myself with the basics of Haskell syntax, so here are some of the oddities thereof I came across today:

  • if statements are expressions, and thus must evaluate to a value, and thus require an else clause. Contrast this with imperative languages like Python and Java where if clauses are instructions, not expressions, and the else bit is optional.
  • Lists are homogenous, which isn’t that weird but is worth noting. For instance, you can’t have ints and strings in the same list. Also [1, 2, 3.0] will evaluate to the list [1.0, 2.0, 3.0]: since the list has to be homogenous the ints must be converted to equivalent floats.
  • There’s a really nice consistency in the syntax between variable definition (x = 0) and function definition (f x = 2*x). Both x and f are just expressions dependent on 0 or more arguments after all, so Haskell syntax reflects this view that values are just 0-ary functions.
  • ++ is used for list concatenation, e.g. [1, 2] ++ [3, 4] evaluates to [1, 2, 3, 4]. You can use sloppy infix notation without parentheses, so that "f" ++ "o" ++ "o" is a valid expression resulting in the string "foo". Concatenating lists s and t with s ++ t takes O(m) time, where m is the length of s. (Haskell walks through the entire first argument to ++.)
  • : is the symbol for the cons operator. For instance, 1 : [2, 3] evaluates to the list [1, 2, 3](and in fact [1, 2, 3] is just syntactic sugar for 1 : 2 : 3 : [].