Random Functional/Math Readings

http://en.wikipedia.org/wiki/Memoization
an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

http://en.wikipedia.org/wiki/Associative_array
Map

http://en.wikipedia.org/wiki/Red-black_tree
= Self-balancing Binary Search Tree

http://www.haskell.org/haskellwiki/Smart_constructors


http://www.haskell.org/haskellwiki/Type_arithmetic
Type arithmetic (or type-level computation) are calculations on the type-level, often implemented in Haskell using functional dependencies to represent functions.

 data Zero
 data Succ a
 
 class Add a b ab | a b -> ab, a ab -> b
 instance Add Zero b b
 instance (Add a b ab) => Add (Succ a) b (Succ ab)

http://www.haskell.org/haskellwiki/Fundeps
Functional dependencies are used to constrain the parameters of type classes

http://www.haskell.org/haskellwiki/Peano_numbers
Peano numbers are a simple way of representing the natural numbers using only a zero value and a successor function.

http://en.wikipedia.org/wiki/Curry-Howard
The Curry–Howard correspondence is the direct relationship between computer programs and proofs in programming language theory and proof theory. Also known as Curry–Howard isomorphism, proofs-as-programs correspondence and formulae-as-types correspondence, it is a generalization of a syntactic analogy between systems of formal logic and computational calculi that was first discovered by the American mathematician Haskell Curry and logician William Alvin Howard.

Big-O Comparison

http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html

Here is a table of typical cases, showing how many "operations" would be performed for various values of N. Logarithms to base 2 (as used here) are proportional to logarithms in other base, so this doesn't affect the big-oh formula.

	constant	logarithmic	linear		quadratic	cubic
n	O(1)	O(log N)	O(N)	O(N log N)	O(N2)	O(N3)
1	1	1	1	1	1	1
2	1	1	2	2	4	8
4	1	2	4	8	16	64
8	1	3	8	24	64	512
16	1	4	16	64	256	4,096
1,024	1	10	1,024	10,240	1,048,576	1,073,741,824
1,048,576	1	20	1,048,576	20,971,520	1012	1016

Searching

Here is a table of typical cases.

Type of Search	Big-Oh	Comments
Linear search array/ArrayList/LinkedList	O(N)
Binary search sorted array/ArrayList	O(log N)	Requires sorted data.
Search balanced tree	O(log N)
Search hash table	O(1)

Algorithm	array ArrayList	LinkedList
access front	O(1)	O(1)
access back	O(1)	O(1)
access middle	O(1)	O(N)
insert at front	O(N)	O(1)
insert at back	O(1)	O(1)
insert in middle	O(N)	O(1)

Sorting arrays/ArrayLists

Some sorting algorithms show variability in their Big-Oh performance. It is therefore interesting to look at their best, worst, and average performance. For this description "average" is applied to uniformly distributed values. The distribution of real values for any given application may be important in selecting a particular algorithm.

Type of Sort	Best	Worst	Average	Comments
BubbleSort	O(N)	O(N2)	O(N2)	Not a good sort, except with ideal data.
Selection sort	O(N2)	O(N2)	O(N2)	Perhaps best of O(N2) sorts
QuickSort	O(N log N)	O(N2)	O(N log N)	Good, but it worst case is O(N2)
HeapSort	O(N log N)	O(N log N)	O(N log N)	Typically slower than QuickSort, but worst case is much better.

Maths/Algebra

http://en.wikipedia.org/wiki/Big_O_notation
Knuth Big O Calculus
A Crash Course on Algebra
http://en.wikipedia.org/wiki/List_of_mathematical_symbols

Scala Logging

Scala Logging

http://scala-programming-language.1934581.n4.nabble.com/verbose-logger-usage-td3084112.html

AOP:
<http://jonasboner.com/2008/02/06/aop-style-mixin-composition-stacks-in-scala.html>
<http://jonasboner.com/2008/10/06/real-world-scala-dependency-injection-di.html>
<http://jonasboner.com/2008/12/09/real-world-scala-managing-cross-cutting-concerns-using-mixin-composition-and-aop/> 

Pointfree

http://www.haskell.org/haskellwiki/Pointfree

it is clearer to write

let fn = f . g . h

than to write

let fn x = f (g (h x))

The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values.

Pros
This style is particularly useful when deriving efficient programs by calculation and, in general, constitutes good discipline. It helps the writer (and reader) think about composing functions (high level), rather than shuffling data (low level).
It is a common experience when rewriting expressions in pointfree style to derive more compact, clearer versions of the code -- explicit points often obscure the underlying algorithm.


Cons
Point-free style can (clearly) lead to Obfuscation when used unwisely. As higher-order functions are chained together, it can become harder to mentally infer the types of expressions. The mental cues to an expression's type (explicit function arguments, and the number of arguments) go missing.
Point-free style often times leads to code which is difficult to modify. A function written in a pointfree style may have to be radically changed to make minor changes in functionality. This is because the function becomes more complicated than a composition of lambdas and other functions, and compositions must be changed to application for a pointful function.
Perhaps these are why pointfree style is sometimes (often?) referred to as pointless style.

eta conversion

http://www.haskell.org/haskellwiki/Eta_expansion

eta conversion (also written η-conversion) is adding or dropping of abstraction over a function. For
example, the following two values are equivalent under η-conversion:

\x -> abs x

and

abs

Converting from the first to the second would constitute an eta reduction, and moving from the second to the first would be an eta abstraction.