\documentclass[12pt,a4paper]{report}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{setspace}
\title{Haskell}
\author{Ben Kero}
\begin{document}
\doublespace
\maketitle

% History and Performance
\subsection*{History and Performance}
A latecomer to the game, Haskell represents a modern, purely function programming language.  It was created and released in 1990, and remained in relative obscurity until recently.  It's named after it's cretator, the logician Haskell Curry.  The programming concept of treating functions as first-class variables, and creating new ones based off the originals with different parameters is called a ``curry'', and is also named after Haskell Curry.  Parallelization in modern computer hardware has necessitated easily parallelizable programming languages.  Haskell fills a certain sweet spot between being easily readable and writable, and having high optimization.

Several high-performance interpreters and compilers exist for Haskell.  Some of these compilers allow Haskell to translate to more efficient machine-level instructions than the old mainstay, the C programming language.  Debian's Alioth Programming Language Shootout measures how well many programming languages deal with common problems, such as performing massive regular expressions on DNA 8-mers, and allocating/deallocating many binary trees.

The performance of each programming language is measured in runtime, and how well the language utilizes the hardware.  For instance, a single-threaded C program might be faster in a single thread, but will lose to a threaded Haskell implementation because the load is distributed across all available processors.  Some of the tests where Haskell trounces almost all programming language include thread-ring benchmarks, which involve switching from thread to thread passing a single token along the switch, and streaming arbitrary-precision arithmetic.

% Characteristics
\subsection*{Characteristics and Features}
Sokme of the characteristics that define Haskell and make it unique among other languages are lazy evaluation, pattern matching, currying, list comprehensions, guards, definable operators, and single assignment.

Lazy evaluation is a method of delaying computation until it's needed.  For instance, in Haskell it's possible to have an array with the range 2 to infinity.  The way to accomplish a simple instance of this in Haskell is to define an array as ``[2..]''.  This is powerful in that it allows the programmer to create infinite data structures and only evaluate what is needed.

The operation that checks for patterns inside a set of things is called pattern matching.  It differs from pattern recognition in that pattern matching has a much more rigorous specification.  Pattern matching is commonly used for testing the existence of structures inside an unknown argument.

Currying, the namesake of this languages author, is the ability to take a function, and create a new function with altered arguments.  For example, if $f(x,y) = 3x+2y$, $g(x)$, a curry of $f(x,y)$ could be $g(x) = f(x,3)$.

The best way to describe list comprehensions is to liken them to ``for'' statements.  They evaluate all of the members of an array as arguments to a common function, very similar to the ``map'' function defined in other languages.  This is very powerful because it allows Haskell to parallize code without original intent of the author.  ``for'' loops are very hard to parallelize because they often have temporary variables, don't implement any sort of mutual exclusion or locking when they need to, and often share resources.

Guards are slightly unusual to have in functional languages.  Nevertheless, Haskell implements guards to create conditional execution and logic.  These can be nice additions to pattern matching, so even if a pattern does match, if a guard is not met, the statement is not evluated.

Definable operators are simply the ability to overload standard operators to provide alternate routines for standard operators to allow them to operate on non-standard datatypes.  For instance, a programmer could overload the ``+'' operator to work on lists as well as integers.  This allows a convenient and easy-to-read infix notation.

The idea of single assignment is merely the constraint that once a variable has been defined as a value, it can no longer be changed to something else.  A good example of this would be if in a statement, a programmer set the variable X to be defined as the value ``4'', it cannot be changed on a subsequent line to be the value ``5''.  Such an action is illegal in a language defined with the ``single assignment'' principle.

Being a functional language, Haskell obviously supports the concept of recursive functions, which are the ability for a function to call itself, until it meets some base condition, in which event it ``recurses'' back up the series of calls until it exits.

% Purpose
\subsection*{Purpose}
Haskell has found it's way into many situations, such as the desktop applications through the tiling window manager Xmonad, in revision control systems through the dreadfully slow application Darcs, and through being a basis for the extension of other programming languages, such as Pugs, the Perl 6 compiler, which is entirely written in Haskell.

% Example
\subsection*{Example: The Knight's Tour}
Here is an example of a solution to a problem called The Knight's Tour.  The problem involves an N by N chessboard, and a chess piece known as the ``Knight''.  The objective is to visit every square of the chess board without repeating a visit.  It's widely regarded as a difficult problem, and all solutions are computationally expensive.  This solution uses complex Haskell data structures known as monads.

\begin{verbatim}
import Control.Monad.Logic
 
import Data.List
import Data.Maybe
import Data.Ord
import Data.Ix
import qualified Data.Map as Map
import System.Environment
 
successors n b = sortWith (length . succs) . succs
 where sortWith f = map fst . sortBy (comparing snd) . map (\x -> (x, f x))
       succs (i,j) = [ (i', j') | (dx,dy) <- [(1,2),(2,1)]
                                , i' <- [i+dx,i-dx] , j' <- [j+dy, j-dy]
                                , isNothing (Map.lookup (i',j') b)
                                , inRange ((1,1),(n,n)) (i',j') ]
tour n k s b | k > n*n   = return b
             | otherwise = do next <- msum . map return $ successors n b s
                              tour n (k+1) next $ Map.insert next k b
showBoard n b = unlines . map (\i -> unwords . map (\j ->
                  pad . fromJust $ Map.lookup (i,j) b) $ [1..n]) $ [1..n]
 where k = ceiling . logBase 10 . fromIntegral $ n*n + 1
       pad i = let s = show i in replicate (k-length s) ' ' ++ s
main = do (n:_) <- map read `fmap` getArgs
          let b = observe . tour n 2 (1,1) $ Map.singleton (1,1) 1
          putStrLn $ showBoard n b
\end{verbatim}

% Comparison
\subsection*{Comparison}
Logically, Haskell is more straightforward than other programming languages, such as Lisp.  Haskell may use many less parenthesis, yet accomplish the same tasks as Lisp, indeed even in the same manner.  This allows it to be much more readable, but still be interpreted to perform the same routines.  It also has a wide variety of libraries available for it, so that it may perform the same tasks that other popular languages, such as Python enjoy.

% Predecessors
\subsection*{Predecessors}
Haskell borrowed much of it's functional basis on the excessively old programming language Lisp.  It was originally menat as a replacement for the programming language Miranda, because Miranda was not released under the public domain, not everybody could use it.  Many of the ideas also came from the programming language ML, such as the concepts of lazy evaluation and pattern matching.

% Bibliography
\subsection*{Bibliography}
Alotioth Programming Language Shootout: http://shootout.alioth.debian.org/u64q/
\end{document}