Haskell

Pre-History

1930s-1950s

Lambda Calculus (Turing)

Combinatory Calculus (Curry & Feys)

LISP (McCarthy)

1960s-1970s

Operational (Landin) and Denotational (Strachey) semantics

ML (Milner)

Lazy FP & Graph Reduction (Turner)

1980s

Miranda (Turner)

Lazy ML (Augustsson & Johnsson)

Early History

1987

More than a dozen non-strict FP languages in use

FCPA '87 meeting (Peyton Jones, Hudak, et. al.)

Formed FPLang committee

Wanted to base language on Miranda, but Turner declined

1988

Chose the name Haskell

Hudak and Wadler chosen to be editors of the report

1990 (April 1st!)

Haskell 1.0 report published (125 pages)

Evolution

1992

Glasgow Haskell Compiler (GHC)

1996

Haskell 1.3 - Monadic I/O, seq, strictness annotations

1999

Haskell 98 - Commitment to stability

2002

Revised Haskell 98 (260 pages)

Fun Quotes

Tony Hoare (1990s?)

I fear that Haskell is doomed to succeed

Simon Peyton Jones (2003)

Motto: avoid success at all costs

Haskell: Batteries Included (2008)

Avoid "avoiding success"

Domain

General Purpose

• Very effective for parsing and compilation
• Great for DSEL (Domain Specific Embedded Languages)
• Has been popular in academia for some time
• Becoming more popular in industry

Commercial Use

Biotech

Amgen - informatics, simulation

Finance

Credit Suisse - quantitative modeling

Barclays - DSEL for exotic equity derivatives

Deutsche Bank - trading group infrastructure

Tsuru Capital - trading platform

McGraw-Hill Financial - report generation (with ermine)

Semiconductor Design

Bluespec - high-level language for chip design

Consumer Apps

Silk

"A platform for sharing collections about anything"

Chordify

"Chord transcription for the masses"

Bump (Google, Sep 2013)

"Send files, videos, everything!" Mobile + web.

MailRank (Facebook, Nov 2011)

Email inbox prioritization. Shuttered post-acquisition.

Bazqux

"RSS reader that shows comments to posts"

Compilers

Haskell

GHC, Ajhc, Haste, GHCJS

Dependently typed

Agda - also an interactive proof assistant!

Idris - general purpose

Compile to JavaScript

Elm - functional reactive in the browser

Fay - Haskell subset

Imperative

Pugs - first Perl 6 implementation

Standalone Apps

Pandoc

Markup swiss-army knife (used to make these slides!)

Darcs

Distributed revision control system (like Git or Mercurial)

xmonad

"the tiling window manager that rocks"

Gitit

Wiki backed by Git, Darcs, or Mercurial

git-annex

Manage large files with git (similar to Dropbox)

ImplicitCAD

Programmatic Solid 3D CAD modeler

Declarative

• "Describe the problem, not the solution"
• Great syntax for this (but not C-like)!
• Functional code is (often) easier to understand and test
• Pure, no side-effects?!

-- MergeSort1.hs
module MergeSort1 (mergeSort) where

-- | Bottom-up merge sort.
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort xs = mergeAll [[x] | x <- xs]

mergeAll :: Ord a => [[a]] -> [a]
mergeAll [xs] = xs
mergeAll xss  = mergeAll (mergePairs xss)

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs (a:b:xs) =
  merge a b : mergePairs xs
mergePairs xs = xs

merge :: Ord a => [a] -> [a] -> [a]
merge as@(a:as') bs@(b:bs')
 | a > b     = b : merge as bs'
 | otherwise = a : merge as' bs
merge [] bs = bs
merge as [] = as

-- MergeSort2.hs
module MergeSort2 (mergeSort) where

-- | Bottom-up merge sort.
mergeSort :: Ord a => [a] -> [a]
mergeSort = mergeAll . map (:[])
  where
    mergeAll []   = []
    mergeAll [xs] = xs
    mergeAll xss  = mergeAll (mergePairs xss)

    mergePairs (a:b:xs) =
      merge a b : mergePairs xs
    mergePairs xs = xs

    merge as@(a:as') bs@(b:bs')
      | a > b     = b : merge as bs'
      | otherwise = a : merge as' bs
    merge [] bs = bs
    merge as [] = as

what.the >>=?

• do is just syntax sugar for the >>= (bind) operator.
• IO is still purely functional, we are just building a graph of actions, not executing them in-place!
• Starting from main, the Haskell runtime will interpret these actions
• It works much like continuation passing style, with a state variable for the current world state (behind the scenes)
• There are ways to cheat and write code that is not pure, but you will have to go out of your way to do it

Pure

• Haskell's purity implies referential transparency
• This means that function invocation can be freely replaced with its return value without changing semantics
• Fantastic for optimizations
• Also enables equational reasoning, which makes it easier to prove code correct

Optimizations

• Common sub-expression elimination
• Inlining (cross-module too!)
• Specialize
• Float out
• Float inwards
• Demand analysis
• Worker/Wrapper binds
• Liberate case
• Call-pattern specialization (SpecConstr)

GHC RULES!

