The Fuck is Haskell?

A pure, lazy, functional programming language. Basically, it is something that happens when like-minded cool people come together.

Meaning of the above bullshit words?

Functional

â€˘

All hail functions. Children of the idea behind lambda calculus. Use functions just like any other sort of values.

â€˘

Evaluate not execute.

Pure

â€˘

Immutability is the key.

â€˘

Fuck all side-effects.

â€˘

Deterministic as fuck.

â€˘

Benefits: equational reasoning, parallelism, happiness

Lazy

â€˘

Infinity? ez.

â€˘

Compositional programming â€” you feel like Mozart.

â€˘

Disadvantage: Wot is time? Wot is space?

Haskell, the new cool guy in campus

Types

â€˘

Statically typed: run time errors $\rightarrow$ď»ż compile-time errors

â€˘

Expressive: the code is the documentation

â€˘

Expressive: brings clarity into coding

Abstraction

â€˘

Eat, Code, Sleep, Repeat: Haskell has polymorphism, higher-order functions and type classes â€” so fuck repetition.

â€˘

Think about the big picture and don't cry about some stupid exception.

What can I do with it?

â€˘

Program Correctness (QuickCheck)

â€˘

Fail safe programming (Cardano)

â€˘

High-load concurrent programming (web back-end)

Haskell: A Functional Programming Langauge

What does it mean for Haskell to be a functional programming language? Well, it means that Haskell follows the principle of functional programming â€” a programming paradigm where functions are the basic building blocks of computation.

Def: A function is a mapping that takes one or more arguments and produces a single result.

Properties of Haskell

â€˘

Consice programs

â€˘

Powerful type system

â€˘

List comprehension

â€˘

Recursive functions

â€˘

Higher-order functions

â€˘

Effectful functions

â€˘

Generic functions

â€˘

Lazy evaluation

â€˘

Equational reasoning

First Steps

Haskell comes with a large number of built-in functions, which are defined in a library file called the standard prelude.

â€˘

head <list>

â€˘

tail <list>

â€˘

take <num> <list>

â€˘

drop <num> <list>

â€˘

sum <list>

â€˘

reverse <list>

â€˘

product <list>

GHCi Command

Function Format

Just as in lambda calculus haskell follows a fixed pattern for functions. Here are some examples to elaborate:

â€˘

$f(x)$ď»ż as f x

â€˘

$f(x, y)$ď»ż as f x y

â€˘

$f(g(x))$ď»ż as f (g x)

â€˘

$f(x, g(y))$ď»ż as f x (g y)

â€˘

$f(x)g(y)$ď»ż as f x * g y

â€˘

Function application has the highest priority than all other operators.

â€˘

x `f` y is a syntactic sugar for f x y

Examples

-- Program 1
main = print (a ++ b ++ c)
a = [((2**3) * 4)]
b = [(2*3) + (4*5)]
c = [2 + (3 * (4**5))]
-- Program 2
main = print (n)
n = (a `div` (length xs))
where
a = 10
xs = [1 .. 5]
-- Program 3
main = print (a [1 .. 5])
a xs = sum (drop (length xs - 1) (take (length xs) xs))
main = putStrLn "hello, world"

Haskell

Types and class

Types

â€˘

They are a collection of related values.

â€˘

f :: A -> B and e :: A then, f e :: B

â€˘

Bool â€“ logical values

â€˘

Char â€“ single characters

â€˘

String â€“ strings of characters

â€˘

Int â€“ fixed-precision integers

â€˘

Integer â€“ arbitrary-precision integers

â€˘

Float â€“ single-precision floating-point numbers

â€˘

Double â€“ double-precision floating-point numbers

â€˘

[[â€™aâ€™,â€™bâ€™],[â€™câ€™,â€™dâ€™,â€™eâ€™]] :: [[Char]]

â€˘

List types â€” ["One","Two","Three"] :: [String]

â€˘

Tuple types â€” ("Yes",True,â€™aâ€™) :: (String,Bool,Char)

â€˘

Function types â€” not :: Bool -> Bool and add :: (Int,Int) -> Int

â€˘

Polymorphic types â€” length :: [a] -> Int and zip :: [a] -> [b] -> [(a, b)]

Classes

â€˘

They are collections of types that support certain overloaded operations called methods.

â€˘

Eq â€” (==) :: Eq a => a -> a -> Bool

â€˘

Ord â€” <, >, min, max with (<) :: Ord a => a -> a -> Bool

â€˘

Show â€” show :: a -> String

â€˘

Read â€” read :: String -> a

â€˘

Num â€” e.g., (+), (-), negate, abs, signum with (+) :: Num a => a -> a -> a

â€˘

Integral â€” div :: Int a => a -> a -> a and mod :: Int a => a -> a -> a, also Int and Integer types are instances of this class.

â€˘

Fractional â€” Float and Double are instances of this class. We also have methods such as / and recip.

