Haskell from scratch

About me

• started using Haskell a few years ago
• writing in Haskell at least several times a week
• still sometimes puzzled by Category Theory

Sarunas Valaskevicius @ Inviqa

What to expect

• an overview of the language
• basic haskell syntax
• basic functional programming patterns

Functional programming

What is it?

• a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data. [Wikipedia]
• It is a declarative programming paradigm, which means programming is done with expressions
• function as first class citizen
• breaks data encapsulation as perceived in OO, aims to decouple behaviour for better reusability
  • data can still be bound by currying or closures

• focuses on behaviour
• declare the functional relation, rather than "tell computer how to do stuff"
• can functions pass around, call from another context, even return them

You've used functional elements already

• map, reduce;
• closures;
• promise pattern in javascript..

About haskell

Generic programming language

• desktop applications
• server side software
• known to be especially good at DSLs

Many examples for desktop include: - xmonad - the famous window manager - pandoc - document converter

Purity and referential transparency

• function with no side effects is pure
• this property is called referential transparency
• it allows equational reasoning:

y = f x
g = h y y

g = h (f x) (f x)

"No side effects"

• all data is passed immutably
• a function with same parameters will always return the same result
• reduces the risk of bugs - all changes to data are explicit

Laziness

• most programming languages use eager evaluation
• but some start to implement lazy generators
• haskell is lazy: it will only compute a value when its actually used
• problematic in microcontroller space
• very convenient in generic programming - allows infinite computation definitions:

printN n =  putStrLn . (intercalate " ") . (map show) . (take n)

print10 = printN 10

print10 [1..]

... or even

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Space leaks

Laziness can be bad too - and space leaks are the effects we want to avoid.

It is possible to specify strict computation when required.

stricter :: Integer -> Integer -> Integer
stricter a b = id $! a + b

Strong typing

• algebraic data types
• uses Hindley-Milner type inference

• "If it type-checks, it's most likely good"

  countSame :: Eq a => a -> [a] -> Int

  • a is a variable type
  • we only require to be able to compare two variables of type a
  • we only can compare the variables of type a
  • the same type a has to be passed to the 1st and 2nd params

Pattern matching

• powerful alternative for many if statements
• functions are written in declarative manner

• destructuring matches

  maybePlus :: Int -> Maybe Int -> Maybe Int
  maybePlus a (Just t) = Just $ t + a
  maybePlus _ Nothing = Nothing

Curried functions

• all functions return either the end result or function to get it:

  f :: a -> b -> c

• f 3 has type (b -> c), which is a function itself.

Asynchronous

• GHC uses green threads (implemented in the VM)
  • events based execution - doesn't block the process
  • all that is abstracted underneath the language
• green threads can be executed by any amount of OS threads, specified at compile time

Modules

• export closely related functions
• hide private implementation

• directory path is mapped to the module name

  Data.List

Ecosystem

Compiler choices

• ghc is the current preference, has multiple backends (native, llvm, c)
• jhc performs whole program optimisation (not maintained)
• ...

ghci (repl)

• check quickly before coding

Packaging

• cabal - dependency manager and more
• hackage - repository for haskell packages
• hoogle - function search engine
• hayoo - another search engine

TDD tools

• quickcheck - randomised testing framework for predefined properties
• hspec - tdd support tool

Hlint

• detects code duplication
• detects point free improvements
• many more checks

Generic language constructs

Defining data types

data MyType = MyIntType Int | MyEmptyType | MyStringType String

Defines a new type MyType and provides three data constructors.

Type alias

type Deck = [Card]

Defines a type alias. The data can still be accessed using the original type.

Newtype

newtype Deck = Deck [Card]

A combination of data and type - the usage of the resulting type is that of a data type, however the runtime is of a type alias.

Function declaration

myFunction :: Type
myFunction arguments = body

Defines a new function available within the module.

Lambda functions

map (\x -> x+5) [1..]

\params -> body - defines a lambda function to use.

Pattern matching

fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Guards!

