slides.md

{#title}

Intro to Haskell
for Erlangers

Bob Ippolito (@etrepum)
Erlang Factory SF
March 7, 2014

[bob.ippoli.to/haskell-for-erlangers-2014]

Who am I?

• Not classically trained in CS
• Erlang user since 2006 (Mochi Media, mochiweb, etc.)
• Haskell user since 2012 (ported exercism.io curriculum)
• Currently teaching web technologies to teenagers with Mission Bit
• Doing a bit of advising/investing in startups

Why learn Haskell?

• I learn a lot of from studying new languages
• Types are supposed to help you write better software
• I like QuickCheck and Dialyzer
• Good support for parallelism and concurrency
• Will help me understand more CS papers

{#cost-of-concurrency}

RAM footprint per unit of concurrency (approx)

1.3KB	Haskell ThreadId + MVar (GHC 7.6.3, 64-bit)
2.6 KB	Erlang process (64-bit)
8.0 KB	Go goroutine
64.0 KB	Java thread stack (minimum)
64.0 KB	C pthread stack (minimum)
1 MB	Java thread stack (default)
8 MB	C pthread stack (default, 64-bit Mac OS X)

Starting out

• Intimidated by Haskell for years
• Took a class while at Facebook
• Read several books
• Deliberate practice

Haskell's Appeal

• Abstractions can often be used without penalty
• Efficient parallel and concurrent programming
• Type system makes maintenance easier
• Nice syntax (not too heavy or lightweight)
• Fantastic community & ecosystem

Haskell {#haskell-history}

**Haskell** B. Curry

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)

{#ifip-1992}

IFIP 1992 Working Group

{#ifip-1992-erl}

John Hughes (QuickCheck), Philip Wadler (Subtyping for Erlang)

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) 2010 ~ Haskell 2010 (300 pages)

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

Internet ~ Facebook - Haxl rule engine "fighting spam with pure functions" 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"

Commercial Services

janrain ~ User management platform. Spaceport (Facebook, Aug 2013) ~ Mobile game framework using ActionScript 3 scrive ~ E-signing service (nordic market) OpenBrain ~ Computing platform for scientific and business analytics skedge.me ~ Enterprise appointment scheduling

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

Haskell Platform

Haskell: Batteries Included

• http://www.haskell.org/platform
• GHC compiler and GHCi interpreter
• Robust and stable set of vetted packages
• Cabal; easily fetch more packages from Hackage

Editor Support

Emacs ~ ghc-mod + HLint Vim ~ hdevtools + Syntastic + vim-hdevtools Sublime Text ~ hdevtools + SublimeHaskell Eclipse ~ EclipseFP + HLint Web ~ FP Haskell Center

Haskell Syntax

Types ~ Defines types and typeclasses ~ Constructors and record accessors become values

Values ~ Named bindings ~ Instances of constructors ~ Functions ~ Control flow

Relative to Erlang

• Syntax is minimal & familiar
• Haskell's pattern matching is not as clever as Erlang's
• Types are kinda like having Dialyzer for every compile
  (although Dialyzer is really quite different!)
• Typeclasses are nice, Erlang doesn't have them
• Erlang is probably (much) better for long-running systems

lists:map/2 {.big-code}

map(F, [H|T]) ->
    [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].

map {.big-code}

map _ []     = []
map f (x:xs) = f x : map f xs

lists:map/2 (typed) {.big-code}

-spec map(Fun, List1) -> List2 when
      Fun :: fun((A) -> B),
      List1 :: [A],
      List2 :: [B],
      A :: term(),
      B :: term().

map(F, [H|T]) ->
    [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].

map (typed) {.big-code}

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

lists:foldr/3 {.big-code}

-spec foldr(Fun, Acc0, List) -> Acc1 when
      Fun :: fun((Elem :: T, AccIn) -> AccOut),
      Acc0 :: term(),
      Acc1 :: term(),
      AccIn :: term(),
      AccOut :: term(),
      List :: [T],
      T :: term().

foldr(F, Accu, [Hd|Tail]) ->
    F(Hd, foldr(F, Accu, Tail));
foldr(F, Accu, []) when is_function(F, 2) -> Accu.

foldr {.big-code}

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
   where
     go []     = z
     go (y:ys) = y `k` go ys

Sum Type {.small-title .big-code}

%% sum type, 3 possible values
-type choice() :: definitely
                | possibly
                | no_way.

Sum Type {.small-title .big-code}

-- sum type, 3 possible values
data Choice = Definitely
            | Possibly
            | NoWay

Product Type {.small-title .big-code}

%% product type, 9 possible values (3 * 3)
-type choices() :: {choice(), choice()}.

Product Type {.small-title .big-code}

-- product type, 9 possible values (3 * 3)
data Choices = Choices Choice Choice

-- as a tuple with a type alias
-- NOT THE SAME AS ABOVE! :)
type Choices = (Choice, Choice)

Product Type (Record) {.small-title .big-code}

%% record syntax
-record(choices,
        fst_choice :: choice(),
        snd_choice :: choice()).

%% getters need to be implemented manually
-spec fst_choice(#choices{}) -> choice().
fst_choice(#choices{fst_choices=X}) -> X.

-spec snd_choice(#choices{}) -> choice().
snd_choice(#choices{snd_choices=X}) -> X.

Product Type (Record) {.small-title .big-code}

-- record syntax defines accessors automatically
data Choices =
  Choices { fstChoice :: Choice
          , sndChoice :: Choice
          }

-- these getters are automatically defined
fstChoice :: Choices -> Choice
fstChoice (Choices { fstChoice = x }) = x

sndChoice :: Choices -> Choice
sndChoice (Choices { sndChoice = x }) = x

Abstract Data Type {.small-title .big-code}

%% abstract data type for a list
-type cons(A) :: nil
               | {cons, A, cons(A)}.

Abstract Data Type {.small-title .big-code}

-- abstract data type for a list
data List a = Nil
            | Cons a (List a)

{#types-and-constructors-1 .small-title .big-code .highlight-type}

Types and Constructors

data Choice = Definitely
            | Possibly
            | NoWay

data Choices = Choices Choice Choice

mkChoices :: Choice -> Choice -> Choices
mkChoices a b = Choices a b

fstChoice :: Choices -> Choice
fstChoice (Choices a _) = a

{#types-and-constructors-2 .small-title .big-code .highlight-constructor}

Types and Constructors

data Choice = Definitely
            | Possibly
            | NoWay

data Choices = Choices Choice Choice

mkChoices :: Choice -> Choice -> Choices
mkChoices a b = Choices a b

fstChoice :: Choices -> Choice
fstChoice (Choices a _) = a

Using Types {.big-code}

-- Values can be annotated in-line
2 ^ (1 :: Int)

-- Bindings can be annotated
success :: a -> Maybe a
-- Constructors are values
-- (and product constructors are functions)
success x = Just x

-- Constructors can be pattern matched
-- _ is a wildcard
case success True of
  Just True -> ()
  _         -> ()

Pattern Matching {.big-code}

-spec is_just({just, A} | nothing) -> boolean().
is_just({just, _}) ->
    true;
is_just(nothing) ->
    false.

Pattern Matching {.big-code}

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust Nothing  = False

Pattern Matching {.big-code}

Erlang's pattern matching allows non-linear patterns.

-spec is_equal(A, A) -> boolean() when
      A :: term().
is_equal(A, A) -> true;
is_equal(_, _) -> false.

Pattern Matching {.big-code}

Haskell's... does not.

isEqual :: a -> a -> Bool
isEqual a b = undefined

This isn't even possible! Only constructors can be pattern matched. Types have no built-in equality.

`Infix` and (Prefix) {.big-code}

%% Symbolic operators can be used
%% as functions from the erlang module
erlang:'+'(A, B).

Erlang doesn't have user-defined infix operators

`Infix` and (Prefix) {.big-code}

-- Symbolic operators can be used
-- prefix when in (parentheses)
(+) a b

-- Named functions can be used
-- infix when in `backticks`
x `elem` xs

-- infixl, infixr define associativity
-- and precedence (0 lowest, 9 highest)
infixr 5 `append`
a `append` b = a ++ b

Functions & Lambdas {.big-code}

-spec add(integer(), integer()) -> integer().
add(X, Acc) ->
    X + Acc.

-spec sum_fun([integer()]) -> integer().
sum_fun(Xs) ->
    lists:foldl(fun add/2, 0, Xs).

-spec sum_lambda([integer()]) -> integer().
sum_lambda(Xs) ->
    lists:foldl(
        fun (X, Acc) -> X + Acc end,
        0,
        Xs).

Functions & Lambdas {.big-code}

add :: Integer -> Integer -> Integer
add acc x = acc + x

sumFun :: [Integer] -> Integer
sumFun xs = foldl add 0 xs

sumLambda :: [Integer] -> Integer
sumLambda xs = foldl (\acc x -> acc + x) 0 xs

Functions & Lambdas {.big-code}

• Haskell only has functions of one argument
• a -> b -> c is really a -> (b -> c)
• f a b is really (f a) b
• Let's leverage that…

Functions & Lambdas {.big-code .highlight}

add :: Integer -> Integer -> Integer
add acc x = acc + x

sumFun :: [Integer] -> Integer
sumFun xs = foldl add 0 xs

sumLambda :: [Integer] -> Integer
sumLambda xs = foldl (\acc x -> acc + x) 0 xs

Functions & Lambdas {.big-code .highlight}

add :: Integer -> Integer -> Integer
add acc x = acc + x

sumFun :: [Integer] -> Integer
sumFun = foldl add 0

sumLambda :: [Integer] -> Integer
sumLambda = foldl (\acc x -> acc + x) 0

Functions & Lambdas {.big-code .highlight}

add :: Integer -> Integer -> Integer
add acc x = (+) acc x

sumFun :: [Integer] -> Integer
sumFun = foldl add 0

sumLambda :: [Integer] -> Integer
sumLambda = foldl (\acc x -> (+) acc x) 0

Functions & Lambdas {.big-code .highlight}

add :: Integer -> Integer -> Integer
add acc = (+) acc

sumFun :: [Integer] -> Integer
sumFun = foldl add 0

sumLambda :: [Integer] -> Integer
sumLambda = foldl (\acc -> (+) acc) 0

Functions & Lambdas {.big-code .highlight}

add :: Integer -> Integer -> Integer
add = (+)

sumFun :: [Integer] -> Integer
sumFun = foldl add 0

sumLambda :: [Integer] -> Integer
sumLambda = foldl (+) 0

Guards {.big-code}

-spec is_negative(number()) -> boolean().
is_negative(X) when X < 0 ->
  true;
is_negative(_) ->
  false.

Guards {.big-code}

isNegative :: (Num a) => a -> Bool
isNegative x
  | x < 0     = True
  | otherwise = False

Guards {.big-code}

isNegative :: (Num a) => a -> Bool
isNegative x
  | x < 0     = True
  | otherwise = False

absoluteValue :: (Num a) => a -> Bool
absoluteValue x
  | isNegative x = -x
  | otherwise    = x

Built-in types {.big-code .small-title}

-- (), pronounced "unit"
unit :: ()
unit = ()

-- Char
someChar :: Char
someChar = 'x'

-- Instances of Num typeclass
someDouble :: Double
someDouble = 1

-- Instances of Fractional typeclass
someRatio :: Rational
someRatio = 1.2345

Lists & Tuples {.big-code .small-title}

some_list() ->
    [1, 2, 3].

some_other_list() ->
    [4 | [5 | [6 | []]]].

some_tuple() ->
    {10, $4}.

some_string() ->
    "foo".

Lists & Tuples {.big-code .small-title}

-- [a], type can be written prefix as `[] a`
someList, someOtherList :: [Int]
someList = [1, 2, 3]
someOtherList = 4 : 5 : 6 : []
dontWriteThis = (:) 4 (5 : (:) 6 [])

-- (a, b), can be written prefix as `(,) a b`
someTuple, someOtherTuple :: (Int, Char)
someTuple = (10, '4')
someOtherTuple = (,) 4 '2'

-- [Char], also known as String
-- (also see the OverloadedStrings extension)
someString :: String
someString = "foo"

Typeclass Syntax {.big-code}

• Erlang doesn't have typeclasses.

• Elixir has Protocols, which are closer, but they are also not typeclasses.

Typeclass Syntax {.big-code}

class Equals a where
  isEqual :: a -> a -> Bool

instance Equals Choice where
  isEqual Definitely Definitely = True
  isEqual Possibly   Possibly   = True
  isEqual NoWay      NoWay      = True
  isEqual _          _          = False

instance (Equals a) => Equals [a] where
  isEqual (a:as) (b:bs) = isEqual a b &&
                          isEqual as bs
  isEqual as     bs     = null as && null bs

Typeclass Syntax {.big-code}

{-
class Eq a where
  (==) :: a -> a -> Bool
-}

instance Eq Choice where
  Definitely == Definitely = True
  Possibly   == Possibly   = True
  NoWay      == NoWay      = True
  _          == _          = False

Typeclass Syntax {.big-code}

data Choice = Definitely
            | Possibly
            | NoWay
            deriving (Eq)

Typeclass Syntax {.big-code}

data Choice = Definitely
            | Possibly
            | NoWay
            deriving ( Eq, Ord, Enum, Bounded
                     , Show, Read )

QuickCheck {.big-code}

prop_itsthere() ->
    ?FORALL(I,int(),
        [I] == queue:to_list(
            queue:cons(I,
                queue:new()))).

QuickCheck {.big-code}

import Data.Sequence ((|>), empty)
import Data.Foldable (toList)

prop_itsthere :: Int -> Bool
prop_itsthere i = [i] == toList (empty |> i)

QuickCheck {.big-code}

$ ghci

λ> import Test.QuickCheck
λ> import Data.Foldable
λ> import Data.Sequence
λ> quickCheck (\i -> [i :: Int] ==
                       toList (empty |> i))
+++ OK, passed 100 tests.

Do syntax {.big-code .highlight}

-spec main([string()]) -> ok.
main(_Args) ->
  {ok, Secret} = file:read_file("/etc/passwd"),
  file:write_file("/tmp/passwd", Secret),
  ok.

Do syntax (IO) {.big-code}

main :: IO ()
main = do
  secret <- readFile "/etc/passwd"
  writeFile "/tmp/passwd" secret
  return ()

Do syntax {.big-code}

do m
-- desugars to:
m

do a <- m
   return a
-- desugars to:
m >>= \a -> return a

do m
   return ()
-- desugars to:
m >> return ()

Do syntax (IO) {.big-code .highlight}

main :: IO ()
main = do
  secret <- readFile "/etc/passwd"
  writeFile "/tmp/passwd" secret
  return ()

Do syntax (IO) {.big-code .highlight}

main :: IO ()
main =
  readFile "/etc/passwd" >>= \secret -> do
  writeFile "/tmp/passwd" secret
  return ()

Do syntax (IO) {.big-code .highlight}

main :: IO ()
main =
  readFile "/etc/passwd" >>= \secret ->
  writeFile "/tmp/passwd" secret >>
  return ()

Do syntax (IO) {.big-code .highlight}

main :: IO ()
main =
  readFile "/etc/passwd" >>= \secret ->
  writeFile "/tmp/passwd" secret

Do syntax (IO) {.big-code .highlight}

main :: IO ()
main =
  readFile "/etc/passwd" >>=
  writeFile "/tmp/passwd"

Do syntax ([a]) {.big-code}

-spec flat_map(fun((A) -> [B]), [A]) -> [B] when
  A :: term(),
  B :: term().
flat_map(F, Xs) -> [ Y || X <- Xs, Y <- F(X) ].

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = [ y | x <- xs, y <- f x ]

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = do
  x <- xs
  y <- f x
  return y

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = do
  x <- xs
  f x

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = xs >>= \x -> f x

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = xs >>= f

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap f xs = flip (>>=) f xs

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap = flip (>>=)

Do syntax ([a]) {.big-code}

flatMap :: (a -> [b]) -> [a] -> [b]
flatMap = (=<<)

Key Features

• Interactive
• Pure
• Non-strict (lazy) evaluation
• Types and typeclasses
• Abstractions
• Multi-paradigm

GHCi

Interactive Haskell

{#runhaskell}

$ runhaskell --help
Usage: runghc [runghc flags] [GHC flags] module [program args]

The runghc flags are
    -f /path/to/ghc       Tell runghc where GHC is
    --help                Print this usage information
    --version             Print version number

{#ghci-start}

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
h> 

{#ghci-t .big-code}

`:t` shows type information

```haskell

h> :t map map :: (a -> b) -> [a] -> [b] h> :t map (+1) map (+1) :: Num b => [b] -> [b] h> :t (>>=) (>>=) :: Monad m => m a -> (a -> m b) -> m b

# {#ghci-i-typeclass .big-code}

<h2>`:i` shows typeclass info</h2>
```haskell

h> :i Num
class Num a where
  (+) :: a -> a -> a
  (*) :: a -> a -> a
  (-) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
    -- Defined in `GHC.Num'
instance Num Integer -- Defined in `GHC.Num'
instance Num Int -- Defined in `GHC.Num'
instance Num Float -- Defined in `GHC.Float'
instance Num Double -- Defined in `GHC.Float'

{#ghci-i-value .big-code}

`:i` shows value info

```haskell

h> :info map map :: (a -> b) -> [a] -> [b]
-- Defined in GHC.Base' h> :info (>>=) class Monad m where (>>=) :: m a -> (a -> m b) -> m b ... -- Defined in GHC.Base' infixl 1 >>=

# {#ghci-i-type .big-code}

<h2>`:i` shows type info</h2>
```haskell

h> :info Int
data Int = ghc-prim:GHC.Types.I#
  ghc-prim:GHC.Prim.Int#
  -- Defined in `ghc-prim:GHC.Types'
instance Bounded Int -- Defined in `GHC.Enum'
instance Enum Int -- Defined in `GHC.Enum'
instance Eq Int -- Defined in `GHC.Classes'
instance Integral Int -- Defined in `GHC.Real'
instance Num Int -- Defined in `GHC.Num'
instance Ord Int -- Defined in `GHC.Classes'
instance Read Int -- Defined in `GHC.Read'
instance Real Int -- Defined in `GHC.Real'
instance Show Int -- Defined in `GHC.Show'

{#ghci-load-reload .big-code}

`:l` load a module

`:r` to reload

```haskell

h> :! echo 'hello = print "hello"' > Hello.hs h> :l Hello [1 of 1] Compiling Main ( Hello.hs, interpreted ) Ok, modules loaded: Main. h> hello "hello" h> :! echo 'hello = print "HELLO"' > Hello.hs h> :r [1 of 1] Compiling Main ( Hello.hs, interpreted ) Ok, modules loaded: Main. h> hello "HELLO"

# {#side-effects .big-code}

```haskell

-- WordCount1.hs

main :: IO ()
main = do
  input <- getContents
  let wordCount = length (words input)
  print wordCount

{#side-effects-2 .big-code}

-- WordCount2.hs

main :: IO ()
main =
  getContents >>= \input ->
    let wordCount = length (words input)
    in print wordCount

{#side-effects-3 .big-code}

-- WordCount3.hs

main :: IO ()
main = getContents >>= print . length . words

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

Common combinators {.big-code}

-- Function composition
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

-- Function application (with a lower precedence)
($) :: (a -> b) -> a -> b
f $ x =  f x

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

{#compiler}

GHC compilation phases Parse Rename Typecheck Desugar Core Optimize Code gen LLVM

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!

{#ghc-rules-ex .big-code}

{-# RULES
"ByteString specialise break (x==)" forall x.
    break ((==) x) = breakByte x
"ByteString specialise break (==x)" forall x.
    break (==x) = breakByte x
  #-}

GHC RULES {.big-code}

{-# RULES
"ByteString specialise break (x==)" forall x.
    break ((==) x) = breakByte x
"ByteString specialise break (==x)" forall x.
    break (==x) = breakByte x
  #-}

import Data.ByteString.Char8 (ByteString, break)

splitLine :: ByteString -> (ByteString, ByteString)
splitLine = break (=='\n')

GHC RULES {.big-code}

{-# RULES
"ByteString specialise break (x==)" forall x.
    break ((==) x) = breakByte x
"ByteString specialise break (==x)" forall x.
    break (==x) = breakByte x
  #-}

import Data.ByteString.Char8 (ByteString, break)

splitLine :: ByteString -> (ByteString, ByteString)
splitLine = breakByte '\n'

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)

{#lazy-ramsey}

Call by need

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

Non-Strict Evaluation {.big-code}

-- [1..] is an infinite list, [1, 2, 3, ...]
print (head (map (*2) [1..]))

Non-Strict Evaluation {.big-code .highlight}

-- [1..] is an infinite list, [1, 2, 3, ...]
print (head (map (*2) [1..]))
-- Outside in, print x = putStrLn (show x)
putStrLn (show (head (map (*2) [1..]))

Non-Strict Evaluation {.big-code .highlight}

-- Outside in, print x = putStrLn (show x)
putStrLn (show (head (map (*2) [1..]))
-- head (x:_) = x
-- map f (x:xs) = f x : map f xs
-- desugar [1..] syntax
putStrLn (show (head (map (*2) (enumFrom 1))))

Non-Strict Evaluation {.big-code .highlight}

-- desugar [1..] syntax
putStrLn (show (head (map (*2) (enumFrom 1))))
-- enumFrom n = n : enumFrom (succ n)
putStrLn (show (head (map (*2)
                          (1 : enumFrom (succ 1)))))

Non-Strict Evaluation {.big-code .highlight}

-- enumFrom n = n : enumFrom (succ n)
putStrLn (show (head (map (*2)
                          (1 : enumFrom (succ 1)))))
-- apply map
putStrLn (show (head
                  ((1*2) :
                   map (*2) (enumFrom (succ 1)))))

Non-Strict Evaluation {.big-code .highlight}

-- apply map
putStrLn (show (head ((1*2) : …)))
-- apply head
putStrLn (show (1*2))

Non-Strict Evaluation {.big-code .highlight}

-- apply head
putStrLn (show (1*2))
-- show pattern matches on its argument
putStrLn (show 2)

Non-Strict Evaluation {.big-code .highlight}

-- show pattern matches on its argument
putStrLn (show 2)
-- apply show
putStrLn "2"

{#control-flow .big-code}

if' :: Bool -> a -> a -> a
if' cond a b = case cond of
  True  -> a
  False -> b

(&&) :: Bool -> Bool -> Bool
a && b = case a of
  True  -> b
  False -> False

const :: a -> b -> a
const x = \_ -> x

{#infinite-programming .big-code}

fib :: [Integer]
fib = 0 : 1 : zipWith (+) fib (tail fib)

cycle :: [a] -> [a]
cycle xs = xs ++ cycle xs

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs)
  | p x       = x : takeWhile p xs
  | otherwise = []

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)

{#constraints}

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)

{#bottoms}

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}

-- 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)!

{#typeclass-example .big-code}

module List where

data List a = Cons a (List a)
            | Nil

instance (Eq a) => Eq (List a) where
  (Cons a as) == (Cons b bs) = a == b && as == bs
  Nil         == Nil         = True
  _           == _           = False

instance Functor List where
  fmap _ Nil         = Nil
  fmap f (Cons x xs) = Cons (f x) (fmap f xs)

{#typeclass-example-2 .big-code}

{-# LANGUAGE DeriveFunctor #-}

module List where

data List a = Cons a (List a)
            | Nil
            deriving (Eq, Functor)

{#newtype .big-code}

import Data.List (sort)

newtype Down a = Down { unDown :: a }
                 deriving (Eq)

instance (Ord a) => Ord (Down a) where
  compare (Down a) (Down b) = case compare a b of
    LT -> GT
    EQ -> EQ
    GT -> LT

reverseSort :: Ord a => [a] -> [a]
reverseSort = map unDown . sort . map Down

Abstractions

Monoid ~ Has an identity and an associative operation Functor ~ Anything that can be mapped over (preserving structure) Applicative ~ Functor, but can apply function from inside Monad ~ Applicative, but can return any structure

Monoid

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a

instance Monoid [a] where
  mempty = []
  mappend = (++)

infixr 6 <>
(<>) :: (Monoid a) => a -> a -> a
(<>) = mappend

Functor

class Functor f where
  fmap :: (a -> b) -> f a -> f b

instance Functor [] where
  fmap = map

instance Functor Maybe where
  fmap f (Just x) = Just (f x)
  fmap _ Nothing  = Nothing

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Applicative

class (Functor f) => Applicative f where
  pure :: a -> f a
  infixl 4 <*>
  (<*>) :: f (a -> b) -> f a -> f b

instance Applicative [] where
  pure x = [x]
  fs <*> xs = concatMap (\f -> map f xs) fs

instance Applicative Maybe where
  pure = Just
  Just f <*> Just x = Just (f x)
  _      <*> _      = Nothing

Monad

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b
  (>>)  :: m a -> m b -> m b
  ma >> mb = ma >>= \_ -> mb

instance Monad [] where
  return = pure
  m >>= f = concatMap f m

instance Monad Maybe where
  return = pure
  Just x  >>= f = f x
  Nothing >>= _ = Nothing

Parser Combinators

{#parsing}

{-# 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` ",") <*. "]"

Foreign Function Interface

{#ffi .big-code}

{-# LANGUAGE ForeignFunctionInterface #-}

import Foreign.C.Types
import Control.Monad

foreign import ccall unsafe "stdlib.h rand"
     c_rand :: IO CUInt

main :: IO ()
main = replicateM_ 20 (c_rand >>= print)

Parallel Programming

{#parallel-flip-image}

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

{#concurrent-http}

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

Why not Haskell?

• Lots of new terminology
• Mutable state takes more effort
• Laziness changes how you need to reason about code
• Once you get used to it, these aren't problematic

{#terminology}

A monad is just a monoid in the category of endofunctors, what's the problem?

Terminology from category theory can be intimidating (at first)!

return probably doesn't mean what you think it means.

{#laziness-behavior-1 .big-code}

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

{#laziness-behavior-2 .big-code}

sum :: Num [a] => [a] -> a
sum = go 0
  where
    go acc (x:xs) = go (acc + x) (go xs)
    go acc []     = acc

{#laziness-behavior-3 .big-code}

sum :: Num [a] => [a] -> a
sum = go 0
  where
    go acc _
      | seq acc False = undefined
    go acc (x:xs)     = go (acc + x) (go xs)
    go acc []         = acc

{#laziness-behavior-4 .big-code}

{-# LANGUAGE BangPatterns #-}

sum :: Num [a] => [a] -> a
sum = go 0
  where
    go !acc (x:xs) = go (acc + x) (go xs)
    go  acc []     = acc

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

Publishing and docs

Haddock ~ Standard library documentation tool for Haskell projects diagrams ~ DSL for vector graphics hakyll ~ Static site generator Pandoc ~ Markup format swiss-army knife (Markdown, LaTeX, EPUB, …)

Parser Combinators

Parsec ~ Industrial strength, monadic parser combinator library for Haskell attoparsec ~ Like Parsec, but makes a few trade-offs for performance

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")

Parallel / Distributed

repa ~ High performance, regular, multi-dimensional arrays (with multi-core!) accelerate ~ Like repa, but can utilize CUDA to run on GPUs Cloud Haskell ~ Erlang-like concurrency and distribution for Haskell

Testing & Profiling

QuickCheck ~ Property based testing HUnit ~ Standard unit testing framework hpc ~ Haskell Program Coverage ThreadScope ~ Visualize multi-core utilization criterion ~ Gold standard for performance benchmarking EKG ~ Embeds a web-server for live monitoring of metrics

Learn More

Books ~ Learn You a Haskell for Great Good ~ Parallel and Concurrent Programming in Haskell ~ Real World Haskell Lectures ~ Functional Systems in Haskell - CS240h Autumn 2011, Stanford ~ Introduction to Haskell - CS1501 Spring 2013, UVA ~ Introduction to Haskell - CIS 194 Spring 2013, UPenn ~ Haskell Track - CS 11 Fall 2011, Caltech Practice ~ exercism.io, Talentbuddy, HackerRank ~ H-99, Project Euler

Thanks!

+-------------+-------------------------------------------------+ | Slides | bob.ippoli.to/haskell-for-erlangers-2014 | +-------------+-------------------------------------------------+ | Source | github.com/etrepum/haskell-for-erlangers-2014 | +-------------+-------------------------------------------------+ | Email | [email protected] | +-------------+-------------------------------------------------+ | Twitter | @etrepum | +-------------+-------------------------------------------------+