Functions

Let us now introduce some really cool implementation techniques in haskell with respect to defining functions.

â€˘

Conditionals

-- Let's see an example
even :: a -> Bool
even n = (n `mod` 2 == 0)
-- Conditional using "if else"
signum n = if n > 0 then 1
else if n < 0 then -1
else 0
-- Conditional using "such that"
signum n | n > 0 = 1
| n < 0 = -1
| otherwise = 0

Haskell

â€˘

Pattern Matching

-- Define functions using '_'
len [] = 0
len (_:xs) = 1 + len xs
initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
where (f:_) = firstname (l:_) = lastname
-- Defining using '_' fundamentally
test :: Int -> Int
test 0 = 1
test 1 = 2
test _ = 0

Haskell

â€˘

Lambda Functions

\x -> x + 1

Haskell

-- For example,
add :: Int -> Int -> Int
add x y = x + y
-- and
odds n = map f [0 .. n - 1]
where
f x = x * 2 + 1
-- can be written as
add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)
-- and
odds n = map (\x -> x * 2 + 1) [0 .. n - 1]

Haskell

Currying Functions

Let $x = f(a, b, c)$ď»ż then, we shall have the following.

$f :: (\text{Type}(a),\ \text{Type}(b),\ \text{Type}(c)) \to \text{Type}(x)$

Upon currying, this gets translated to the below expression.

$f :: \text{Type}(a) \to (\text{Type}(b) \to (\text{Type}(c) \to (\text{Type}(x))))\\
\text{or, } f :: \text{Type}(a) \to \text{Type}(b) \to \text{Type}(c) \to \text{Type}(x)$

This is because, $x = f(a, b, c)$ď»ż becomes $h = g(a), i = h(b), x = i(c)$ď»ż or if called in sequence $x = g(a)(b)(c)$ď»ż.

fst :: (a, b) -> a
zip :: [a] -> [b] -> [(a, b)]
id :: a -> a
take :: Int -> [a] -> [a]
head :: [a] -> a

Haskell

Operator Sections

-- Operator Sections
w = 1 + 2
-- is same as
x = (+) 1 2
-- is same as
y = (1+) 2
-- or
z = (+2) 1

Haskell

This is very useful to construct certain functions.

List Comprehension

The idea is based on set construction from other sets.

xy = [(x, y) | x <- [1..3], y <- [x..3]]
-- The above is an example of dependent generators.
-- Definitions of x and y serve as generators.
-- Check out the usability of .. operator.
concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]
-- Guards are possible for example as bellow.
evens = [x | x <- [1..10], even x]

Haskell

Recursion

How to think recursively?

â€˘

Name the function

â€˘

Define its type

â€˘

Enumerate the cases

â€˘

Define the base cases

â€˘

List the "ingredients"

â€˘

Reason about the parameters

â€˘

Define the transition (non-trivial cases)

â€˘

Think about the result

Recursion

-- Example of a recursion
zip :: [a] -> [b] -> [(a, b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x, y) : zip xs ys
-- Append Definition
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Haskell

Memoization

The following memoize function takes a function of type Int -> a and returns a memoized version of the same function. The trick is to turn a function into a value because, in Haskell, functions are not memoized but values are.

import Data.Function (fix)
memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)
fib :: (Int -> Integer) -> Int -> Integer
fib f 0 = 0
fib f 1 = 1
fib f n = f (n - 1) + f (n - 2)
fibMemo :: Int -> Integer
fibMemo = fix (memoize . fib)

Haskell

Higher Order Function

A function is called a higher order if it takes a function as an argument or returns a function as a result.

twice :: (a -> a) -> a -> a
twice f x = f (f x)

Haskell

â€˘

Common programming idioms can be encoded as functions within the language itself.

â€˘

Domain specific languages can be defined as collections of higher order functions.

â€˘

Algebraic properties of higher-order functions can be used to reason about numbers.

-- Example
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]
-- Alternate
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

Haskell

-- Example
filter :: (a -> Bool) -> [a] -> [a]
filter f xs = [x | x <- xs, f x]
-- Alternatively
filter f [] = []
filter f (x:xs) | f x = x : filter f xs
| otherwise = filter f xs

Haskell

Foldr

A number of functions on lists can be defined using the following simple pattern of recursion.

f [] = v
f (x:xs) = x âŠ• f xs

Haskell

Here $f$ď»ż maps the empty list to some value $v$ď»ż and any non-empty list to some function $âŠ•$ď»ż applied to its head and $f$ď»ż of its tail.

The higher-order library function foldr (fold-right) encapsulates this simple pattern of recursion with the function ď»ż$âŠ•$ď»ż and the value $v$ď»ż as arguments.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

Haskell

