1 - haskell

In absence of side-effects (purely functional computations), from the point of view of the result the order in which functions are applied (almost) does not matter.

However, it matters in terms of performances, consider this function:

(define (sum-square x y)
  (+ (* x x)
     (* y y)))
Copy

In Scheme the function is evaluated in a call-by-value strategy:

(sum-square (+ 1 2) (+ 2 3))
;; applying the first +
= (sum-square 3 (+ 2 3))
;; applying +
= (sum-square 3 5)
;; applying sum-square
= (+ (* 3 3)(* 5 5))
...
= 34
Copy

This means that redexs (reducible expressions) are evaluated in a leftmost-innermost order.

Another strategy is call-by-name:

(sum-square (+ 1 2) (+ 2 3))
;; applying sum-square
= (+ (* (+ 1 2)(+ 1 2))(* (+ 2 3)(+ 2 3)))
...
= 34
Copy

In this case redexs are evaluated in an outermost fashion, that means function are always applied before their arguments.

If there is an evaluation for an expression that terminates, call-by-name
terminates, and produces the same result.

Differences arise when an evaluation does not terminate, e.g., infinite loop, in this case only with a call-by-name strategy the computation can terminate.

(define (infinity)
  (+ 1 (infinity)))
(define (fst x y) x)

(fst 3 (infinity)) ; => 3 with CBN
Copy

Haskell strategy is call-by-need, which is a memoized^[1] version of call-by-name where, if the function argument is evaluated, that value is stored for subsequent uses.

In Scheme the default is call-by-value, but we can achieve other strategies too:

• call-by-name (outermost order): the only way to delay the execution is to use macros which are expanded at compile time.
• call-by-need: can be enforced using thunks^[2] to prevent evaluation, and then force it with an explicit call, a possible idea to overcome the non termination of (fst 3 (infinity)).

There is already an implementation in Racket based on delay and force, but we’ll see how to implement them with macros and thunks.

delay is used to return a promise to execute a computation (implements call-by-name), moreover, it caches the result (memoization) of the computation on its first evaluation and returns that value on subsequent calls (implements call-by-need).