alg :: [Integer] -> Integer -> Integer
alg (x:x':xs) a
 | x == a = x' + alg xs x'
 | otherwise = alg (x':xs) x
alg [_] _ = 0
alg [] _ = 0

Allows computation in the matching.

Case .. of

alg :: [Integer] -> Integer -> Integer
alg (x:x':xs) a = case x == a of
                    True -> x' + alg xs x'
                    _ -> alg (x':xs) x')
alg [_] _ = 0
alg [] _ = 0

Pattern-matches in the code.

If

alg :: [Integer] -> Integer -> Integer
alg (x:x':xs) a = if x == a then x' + alg xs x'
                  else alg (x':xs) x'
alg [_] _ = 0
alg [] _ = 0

Let .. in

myFunction :: Int
myFunction = let x = 1
             in x + 1

Where

myFunction :: Int
myFunction = increasedX
    where x = 1
          increasedX = x + 1

Do notation

myFunction :: IO Int
myFunction = do
    other <- otherFunction
    return $ 1 + other

Let inside do

myFunction :: IO Int
myFunction = do
    let x = 1
    return x

Hello world

main :: IO()
main = putStrLn "hello world"

The "do" notation

worldType :: IO String
worldType = return "haskell"

main :: IO()
main = do
    whatWorld <- worldType
    putStrLn $ "hello " ++ whatWorld ++ " world"

Note: indentation matters.

Type system

What's a type class?

• similar to interfaces/abstract classes in OO
• can have default implementation

class  (Eq a) => Ord a  where
    compare              :: a -> a -> Ordering
    (<), (<=), (>), (>=) :: a -> a -> Bool
    max, min             :: a -> a -> a

    compare x y = if x == y then EQ
                  else if x <= y then LT
                  else GT

    x <  y = case compare x y of { LT -> True;  _ -> False }
    x <= y = case compare x y of { GT -> False; _ -> True }
    x >  y = case compare x y of { GT -> True;  _ -> False }
    x >= y = case compare x y of { LT -> False; _ -> True }

    max x y = if x <= y then y else x
    min x y = if x <= y then x else y

• choose which function to implement - compare or (<=)

Deriving a type class

data MyType = MyType Int deriving Eq

instance Ord MyType where
    (MyType a) <= (MyType b) = a <= b

(in this case, simply deriving (Eq, Ord) would also have worked)

Usage in functions

findLowerThan :: Ord a => a -> [a] -> [a]
findLowerThan measure = filter (< measure)

Elements of functional programming

Composing two functions

In haskell, it is possible to compose two functions to one using the (.) operator:

foo :: Int -> String
foo = show

bar :: String -> [String]
bar x = [x]

foobar = bar . foo

foobar 5  -- ["5"]

...it is not a language construct - like many others, it is a simple function, defined in the Prelude:

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

Monoids

class Monoid a where
        mempty  :: a
        -- ^ Identity of 'mappend'
        mappend :: a -> a -> a
        -- ^ An associative operation
        mconcat :: [a] -> a
        mconcat = foldr mappend mempty

Monoid laws

• Identity law
  • mappend mempty x = x
  • mappend x mempty = x
• Associative law
  • mappend x (mappend y z) = mappend (mappend x y) z

Monoid example

Sum 4 <> Sum 3 <> Sum 2 <> Sum 1
--    Sum{getSum = 10}

mconcat . (map Sum) $ [1..4]
--    Sum{getSum = 10}

mconcat . (map $ Just . Sum) $ [1..4]
--    Just (Sum{getSum = 10})

Just (Sum 10) <> Nothing <> Just (Sum 5)
--    Just (Sum{getSum = 15})

Higher order functions

Wikipedia: "In mathematics and computer science, a higher-order function is a function that does at least one of the following:

• takes one or more functions as an input
• outputs a function"

For example, map and fold (reduce) are very common in functional paradigm.

Boxes and computation context

data MyType a = MyType { usedValue :: a }

• a box, as an analogy, is a useful explanation of a parametrised type
• MyType is a box for any type a

myFunction :: f a -> f a

• f is a variable "box" where we don't specify its type
• the only property specified in the function definition is that the type has to have a type parameter

Functors

• functor allows mapping over them

• definition:

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

Functor laws

• identity:
  • fmap id = id
• composition:
  • fmap (p . q) = (fmap p) . (fmap q)

• f is the computation context
• fmap takes a function, and a value in the context
• then fmap applies the function to an unwrapped value
• and returns wrapped result

Example

numbers = [1..10]
strings = fmap show numbers
-- ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10"]

notSureIfNumber = Just 9
notSureIfString = fmap show notSureIfNumber
-- Just "9"

notSureIfNumber = Nothing
notSureIfString = fmap show notSureIfNumber
-- Nothing

Applicative functors

• applicative functor is a functor accepting wrapped functions

• it's definition:

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

• same as functor, however allows the function to be wrapped too!
• unwraps the function and the argument
• "unwrapping" means to execute the context rules, take the value
• applies the function
• wraps the result back

Applicative functor example

• apply a "boxed" function to a "boxed" value:

  Just (+1) <*> Just 1                 -- Just 2

• apply a binary function:

  Just (+) <*> Just 1 <*> Just 4       -- Just 5

  Just (+) <*> Just 1 <*> Nothing      -- Nothing

• a shorthand for fmap:

  (+) <$> Just 1 <*> Just 4            -- Just 5

Monads

class  Monad m  where
    return      :: a -> m a
    (>>=)       :: m a -> (a -> m b) -> m b
    (>>)        :: m a -> m b -> m b

    m >> k      = m >>= \_ -> k

• return - Inject a value into the monadic type.
• (>>=) - Sequentially compose two actions, passing any value produced by the first as an argument to the second.
• (>>) - Sequentially compose two actions, discarding any value produced by the first, like sequencing operators (such as the semicolon) in imperative languages.

Monad laws

• identity:
  • return a >>= k = k a
  • m >>= return = m
• associativity:
  • m >>= (\x -> k x >>= h) = (m >>= k) >>= h

Maybe monad

Just 1 >>= (\a -> return $ a+1)  -- or just "Just 1 >>= return . (+1)"
-- Just 2

The do notation is just syntactic sugar over >>=!

computation :: Maybe Int
computation = do
    a <- Just 1
    return $ a + 1

IO monad

echo :: IO ()
echo = getLine >>= putStrLn

Extras

lenses

monad transformers

extensible effects

free monads

category theory

Summary

You've seen

• overview of haskell ecosystem
• basic language constructs
• functional programming constructs

Where to next?

• code!
• learn you a haskell for great good
• real world haskell
• /r/haskell
• code more!

Thanks

Any questions?