• Term rewriting engine
• RULES pragma allows library defined optimizations
• Used to great effect for short cut fusion
• Example: map f (map g xs) = map (f . g) xs
• Prevent building of intermediate data structures
• Commonly used for lists, Text, ByteString, etc.
• Great incentive to write high-level code!
• ANY LIBRARY CAN USE THIS!

Lazy

• Call by need (outside in), not call by value (inside out)
• Non-strict evaluation separates equation from execution
• No need for special forms for control flow, no value restriction
• Enables infinite or cyclic data structures
• Can skip unused computation (better minimum bounds)

Call by need

• Expressions are translated into a graph (not a tree!)
• Evaluated with STG (Spineless Tagless G-Machine)
• Pattern matching forces evaluation

Types

• Enforce constraints at compile time
• No NULL
• Can have parametric polymorphism and/or recursion
• Built-in types are not special (other than syntax)
• Typeclasses for ad hoc polymorphism (overloading)

h> let f x = head True

<interactive>:23:16:
    Couldn't match expected type `[a0]' with actual type `Bool'
    In the first argument of `head', namely `True'
    In the expression: head True
    In an equation for `f': f x = head True

h> let f x = heads True

<interactive>:24:11:
    Not in scope: `heads'
    Perhaps you meant one of these:
      `reads' (imported from Prelude), `head' (imported from Prelude)

h> let x = x in x
-- Infinite recursion, not a fun case to deal with!

h> case False of True -> ()
*** Exception: <interactive>:29:1-24: Non-exhaustive patterns in case

h> head []
*** Exception: Prelude.head: empty list

h> error "this throws an exception"
*** Exception: this throws an exception

h> undefined
*** Exception: Prelude.undefined

-- Polymorphic and recursive
data List a = Cons a (List a)
            | Nil
            deriving (Show)

data Tree a = Leaf a
            | Branch (Tree a) (Tree a)
            deriving (Show)

listMap :: (a -> b) -> List a -> List b
listMap _ Nil         = Nil
listMap f (Cons x xs) = Cons (f x) (listMap f xs)

treeToList :: Tree a -> List a
treeToList root = go root Nil
  where
    -- Note that `go` returns a function!
    go (Leaf x)     = Cons x
    go (Branch l r) = go l . go r

Typeclasses

• Used for many of the Prelude operators and numeric literals
• Ad hoc polymorphism (overloading)
• Many built-in typeclasses can be automatically derived (Eq, Ord, Enum, Bounded, Show, and Read)!

{-# LANGUAGE OverloadedStrings #-}
module SJSON where
import Prelude hiding (concat)
import Data.Text (Text, concat)
import Data.Attoparsec.Text
import Control.Applicative

data JSON = JArray [JSON]
          | JObject [(Text, JSON)]
          | JText Text
          deriving (Show)

pJSON :: Parser JSON
pJSON = choice [ pText, pObject, pArray ]
  where
    pString = concat <$> "\"" .*> many pStringChunk <*. "\""
    pStringChunk = choice [ "\\\"" .*> pure "\""
                          , takeWhile1 (not . (`elem` "\\\""))
                          , "\\" ]
    pText = JText <$> pString
    pPair = (,) <$> pString <*. ":" <*> pJSON
    pObject = JObject <$> "{" .*> (pPair `sepBy` ",") <*. "}"
    pArray = JArray <$> "[" .*> (pJSON `sepBy` ",") <*. "]"

-- FlipImage.hs
import System.Environment
import Data.Word
import Data.Array.Repa hiding ((++))
import Data.Array.Repa.IO.DevIL
import Data.Array.Repa.Repr.ForeignPtr

main :: IO () 
main = do
  [f] <- getArgs
  (RGB v) <- runIL $ readImage f
  rotated <- (computeP $ rot180 v) :: IO (Array F DIM3 Word8)
  runIL $ writeImage ("flip-"++f) (RGB rotated)

rot180 :: (Source r e) => Array r DIM3 e -> Array D DIM3 e
rot180 g = backpermute e flop g
  where
    e@(Z :. x :. y :. _) = extent g
    flop (Z :. i         :. j         :. k) =
         (Z :. x - i - 1 :. y - j - 1 :. k)

Concurrency

RAM footprint per unit of concurrency (approx)

import Control.Concurrent
import Network.HTTP

getHTTP :: String -> IO String
getHTTP url = simpleHTTP (getRequest url) >>= getResponseBody

urls :: [String]
urls = map ("http://ifconfig.me/"++) ["ip", "host"]

startRequest :: String -> IO (MVar ())
startRequest url = do
  v <- newEmptyMVar
  forkIO (getHTTP url >>= putStr >> putMVar v ())
  return v

main :: IO ()
main = do
  mvars <- mapM startRequest urls
  mapM_ takeMVar mvars

Notable Libraries

Web Frameworks

Snap

HTTP + Templates. Extensible with "Snaplets"

Yesod

Full stack, uses Template Haskell

Happstack

Full stack, does not rely on Template Haskell (happstack-lite)

scotty

Like Ruby Sinatra, great for simple REST apps

Dev Tools

HLint

Suggests improvements for your code

ghc-mod, hdevtools

Editor integration

Hoogle, Hayoo

Search for Haskell functions by name or by type!

Djinn

Automatically generate code given a type!

tidal

DSL for live coding music patterns ("algorave")