(struct promise
  (proc   ; thunk or value
   value? ; already evaluated?
   ) #:mutable)

(define-syntax delay
  (syntax-rules ()
    ((_ (expr ...))
     (promise (lambda ()
                (expr ...)) ; a thunk
              #f)))) ; still to be evaluated
Copy

force is used to force the evaluation of a promise:

(define (force prom)
  (cond
    ; is it already a value (not a promise)?
    ((not (promise? prom)) prom)
    ; is it an evaluated promise?
    ((promise-value? prom) (promise-proc prom))
    (else
     (set-promise-proc! prom
                        ((promise-proc prom)))
     (set-promise-value?! prom #t)
     (promise-proc prom))))
Copy

In Haskell functions have only one argument, functions with more arguments are curried.
Consider the function with signature sum-square: 𝟚, where is the set of complex numbers:

(define (sum-square x y)
  (+ (* x x)
     (* y y)))
Copy

The curried version has signature sum-square : :

(define (sum-square x)
  (lambda (y)
    (+ (* x x)
       (* y y))))
 
;; shorter version:
(define ((sum-square x) y)
  (+ (* x x)
     (* y y)))
Copy

The operator is right associative, the signature can be re-written as sum-square : .
In the curried version the partial application is much easier: we don't provide all the parameters but just the first, the rest of the parameters are left as lambda functions.

In Haskell every function is automatically curried.

Haskell has static typing, everything must be known at compile time. There is type inference, so usually we do not need to explicitly declare variables. Types start with a capital letter.

"has type" is written ::

5   :: Integer
'a' :: Char
inc :: Integer -> Integer
[1, 2, 3] :: [Integer]  -- equivalent to 1:(2:(3:[]))
(’b’, 4)  :: (Char, Integer)
"Hello World" :: [Char]
"But also" :: String
Copy

Type synonyms are defined with keyword type:

type String = [Char]
type Assoc a b = [(a,b)]
Copy

User defined types are based on data declarations:

-- a "sum" type (union in C)
data Bool = False | True
Copy

Bool is the (nullary) type constructor, while False and True are data constructors (nullary as well). The Bool type is already defined in Haskell.

Data and type constructor live in separate name-spaces, so it is possible to use the same name for both:

-- a "product" type (struct in C)
data Pnt a = Pnt a a
Copy

Parametric polymorphism: lower case letters are type variables, [a] stands for "list of elements of type a, for any (type) a".
It allows a function or a data type to be written generically so that it can handle values identically without depending on their type.

Product types are like struct in C or in Scheme, the access is positional, we may define accessors as:

pointx Point x _ = x
pointy Point _ y = y

-- OR with C like syntax
data Point = Point {pointx, pointy :: Float}
Copy

This declaration automatically define two field names pointx and pointy and their corresponding selector functions.

Recursive types are allowed, an example of binary tree:

data Tree a = Leaf a | Branch (Tree a) (Tree a) 
Branch :: Tree a -> Tree a -> Tree a  -- data constructor Branch type
aTree = Branch (Leaf 'a') (Branch (Leaf 'b') (Leaf 'c'))
Copy

At the prompt we can use :t for getting the type:

ghci> :t (aTree)
(aTree) :: Tree Char
Copy

List are also recursive, Haskell has special syntax for them:

data [a] = [] | a : [a]
Copy

Note: [] is a data and type constructor, while : is an infix data constructor.

Functions are declared through a sequence of equations:

length :: [a] -> Integer      -- domain and codomain
length [] = 0                 -- case of empty list covered first
length (x:xs) = 1 + length xs -- general case
Copy

A list of integers can be seen as a cons node (x:xs) where x is the first value and xs is the rest of the list.

This is also a case of pattern matching: arguments are matched with the right part of the equations and if a match succeeds, the function body is called.

Pattern matching proceeds top-down, left-to-right, patterns may have boolean guards:

sign x | x > 0  = 1
       | x == 0 = 0
       | x < 0  = -1
Copy

An example function on trees:

fringe :: Tree a -> [a]      -- domain and codomain
fringe (Leaf x) = [x]        -- special case first
fringe (Branch left right) = fringe left ++ fringe right
Copy

++ is a list concatenation.

Haskell has map, and it can be defined as:

map f [] = []                 -- special case first 
map f (x:xs) = f x : map f xs -- general case

map (1 +) [1,2,3] -- => [2,3,4]
Copy

. is used for composing functions

let dd = (*2) . (1+)
dd 6 -- => 14

let dd = (2*) . (+1)
dd 6 -- => 14
Copy

$ syntax for avoiding parentheses, e.g. (10*) (5+3) = (10*) $ 5+3

Infinite computations can be defined:

ones = 1 : ones
numsFrom n = n : numsFrom (n+1)
squares = map (^2) (numsFrom 0)
Copy

We cannot evaluate them but there is take to get finite slices from them:

take 5 squares  -- => [0,1,4,9,16]
Copy

There is a convenient syntax for infinite lists:

ones = [1,1..]
numsFrom n = [n..]
Copy

zip is a useful function:

:t zip             -- => zip :: [a] -> [b] -> [(a, b)]
zip [1,2,3] "ciao" -- => [(1,'c'),(2,'i'),(3,'a')]
Copy

List comprehension uses set annotation theory (like in Python):

[(x,y) | x <- [1,2], y <- "ciao"]
-- => [(1,'c'),(1,'i'),(1,'a'),(1,'o'),(2,'c'),(2,'i'),(2,'a'),(2,'o')]
Copy

In this case we created a list of pairs where the first element x is taken from the first list and y from the second.

A list of all the fibonacci numbers:

fib = 1 : 1 :
	[a+b | (a,b) <- zip fib (tail fib)] 
	-- recursive zip [1,1] , [1, __ ]

zip [1,1,2,3] [1,2,3]  -- => [(1,1),(1,2),(2,3)]
Copy

Similar to Scheme tail is cdr, while head is car.

bottom (often represented as ⊥) is a term used to represent computations that do not result in a normal value.
It is defined as bot = bot, an example of a non-terminating computation, the expression is trying to define bot in terms of itself, leading to an infinite loop.
bottom can manifest in several ways, such as:

• Non-terminating computations (infinite loops)
• Exceptions
• Partial functions that are not defined for certain inputs
  All errors have value bot, a value shared by all types.
  error :: String -> a is used to generate an error and it can be of any type (polymorphic only in the output), the reason is that it returns bot, in practice an exception is raised.

take 0 bot -- => []
take bot 0 -- => infinite computation
Copy

case syntax for an alternative definition of take:

take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

-- alternative
take m ys = case (m,ys) of 
              (0,_)    -> []
              (_,[])   -> []
              (n,x:xs) -> x : take (n-1) xs
Copy

if is available, its syntax is if <c> then <t> else <e>, we could define it as a function:

if :: Bool -> a -> a -> a
if True  x _ = x
if False _ y = y
Copy

let is like Scheme letrec , that means evaluation are top-to-bottom, left-to-right and may be recursive:

-- python like layout
let x = 3
    y = 12
in x+y -- => 15

-- C like layout
let {x = 3 ; y = 12} in x+y
Copy

where can be convenient to scope binding over equations (local binding):

powset set = powset' set [[]] where
  powset' [] out = out
  powset' (e:set) out = powset' set (out ++ [e:x | x <- out])
Copy

foldl is efficient in Scheme, its definition is naturally tail-recursive, in Haskell this is not as efficient because of call-by-need:

foldl (+) 0 [1,2,3]
foldl (+) (0 + 1) [2,3]
foldl (+) ((0 + 1) + 2) [ 3 ]
foldl (+) (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3) = 6
Copy

Haskell is a non-strict (or lazy) by default but there are various ways to enforce strictness in Haskell, e.g., on data we can use bang patterns:

data Complex = Complex !Float !Float
Copy

A datum marked with ! is considered strict.

seq is the canonical operator to force evaluation seq :: a -> t -> t.
seq x y returns y only if the evaluation of x terminates, strict version of fodl:

foldl' f z []     = z
foldl' f z [x:xs] = let z' = f z x
                    in seq z' (foldl' f z' xs)
Copy

Strict version of standard functions are usually primed.

There is a convenient strict variant of $ called $!, its definition:

($!) :: (a -> b) -> a -> b
f $! x = seq x (f x)
Copy

Haskell has a simple module system, with import, export and namespaces

module CartProd where --- export everything
infixr 9 -*-
-- r: right associative
-- 9: precedence goes from 0 to 9, the strongest
x -*- y = [(i,j) | i <- x, j <- y]
Copy

In Haskell, a file can only define a single module, for example the module Treehas to be defined in another file:

module Tree ( Tree(Leaf, Branch), fringe ) where
data Tree a = Leaf a | Branch (Tree a) (Tree a)
fringe :: Tree a -> [a] ...
Copy

The main module in Haskell is the module that serves as the entry point of a Haskell program. By convention, this module is called Main and it must export the value main. The main function is of type IO () and when the program is executed, the computation main is performed, and its result is discarded:

module Main (main) where
import Tree ( Tree(Leaf ,Branch) ) -- import Tree
main = print (Branch (Leaf 'a') (Leaf 'b'))
Copy

Modules provide the only way to build Abstract Data Types (ADT), the characteristic feature of an ADT is that the representation type is hidden: all operations on the ADT are done at an abstract level which does not depend on the representation.

A suitable ADT for binary trees might include the following operations:

data Tree a  -- just the type name
leaf         :: a -> Tree a
branch       :: Tree a -> Tree a -> Tree a
cell         :: Tree a -> a
left, right  :: Tree a -> Tree a
isLeaf       :: Tree a -> Bool
Copy

ADT implementation:

module TreeADT (Tree, leaf, branch, cell,
                left, right, isLeaf) where
data Tree a          = Leaf a | Branch (Tree a) (Tree a)
leaf                 = Leaf
branch               = Branch
cell (Leaf a)        = a
left (Branch l r)    = l
right (Branch l r)   = r
isLeaf (Leaf _)      = True
isLeaf _             = False
Copy

Having an ADT without constructor is an advantage if at a later time we change the representation type without affecting users of the type.

The Prelude module is a standard library module that is automatically imported into every Haskell program by default. It contains a collection of commonly used functions, types, and classes that are essential for writing Haskell programs, in fact all the operations that we didn't define ourselves are part of the Prelude module.

Type classes are the mechanism provided by Haskell for ad-hoc polymorphism^[3] (a.k.a. overloading), e.g.:

:t (+)  -- => (+) :: Num a => a -> a -> a
Copy

Num is a type class (to consider as a set of types), Float, Integer, Int^[4], Rational belongs to the class and therefore we can apply + to these types.

A class is a "container" of overloaded operations, we can declare a type to be an instance of a type class, meaning that it implements its operations.
In other words, a type class defines a set of functions that can have different implementations depending on the type of data they are used with.

The Eq typeclass provides the == (equality) and /= (inequality) operations. So, for any type that is a member of the Eq type class, you can use these operations.
Type class Eq definition:

class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)  
    x /= y = not (x == y)

(==) :: Eq a => a -> a -> Bool
Copy

In this definition, a is a type variable and Eq a is a typeclass constraint. The constraint Eq a means that a must be an instance of Eq typeclass.
The == and /= operations are defined in terms of each other. This means if you define one of them for a type, Haskell can automatically figure out the other one. This is why you can create an instance of Eq and only need to implement the == operator.
An implementation of == is called a method.

We can define instances like this:

instance (Eq a) => Eq (Tree a) where
-- type a must support equality as well
  Leaf a == Leaf b = a == b
  (Branch l1 r1) == (Branch l2 r2) = (l1==l2) && (r1==r2)
  _ == _ = False
Copy

We declare that Tree a is an instance of the Eq type class, but only when a is also an instance of Eq with the (Eq a) => syntax. This is because the implementation of == for Tree a relies on == for a.

We can also extend Eq with comparison operations:

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

Ord is a subclass of Eq.
It is possible to have multiple inheritance: class (X a, Y a) => Z a.

Show is another class used for showing, i.e. creating a string representation of the value. To have an instance of Show we have to implement the method show:

instance Show (a -> b) where
  show f = "<< a function >>"
  
instance Show a => Show (Tree a) where
  show (Leaf a) = show a
  show (Branch x y) = "<" ++ show x ++ " | " ++ show y ++ ">"
Copy

deriving can be used to automatically define instances of some classes:

-- custom operator right-associative with precedence level of 5
infixr 5 :^: 
data Tr a = Lf a | Tr a :^: Tr a deriving (Show, Eq)

ghci> let x = Lf 3 :^: Lf 5 :^: Lf 2
ghci> x
Lf 3 :^: (Lf 5 :^: Lf 2)
Copy

Example with class Ord:

data RPS = Rock | Paper | Scissors deriving (Show, Eq)

instance Ord RPS where
  x <= y | x == y      = True
  Rock     <= Paper    = True 
  Paper    <= Scissors = True
  Scissors <= Rock     = True
  _        <= _        = False
Copy

In Haskell | pipes are guards, x <= y | x == y means that if we match any two instances of RPS where the boolean guard x == y is true then <= is true, in other words if x and y are the same move, then x is considered to be less than or equal to y. We only need to define <= to have an instance of Ord.

A simple reimplementation of rational numbers with class Num:

data Rat = Rat !Integer !Integer deriving (Eq) -- Rational \frac{x}{y}

simplify (Rat x y) = let g = gcd x y in Rat (x 'div' g) (y 'div' g)

makeRat x y = simplify (Rat x y)

instance Num Rat
	(Rat x y) + (Rat x' y') = makeRat (x * y' + x' * y) (y * y')
	(Rat x y) - (Rat x' y') = makeRat (x * y' - x' * y) (y * y')
	(Rat x y) * (Rat x' y') = makeRat (x * x') (y * y')
	abs (Rat x y)           = makeRat (abs x) (abs y)
	signum (Rat x y)        = makeRat (signum x * signum y) 1
	fromInteger x           = makeRat x 1

instance Ord Rat where
	(Rat x y) <= (Rat x’ y’) = x*y’ <= x’*y

instance Show Rat where
	show (Rat x y) = show x ++ "/" ++ show y
Copy

I/O is not referentially transparent^[5], two different calls of getChar could return different characters.
In general, IO computation is based on state change (e.g. of a file), hence if we perform a sequence of operations, they must be performed in order (and this is not easy with call-by-need).
getChar is an IO action:

getChar :: IO Char
putChar :: Char -> IO ()
Copy

IO is an instance of the monad class, and in Haskell it is considered as an indelible stain of impurity.

main is the default entry point of the program (like in C), special syntax for working with IO: do, <-:

main = do {
  putStr "Please, tell me something>";
  thing <- getLine;
  putStrLn $ "You told me \"" ++ thing ++ "\".";
}

main    :: IO ()
putStr  :: String -> IO ()
getLine :: IO String
Copy

<- is used instead of = to obtain a value from an IO action.
We will see its real semantics later, it is used to define an IO action as an ordered sequence of IO actions.

In Haskell, exceptions can be raised in pure code but can only be caught within the IO monad. The handle function provided serves this purpose. It has the type:

Exception e => (e -> IO a) -> IO a -> IO a
Copy

This means it takes two arguments:

• A function that takes an exception and returns an IO action.
• An IO action where exceptions may occur.

The first argument (e -> IO a) is the handler which is a function that gets triggered when an exception occurs.

import System.IO
import System.Environment

readfile = do {
    args <- getArgs; -- command line arguments
    handle <- openFile (head args) ReadMode;
    contents <- hGetContents handle; -- note: lazy
    putStr contents;
    hClose handle;
    }
    
main = handle handler readfile
    where handler e
        | isDoesNotExistError e =
            putStrLn "This file does not exist."
        | otherwise =
            putStrLn "Something is wrong."    
Copy

Traditional versions of data structure are imperative! If really needed, there are libraries with imperative implementations living in the IO monad.

In Haskell, the idiomatic approach to working with data structures is to use immutable arrays (Data.Array) and maps (Data.Map) instead of imperative structures. These are both part of the standard libraries that come with Haskell.

In Haskell, a monad is a type class that is used to represent computations as abstract data types. Monads are used for handling side effects, such as I/O operations, exceptions, or state changes.

A Monad must be an instance of Foldable(optional), Functor, Applicative:

• The Functor type class is used for types that can be mapped over. A functor is a type constructor that implements the fmap function, which applies a function to a value in a context. The fmap function is used to apply a function to a value within a functor without changing the context. For example, if you have a Maybe value that contains an integer, you can use fmap to apply a function to the integer without removing it from the Maybe context.
• The Applicative type class is used for types that can be applied to values within a context. An applicative is a type constructor that implements the pure function and the <*> operator. The pure function is used to lift a value into a context, and the <*> operator is used to apply a function within a context to a value within a context. For example, if you have a Maybe value that contains a function and another Maybe value that contains an integer, you can use <*> to apply the function to the integer within the Maybe context.
• The Foldable type class is used for types that can be folded. A foldable is a type constructor that implements the foldr function, which is used to fold a structure of values, applying a function to each value and combining the results.
  However, it's important to note that while Foldable is not a requirement for a Monad but, many common Monads, like Maybe, List, and IO, are also instances of Foldable.

Monads, in Haskell, are a type of algebraic data type that encapsulate computations, often referred to as actions. They enable chaining of these actions into an ordered sequence. Each action within this sequence is augmented with additional processing rules provided by the monad and executed automatically. It is essential for a Monad to be an instance of Functor, Applicative, and Foldable because these operations form the foundation of the monad concept.

Here is the Haskell definition of a Monad:

class Applicative m => Monad m where
    -- Sequentially compose two actions, passing any value produced
    -- by the first as an argument to the second.
    (>>=)  :: m a -> (a -> m b) -> m b
    -- Sequentially compose two actions, discarding any value produced
    -- by the first, like sequencing operators (such as the semicolon)
    -- in imperative languages.
    (>>)   :: m a -> m b -> m b
    m >> k = m >>= \_ -> k
    -- Inject a value into the monadic type.
    return :: a -> m a
    return = pure
    -- Fail with a message.
    fail   :: String -> m a
    fail s = error s
Copy

In this definition, >>= and >>, also known as bind operators, are used to compose actions:

• x >>= y performs the computation x, takes the resulting value and passes it to y then performs y.
• x >> y is analogous, but "throws away" the value obtained by x

The return function is used to inject a value into the monadic type, while fail is used to handle errors. return is by default pure, so it is used to create a single monadic action, e.g., return 5 is an action containing the value 5.

A Monad instance is illustrated below using Maybe:

instance Monad Maybe where
    (Just x) >>= k    = k x
    Nothing  >>= _    = Nothing
    fail _            = Nothing
Copy

The information managed automatically by the monad is the “bit” which encodes the success Just, or failure Nothing of the action sequence.

Just 4 >> Just 5 >> Nothing >> Just 6 
Copy

Evaluates to Nothing, we have propagation of the error.

For a monad to behave correctly, method definitions must obey the following laws:

1. Identity Law
   The Identity Law states that if we take a monadic value and use the return function to put it in a minimal context (i.e., the monad itself), then use the bind operator >>= to feed it to a function, it should be equivalent to just applying that function to the value: return is the identity element.

return x >>= f  <=> f x -- left identity
m >>= return    <=> m   -- right identity
Copy

For example:

> (return 4 :: Maybe Integer) >>= \x -> Just (x+1)
Just 5
> Just 5 >>= return
Just 5
Copy

2. Associativity Law
   The Associativity Law states that the way in which monadic values are combined should not matter. This means that the order in which operations are performed should not affect the result: associativity for binds.

(m >>= f) >>= g <=> m >>= (\x -> (f x >>= g))

> (return 4 >>= \x -> Just (x+1))
            >>= \x -> Just (x*2)
Just 10
> return 4 >>= (\y ->
                  ((\x -> Just (x+1)) y)
                >>= \x -> Just (x*2))
Just 10
Copy

The do syntax is used to avoid the explicit use of >>= and >>, translation:

do e1 ; e2       <=> e1 >> e2
do p <- e1 ; e2  <=> e1 >>= \p -> e2
Copy

Others ways to express the do notation:

do e1               do p <- e1
   e2                  e2
   
do { e1 ;           do { p <- e1;
     e2 }                e2 }
Copy

IO is a built-in monad in Haskell, we use the do notation to perform IO actions, though it looks like a sub-language its semantics are based on bind and pure, example:

esp :: IO Integer
esp = do x <- return 4
         return (x+1)
> esp
5
Copy

We saw that monads are useful to automatically manage state (of the computation), we now define a general monad to do it (it is already available in the libraries as Control.Monad.State).

First of all, we define a type to represent our state:

data State st a = State (st -> (st, a))
Copy

The idea is having a type that represent a computation with a state, i.e., a function taking the current state and returning the next (type a is the explicit part of the monad).
It is different from previous containers because we have two parameters, but we need unary type constructor so the "container" know has type constructor State st.

We need to make State an instance of Functor:

instance Functor (State st) where
    fmap f (State g) = State (\s -> let (s’, x) = g s
                                    in (s’, f x))
Copy

The idea is quite simple: in a value of type State st a we apply f to the value of type a.

Then, we need to make State an instance of Applicative:

instance Applicative (State st) where
    pure x = State (\t -> (t, x))
    (State f) <*> (State g) =
        State (\s0 -> let (s1, f’) = f s0
                          (s2, x) = g s1
                      in  (s2, f’ x))
Copy

The idea is similar to the previous one: we apply f :: State st (a -> b) to the data part of the monad.

The same approach can be used for the monad definition:

instance Monad (State state) where
    State f >>= g = State (\olds ->
                            let (news, value) = f olds
                                State f’ = g value
                            in f’ news)
Copy

An important aspect of this monad is that monadic code does not get evaluated to data, but to a function, State is a function and bind is function composition.