-- Generic Examples
sum = foldr (+) 0
product = foldr (*) 1
or = foldr (||) False
and = foldr (&&) True
-- Other examples
length = foldr (\ _ n -> 1 + n) 0
reverse = foldr (\ x xs -> xs ++ [x]) []
(++ ys) = foldr (:) ys

Haskell

Composition

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
odd :: Int -> Bool
odd = not . even

Haskell

Other nice library functions

all :: (a -> Bool) -> [a] -> Bool
all f xs = and [f x | x <- xs]
any :: (a -> Bool) -> [a] -> Bool
any f xs = or [f x | x <- xs]
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile f [] = []
takeWhile f (x:xs) | f x = x : takeWhile f xs
| otherwise = []
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile f [] = []
dropWhile f (x:xs) | f x = dropWhile f xs
| otherwise = x:xs

Haskell

Moreover, curried functions are higher-order functions that returns a function.

Where and Let Clauses

-- Let
f = let x = 1; y = 2 in (x + y)
-- Where
f = x + y where x = 1; y = 1

Haskell

Type and Class Declaration

type Pos = (Int, Int)
type Trans = Pos -> Pos
type Tree = (Int, [Tree])

Haskell

A completely new type can be defined by specifying its values in context-free formulation.

data Bool = False | True

Haskell

data Answer = Yes | No | Unknown
answers :: [Answer]
answers = [Yes, No, Unknown]
flip :: Answer -> Answer
flip Yes = No
flip No = Yes
flip Unknown = Unknown

Haskell

Circle :: Float -> Shape
Rect :: Float -> Float -> Shape
data Shape = Circle Float | Rect Float Float
square :: Float -> Shape
square n = Rect n n
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y

Haskell

Maybe, Nothing, Just

data Maybe a = Nothing | Just a
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)

Haskell

This is basically a cool syntactic encapsulation to prevent crashing. This is used to often deal with exceptions and create failsafe programs.

Recursive Types

data Nat = Zero | Succ Nat
-- we have Zero :: Nat
-- and Succ :: Nat -> Nat

Haskell

data Expr = Val Int
| Add Expr Expr
| Mul Expr Expr
eval :: Expr -> Int
eval (Val n) = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y

Haskell

Interactive Programming

This is a problem because Haskell is designed to have no side effects and thus only to create batch programs.

Interactive programs, on the other hand, necessarily require side effects.

Solution

â€˘

We will use types to describe impure actions involving side effects (IO a).

â€˘

IO Char is the type of actions that return a character.

â€˘

IO () is the type of purely side effecting actions that return no result value.

The standard library provides a number of actions including the following three primitives.

-- reads character from the keyboard
-- and echoes it o the screen
-- returning the character as the result value
getChar :: IO Char
-- takes a character as a input and writes it to the screen
-- and returns no result value
putChar :: Char -> IO ()
-- simply return value without performing any interaction
-- this is basically a pure to impure conversion
return :: a -> IO a

Haskell

Sequencing

act :: IO (Char, Char)
act = do x <- getChar
getChar
y <- getChar
return (x, y)

Haskell

Derived Primitives

getLine :: IO String
getLine = do x <- getChar
if x == '\n' then return []
else
do xs <- getLine
return (x:xs)

Haskell

putStr :: String -> IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
putStr xs

Haskell

-- Just mentioned here so that
-- one can try out problems with input
import Control.Arrow ((>>>))
main :: IO ()
main = interact $
lines >>> head >>> read >>> solve >>> (++ "\n")
solve :: Int -> String
-- Type 2
import Control.Arrow ((>>>))
main :: IO ()
main =
interact $
words >>> map read >>> solve >>> show >>> (++ "\n")
solve :: [Integer] -> Integer

Haskell

Simple I/O Operations

These are in-built.

putChar :: Char -> IO()
putStr :: String -> IO ()
putStrLn :: String -> IO ()
print :: Show a => a -> IO ()
getChar :: IO Char
getLine :: IO String
getContents :: IO String
interact :: (String -> String) -> IO ()
show :: Show a => a -> String
read :: Read a => String -> a

Haskell

main = do
putStrLn "enter value for x: "
input1 <- getLine
putStrLn "enter value for y: "
input2 <- getLine
let x = (read input1 :: Int)
let y = (read input2 :: Int)
print (x + y)

Haskell

Lazy Evaluation

$\text{lazy evaluation} = \text{outermost evaluation}\ +\ \text{shared arguments}$

Why is it important?

â€˘

No unnecessary evaluation

â€˘

Ensures termination when possible

â€˘

Supports programming with infinite structures

â€˘

Allows programs to be modular (separates control from data)

Notes on Functional Programming

Haskell is very expressive language. It makes you think abstractly and forces to model and define the problem mathematically.

â€˘

Focus on what to compute (definitions) rather than how

â€˘

Power of abstraction and modularity

â€˘

Equational reasoning

â€˘

How powerful types are

The main drawback is that it is hard to reason about efficiency.