Martin Sulzmann
Playing with functions and lists
head, tail, null (total vs partial functions)
recursive functions, tail recursion, see "sumUp"
quicksort gtThan [] = []
quicksort gtThan (p:xs) = (quicksort gtThan lesser) ++ [p] ++ (quicksort gtThan greater)
where
ltEqThan = \x -> \y -> not (gtThan x y)
lesser = filter (gtThan p) xs
greater = filter (ltEqThan p) xs
-- lists in Haskell
-- [] denotes the empty list
-- [1,2,3,4] denotes the list containing the elements 1,2,3 and 4.
-- elements in a list must all be of the same type!
-- True is of type Bool
-- Hence, [1,True,2] will not type check!
-- 1 is a number but can be an Int, a Float, ...
-- Lesson learned. Lists in Haskell are homogenous, elements must be of the same type.
-- What we will see later, same type or belong to the same type class.
-- Let's play with lists.
-- [[1,2], [1], [2,3]] denotes a list of lists where the inner list only contains numbers
-- A non-empty list has a head and a tail.
-- head [1,2,3] => 1
-- tail [1,2,3] => [2,3]
-- null checks if a list is empty
-- null [] => True
-- null [1,2,3] => False
-- add up all numbers in a list, our first function in Haskell!
-- Java: Use an array and simply iterate through the array,
-- accessing each element and adding that element to some 'sum' variable.
-- Haskell: Iteration via recursion and structural induction over the input values.
--
{-
Haskell is implicitly typed, no type annotations required!
Haskell is expression based (not command base like say C, ...)
-}
-- The desired behavior:
-- If the list xs is empty => 0
-- if the list xs is non-empty => head xs + sumUp (tail xs)
sumUp xs = if null xs
then 0
else head xs + sumUp (tail xs)
-- else (head xs) + (sumUp (tail xs))
-- function application in Haskell binds tighter than say '+'.
-- Haskell supports guarded equations
sumUp2 xs
| null xs = 0
| otherwise = head xs + sumUp2 (tail xs)
{-
Example evaluation:
sumUp [1,2,3]
=> if null [1,2,3]
then 0
else head [1,2,3] + sumUp (tail [1,2,3])
Side calculation: null [1,2,3] => False
=> if False
then 0
else head [1,2,3] + sumUp (tail [1,2,3])
=> head [1,2,3] + sumUp (tail [1,2,3])
Side calculation: head [1,2,3] => 1
tail [1,2,3] => [2,3]
=> 1 + sumUp [2,3]
=> ...
=> 1+2+3 => 6
-}
-- Accumulator recursive variant of "sumUp" using tail recursion.
sumUpAcc n xs
| null xs = n
| otherwise = sumUpAcc (head xs + n) (tail xs)
sumAcc xs = sumUpAcc 0 xs
-- In C, Java, you're "forced" to write programs in "tail recursive" form.
-- Haskell does many optimizations automatically.
-- Functions in Haskell can be total or partial.
-- Total function means: Each possible input yields some valid output.
-- Partial function means: The function is not defined for some input values.
-- head and tail are examples of partial functions.
-- null is a total function.
-- Haskell supports various forms of polymorphism.
-- null, head, and tail can be applied on lists of any type.
-- All three functions do not care about the specific element type.
-- This means that all three are examples of "generic" functions.
-- We find here an example of "parametric polymorphism (aka generics in Java slang).
-- Supplying arguments one by one.
add (x,y) = x + y
plus x y = x + y
plus2 = \x -> (\y -> x + y)
inc = plus2 1
{-
inc 4
=> (plus2 1) 4 -- shorter write this as "plus2 1 4"
=> (\y -> 1 + y) 4
=> 1 + 4
=> 5
-}
-- Function application is left associative.
-- That means, "plus 1 2" equals "(plus 1) 2"
Lambda calculus
Syntax
Free and bound variables
Renaming and substitution (alpha-reduction)
Evaluation (beta-reduction)
{-
Context-free languages (grammars + rules) (CFL, CFG, CFR).
Example rule:
E -> x
where E denotes a non-terminal symbol by a terminal symbol x.
Convention:
Non-terminals are written uppercase and terminals are written lowercase.
Another example rule:
E -> ( E )
In computer science we often use EBNF (Extended Backus Naur Form).
EBNF a "short-hand" version of writing CFRs.
In EBNF, non-terminals are usually written lowercase.
For example,
e ::= ( e )
CFRs with the same left-hand side are combined.
For example,
e ::= ( e ) | x
Lambda calculus syntax:
t ::= x | \ x -> t | t t
where we use "\ x ->" to denote a lambda-binding.
Based on the above grammar, the term "\x -> x x" is ambiguous.
That means, there are two possible interpretations based on the above grammar.
There are two possible derivations.
(1)
t
-> \ x -> t (we replace "t" by "\ x -> t" using the 2nd rule)
-> \ x -> t t
-> \ x -> x t
-> \ x -> x x
Interpreted as \ x -> ( x x )
where we make use of ( ... ) to hightlight the difference in interpretation.
(2)
t
-> t t (we replace "t" by "t t" using the 3rd rule)
-> \ x -> t t
-> \ x -> x t
-> \ x -> x x
Interpreted as (\ x -> x) x
How to resolve such ambiguities?
We add (...) to our language.
t ::= x | \ x -> t | t t | ( t )
And we use some further syntactic sugar (conventions) to remove ( ... ).
Function application is left associative:
Usually, "t t t" would be ambigous, cause could be interpreted either
(a) (t t) t, or
(b) t (t t)
Under the assumption that function application is left associative,
we will always choose (a).
The body of a lambda abstractions extends to the right as long as possible:
Usually, "\x -> t t" would be ambiguous. See above.
Under the "the body ...", we will alwasy interprete "\x -> t t" as "\x -> (t t)".
Free and bound variables.
See also "scoping rules".
Examples:
\ x -> x x
there are three occurences of "x".
Above term has no free variables.
fv(\ x -> x x) = { }
fv(\ x -> x x)
= fv(x x) - { x }
= (fv(x) cup fv(x)) - { x }
= ({x} cup {x}) - {x}
= {x} - {x}
= {}
where
"-" denotes set difference
"cup" denotes set union.
Another example:
(\x -> x) x
fv( (\x -> x) x )
= fv( \ x -> x) cup fv(x)
= (fv(x) - {x}) cup {x}
= ({x} - {x}) cup {x}
= {} cup {x}
= {x}
Point to note.
There are two occurences of "x" as a variable!
But they have nothing in common.
Renaming.
Example:
Consider
(\x -> x) x
What if we rename the bound variable x?
Say we call it "x2" instead of "x".
Do we (after renaming) get the following?
(\x2 -> x2) x
Renaming for our example means the following.
(i) (\x -> ...) replace the x by x2 and we obtain (\x2 -> ...)
(ii) In the lambda body, we replace all free occurences of x by x2.
In our example, the lambda body just consists of x. Hence, we obtain x2.
In general, consider renaming of a lambda bound variable for
\x -> t
(i) replace \x -> ... by \x2 -> ...
(ii) In the lambda body t, we apply the substitution [x2/x].
This means, whenever we find x replace the x by x2.
In our example, we find [x2/x]x.
That is, the substitution [x2/x] is applied on the lambda body x.
Example:
(\x -> (\x -> x) x) x
Rename all the bound variables by introducing some "fresh" variables.
Fresh means, some variables names that haven't been used so far.
(\x -> x) is renamed to (\x2 -> x2)
(\x -> (\x -> x) x) is renamed to (\x3 -> [x3/x] ((\x -> x) x) )
and this yields (\x3 -> (\x -> x) x3)
Combing the sub(renmaing) results.
We rename (\x -> (\x -> x) x) x to (\x3 -> (\x2 -> x2) x3) x.
Dynamic semantics:
The first steps consists of renaming the lambda term.
This referred to as "alpha-reduction".
Then, we actually evaluate function applications.
This referred to as "beta-reduction".
(\x -> t1) t2 -> [t2/x]t1
This means, on the lambda body t1 we apply the substitution [t2/x].
By doing alpha-reduction (aka renaming) first,
applying the substitution is easy. Cause we run into "name clashes".
The variable to be replaced will never clash with the variable of lambda binder.
-}Evaluation strategies (CBN, CBV, AOR, NOR)
Laziness in Haskell, see "ones".
Intro to algebraic data types (and showing/printing user-defined values via "deriving").
{-
Evaluation strategies.
-- Syntax again
Example.
(\f -> \x -> f (f x)) ((\x -> x) (\x -> x))
^^^^^^^^^^^^^^
Notation: We simply add some redundant ( ... )
(\f -> ( \x -> f (f x) ) ) ((\x -> x) (\x -> x))
^^ ^^
redundant cause the body of a lambda extends furthest to the right.
What about getting rid of some (...).
(\f -> \x -> f ( f x ) ) ((\x -> x) (\x -> x))
^^ ^^
Can we get rid of these ( ... )!
No! We can't for the following reason.
(\f -> \x -> f f x ) ((\x -> x) (\x -> x))
Function application is left associative.
Hence, the above is interpreted as follows.
(\f -> \x -> ( f f ) x ) ((\x -> x) (\x -> x))
^^ ^^
Yields a lambda term that has a different meaning !!!
-- CBN vs NOR
Example.
(\f -> \x -> f (f x)) ((\x -> x) (\x -> x))
We're looking for a redex. Let's label all redexes we find.
Redex 1:
(\f -> \x -> f (f x)) ((\x -> x) (\x -> x))
^^^^^^^^^ ^^^^^^^^
redex (inner)
Redex 2:
(\f -> \x -> f (f x)) ((\x -> x) (\x -> x))
^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^
redex (outer)
(\f -> \x -> f (f x)) ((\x -> x) (\x -> x))
--> CNB+NOR picks redex 2
[((\x -> x) (\x -> x)) / f] \x -> f (f x)
= \x -> ( (\x -> x) (\x -> x) ) ( ((\x -> x) (\x -> x)) x )
^^ ^^
can drop (...) cause function application is left associative
= \x -> (\x -> x) (\x -> x) ( ((\x -> x) (\x -> x)) x )
Let's add some ( ... ) to highlight the body of the lambda abstraction
= \x -> ( (\x -> x) (\x -> x) ( ((\x -> x) (\x -> x)) x ) )
^^ ^^
actually redundant, cause body of lambda extends furthest to the right,
but added for clarity
= \x -> ( (\x -> x) (\x -> x) ( ((\x -> x) (\x -> x)) x ) )
^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^^
Take note. Both redexes are under a "lambda".
Hence, we won't further evaluate under CBN.
But we can continue with NOR.
-> we pick the outermost redex
\x -> ( (\x -> x) (\x -> x) ( ( (\x -> x) x ) )
^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^^^^^^^^^
[
A note regarding name clashes.
Consider
(\x -> x) x -> [x / x] x
^^^^^^^^^^^
crazy, same x's but refer to different things!!!!
Apply alpha-reduction = renaming of lambda bound variables.
(\x -> x) x
=_alpha (\x1 -> x1) x
-> [x / x1] x1
= x
]
-> \x -> ( (\x -> x) (\x -> x) ( ( x ) )
= \x -> (\x -> x) (\x -> x) x
^^^^^^^^^^^^^^^^^^
-> \x -> (\x -> x) x
^^^^^^^^^^^
-> \x -> x
This is the final result!
-}
-- laziness in Haskell = special form of CBN
l1 :: [Int]
l1 = [1]
l2 :: [Int]
l2 = [1] ++ l1
l3 :: [Int]
l3 = [1] ++ l2
ones :: [Int]
ones = 1:ones
-- Assumption: There are at least two elements in the input list.
addFirstTwoElems :: [Int] -> Int
addFirstTwoElems xs
| myNull xs = 0
| myNull (tail xs) = 0
| otherwise = head xs + head (tail xs)
-- (1) a is a type parameter, among other forms of polymorphism,
-- Haskell supports parametric polymorphism (aka generics).
-- (2) Define functions by pattern matching over the possible shapes of input.
myNull :: [a] -> Bool
myNull [] = True
myNull (x:_) = False
-- algebraic data types (simple cases)
data Result = OK Int | Fail String deriving Show
failSafeDiv :: Int -> Int -> Result
failSafeDiv n 0 = Fail "division by zero"
failSafeDiv n m = OK (n `div` m)
{-
failSafeDiv 3 2
=> OK (3 `div` 2)
= OK 1
OK 1 is a value of type Result
ghci wants to print a value.
What does this mean?
Well, we need to convert that value into string!
We need to define a conversion of Result values to strings.
Here comes some magic!
The "deriving Show" bit in the above data type definition,
tells ghci how to convert
the Haskell value of type Result
OK 1
into a string of the form
"OK 1"
Consider some ghci interaction.
*Main> OK 1
OK 1
In detail,
*Main> OK 1 <--- Haskell value of type Result
OK 1 <--- string value
There are no "..." !?
Well, Haskell "prints" the value via putStrLn. Hence, no " ... ".
For example, consider the following ghci interaction.
*Main> putStrLn "Hello"
Hello
-}Regular expressions
From EBNF to (recursive) data types in Haskell
Show type class
Parametric data types by examples
Type class instances
{-# LANGUAGE FlexibleInstances #-}
-- required to due our definition of "instance Show (RE Char) where"
-- let's play with regular expressions
-- Syntax of regular expression.
-- We write R to denote a regular expression.
-- We assume that our alphabet symbols are regular expressions.
-- R ::= 'x' | 'y' | ... alphabet symbols
-- | epsilon represents the empty string
-- | R + R alternatives
-- | R . R concatenation
-- | R* Kleene star
--- | (R) Grouping via parentheses
-- Example:
-- R1 = 'y' + ( ('z')* . 'x' )
-- R2 = 'y' + ('z')* . 'x'
-- Ambiguous!
-- Do we mean 'y' + (('z')* . 'x') or ('y' + ('z')*) . 'x'
-- How to represent the above syntactic description in Haskell?
-- In Haskell the natural way is to use data types.
-- In fact, any EBNF specification can be turned into a data type!!!
data R = Sym Char
| Alt R R -- the option would to be define Alt (R, R)
| Conc R R
| Star R {- deriving Show -}
-- deriving Show bit means the following.
-- Haskell automatically derives and instance of Show for the type R.
-- That means, the (overloaded) "show" function can be applied
-- to a value of type R and yields a String.
-- We wish to build our own instance of Show.
instance Show R where
-- show in this context is of type R -> String
-- In Haskell String = [Char]
show (Sym x) = [x]
-- Recall variables in patterns are non-linar (at most one occurrenc).
-- Hence, Alt r r is not legal.
show (Alt r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (Conc r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (Star s) = "(" ++ show s ++ ")" ++ "*"
-- HOMEWORK:
-- Add prededenc rules.
-- We assume that concatenation (".") binds tigher than alternatives ("+").
-- Instead of (y+((z)*.x))
-- we'd like to get y+(z)*.x
-- HINT: Need to adapt the above show definition.
-- Need some more involved pattern matching.
-- some examples
r1 = Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
r1b = (Sym 'y') `Alt` ((Star (Sym 'z')) `Conc` (Sym 'x'))
r1c = Alt (Sym 'y') $ Conc (Star (Sym 'z')) (Sym 'x')
{-
*Main> r1
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
1. Haskell evaluates r1 and applies "show" on this value.
2. Then, Haskell prints the resulting String to console.
In essence, Haskell evaluates the following piece of code.
*Main> putStrLn (show r1)
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
While we are here. I'm often using the "$" symbol.
Allows us to get rid of ( ... ).
If we just write
*Main> putStrLn show r1
yields a type error cause the above is interpeted as
(putStrLn show) r1
due to function application being left associative.
We can use "$" to separate function application and
thus it's "nicer" to write the above as follows.
*Main> putStrLn $ show r1
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
Sample outputs.
*Main> r1
(y+((z)*.x))
-}
data RE a = SymRE a
| AltRE (RE a) (RE a)
| ConcRE (RE a) (RE a)
| StarRE (RE a)
re1 = AltRE (SymRE 'y') (ConcRE (StarRE (SymRE 'z')) (SymRE 'x'))
re2 = AltRE (SymRE True) (StarRE (SymRE False))
{-
-- Overlaps with instance Show a => Show (RE a) where
instance Show (RE Char) where
show (SymRE x) = [x]
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
-}
{-
*Main> :t re2
re2 :: RE Bool
If we only have "instance Show (RE Char) where"
then we get
*Main> re2
<interactive>:46:1: error:
• No instance for (Show (RE Bool)) arising from a use of ‘print’
• In a stmt of an interactive GHCi command: print it
because as the error message says,
we need an instance for (Show (RE Bool))
-}
{-
-- Overlaps with instance Show a => Show (RE a) where
instance Show (RE Bool) where
-- example of nested pattern matching
show (SymRE True) = "1"
show (SymRE False) = "0"
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
-}
{-
Now works!
*Main> :t re2
re2 :: RE Bool
*Main> re2
(1+(0)*)
-}
-- To be read as follows.
-- Given we have
-- Show a
-- we can provide an instance
-- Show (RE a)
instance Show a => Show (RE a) where
-- What we know about x?
-- Some value of type a. How to "show" x?
-- show x implies that we need Show a!
show (SymRE x) = show x
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
data SomeSigma = A | B | C deriving Show
re3 :: RE SomeSigma
re3 = ConcRE (SymRE A) (AltRE (SymRE B) (SymRE C))
-- You can't mix RE Char and RE Bool, e.g. consider
{-
re4 = ConcRE (SymRE True) (SymRE 'a')
PPSoSe21-W6.hs:215:28: error:
• Couldn't match type ‘Char’ with ‘Bool’
Expected type: RE Bool
Actual type: RE Char
• In the second argument of ‘ConcRE’, namely ‘(SymRE 'a')’
In the expression: ConcRE (SymRE True) (SymRE 'a')
In an equation for ‘re4’: re4 = ConcRE (SymRE True) (SymRE 'a')
|
215 | re4 = ConcRE (SymRE True) (SymRE 'a')
The definition of RE tells us that the alphabet, the type parameter a,
must be the same!
-}Extension of Week 6
More on "(...)" (concrete = source syntax versus abstract syntax)
"type" versus "data" keyword
Qualified (constrained) types such as "Show a => [a] -> String"
Show instance for user-defined lists.
{-# LANGUAGE FlexibleInstances #-}
-- required to due our definition of "instance Show (RE Char) where"
-- let's play with regular expressions
-- Syntax of regular expression.
-- We write R to denote a regular expression.
-- We assume that our alphabet symbols are regular expressions.
-- The EBNF below describes the source syntax of regular expressions.
-- That means, how we humans write and specify regular expressions.
-- R ::= 'x' | 'y' | ... alphabet symbols
-- | epsilon represents the empty string
-- | R + R alternatives
-- | R . R concatenation
-- | R* Kleene star
--- | (R) Grouping via parentheses
-- Example:
-- R1 = 'y' + ( ('z')* . 'x' )
-- R2 = 'y' + ('z')* . 'x'
-- Ambiguous!
-- Do we mean 'y' + (('z')* . 'x') or ('y' + ('z')*) . 'x'
{-
1. Assuming that "." binds tighter than "+", we could get rid of (some) parantheses.
2. In fact, "+" and "." are associative operators.
Can we get rid of all "(...)"?
Not quite, in case of Kleene star, it greatly helps to have "(...)" available.
For example, consider
(x + y)* versus x + y*
Short summary.
Assuming some "rules" (see 1. and 2. above), we can eliminate some "(...)",
but for us humans "(...)" are helpful to parse (recognize) regular expressions
and their intended meaning.
-}
-- How to represent the above syntactic description in Haskell?
-- In Haskell the natural way is to use data types.
-- In fact, any EBNF specification can be turned into a data type!!!
-- The data type below describes the *abstract* syntax of regular expressions.
-- For example, we no longer need "(...)". Why?
data R = Sym Char
| Alt R R -- the option would to be define Alt (R, R)
| Conc R R
| Star R {- deriving Show -}
-- Some examples.
-- Recall.
-- R2 = 'y' + ('z')* . 'x'
-- Ambiguous!
-- Do we mean 'y' + (('z')* . 'x') or ('y' + ('z')*) . 'x'
-- 'y' + (('z')* . 'x')
-- Observation:
-- It seems we couldn't get rid of "(...)"?
r3 :: R
r3 = let y = Sym 'y'
x = Sym 'x'
z = Sym 'z'
in Alt y (Conc (Star z) x)
r3b :: R
r3b = let y = Sym 'y'
x = Sym 'x'
z = Sym 'z'
r1 = Star z
r2 = Conc r1 x
in Alt y r2
-- deriving Show bit means the following.
-- Haskell automatically derives and instance of Show for the type R.
-- That means, the (overloaded) "show" function can be applied
-- to a value of type R and yields a String.
-- We wish to build our own instance of Show.
instance Show R where
-- show in this context is of type R -> String
-- In Haskell String = [Char]
show (Sym x) = [x]
-- Recall variables in patterns are non-linar (at most one occurrenc).
-- Hence, Alt r r is not legal.
show (Alt r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (Conc r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (Star s) = "(" ++ show s ++ ")" ++ "*"
-- HOMEWORK:
-- Add prededenc rules.
-- We assume that concatenation (".") binds tigher than alternatives ("+").
-- Instead of (y+((z)*.x))
-- we'd like to get y+(z)*.x
-- HINT: Need to adapt the above show definition.
-- Need some more involved pattern matching.
-- some examples
r1 = Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
r1b = (Sym 'y') `Alt` ((Star (Sym 'z')) `Conc` (Sym 'x'))
r1c = Alt (Sym 'y') $ Conc (Star (Sym 'z')) (Sym 'x')
{-
*Main> r1
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
1. Haskell evaluates r1 and applies "show" on this value.
2. Then, Haskell prints the resulting String to console.
In essence, Haskell evaluates the following piece of code.
*Main> putStrLn (show r1)
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
While we are here. I'm often using the "$" symbol.
Allows us to get rid of ( ... ).
If we just write
*Main> putStrLn show r1
yields a type error cause the above is interpeted as
(putStrLn show) r1
due to function application being left associative.
We can use "$" to separate function application and
thus it's "nicer" to write the above as follows.
*Main> putStrLn $ show r1
Alt (Sym 'y') (Conc (Star (Sym 'z')) (Sym 'x'))
Sample outputs.
*Main> r1
(y+((z)*.x))
-}
data RE a = SymRE a
| AltRE (RE a) (RE a)
| ConcRE (RE a) (RE a)
| StarRE (RE a)
re1 = AltRE (SymRE 'y') (ConcRE (StarRE (SymRE 'z')) (SymRE 'x'))
re2 = AltRE (SymRE True) (StarRE (SymRE False))
{-
-- Overlaps with instance Show a => Show (RE a) where
instance Show (RE Char) where
show (SymRE x) = [x]
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
-}
{-
*Main> :t re2
re2 :: RE Bool
If we only have "instance Show (RE Char) where"
then we get
*Main> re2
<interactive>:46:1: error:
• No instance for (Show (RE Bool)) arising from a use of ‘print’
• In a stmt of an interactive GHCi command: print it
because as the error message says,
we need an instance for (Show (RE Bool))
-}
{-
-- Overlaps with instance Show a => Show (RE a) where
instance Show (RE Bool) where
-- example of nested pattern matching
show (SymRE True) = "1"
show (SymRE False) = "0"
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
-}
{-
Now works!
*Main> :t re2
re2 :: RE Bool
*Main> re2
(1+(0)*)
-}
-- To be read as follows.
-- Given we have
-- Show a
-- we can provide an instance
-- Show (RE a)
instance Show a => Show (RE a) where
-- What we know about x?
-- Some value of type a. How to "show" x?
-- show x implies that we need Show a!
show (SymRE x) = show x
show (AltRE r s) = "(" ++ show r ++ "+" ++ show s ++ ")"
show (ConcRE r s) = "(" ++ show r ++ "." ++ show s ++ ")"
show (StarRE s) = "(" ++ show s ++ ")" ++ "*"
data SomeSigma = A | B | C deriving Show
re3 :: RE SomeSigma
re3 = ConcRE (SymRE A) (AltRE (SymRE B) (SymRE C))
-- You can't mix RE Char and RE Bool, e.g. consider
{-
re4 = ConcRE (SymRE True) (SymRE 'a')
PPSoSe21-W6.hs:215:28: error:
• Couldn't match type ‘Char’ with ‘Bool’
Expected type: RE Bool
Actual type: RE Char
• In the second argument of ‘ConcRE’, namely ‘(SymRE 'a')’
In the expression: ConcRE (SymRE True) (SymRE 'a')
In an equation for ‘re4’: re4 = ConcRE (SymRE True) (SymRE 'a')
|
215 | re4 = ConcRE (SymRE True) (SymRE 'a')
The definition of RE tells us that the alphabet, the type parameter a,
must be the same!
-}
-- The type keyword introduces a new type name and this type name
-- is a short-hand for the type on the right-hand side.
-- For example, we have that
--
-- type String = [Char]
--
-- Point to note. String is just an abbreviation of [Char].
type RList = [R]
-- Below type also works, but is more specific
-- showAllRegExesInSomeList :: RList -> String
-- Recall. The "type" keyword introduces shorthands!
-- The type below is equivalent to the type above.
-- showAllRegExesInSomeList :: [R] -> String
-- This is the most general type we can give to this function.
-- How to read this type.
-- In fact it's a "qualified type" (aka constrainted type).
-- The reason is as follows:
-- The part "[a] -> String" says
-- we expect a value that is a list whose elements are of type "a".
-- But, we also assume that all the elements come with a "show" function.
-- This part is specified via "Show a =>".
-- This states the pre-condition:
-- For type "a" we must have an instance of the "Show" class.
showAllRegExesInSomeList :: Show a => [a] -> String
showAllRegExesInSomeList rs = unlines (map show rs)
data List a = Nil
| Cons a (List a)
-- The below states,
-- we want to implement the show method for lists where
-- all the elements are of type "a".
-- That means, we also need to show these elements.
-- Hence, as a precondition, we require "Show a".
instance Show a => Show (List a) where
-- we only add brackets at the outer level
show xs = "[" ++ show2 xs ++ "]"
where
-- show the elements but don't add any brackets
-- add "," only if there are at least two elements in the list.
show2 Nil = ""
show2 (Cons x Nil) = show x
-- the last pattern only applies if xs is not Nil.
-- Recall, patterns are tried from top to bottom (textual order).
show2 (Cons x xs) = show x ++ "," ++ show2 xs
{-
-- we only add brackets at the outer level
-- but we require some post-processing,
-- need to take away the "last ,".
show xs = "[" ++ ys ++ "]"
where
-- drop the last element
ys = take (length (show2 xs) - 1) (show2 xs)
-- The below also works but is less efficient.
-- ys = reverse (tail (reverse (show2 xs)))
-- show the elements but don't add any brackets
show2 Nil = ""
show2 (Cons x xs) = show x ++ "," ++ show2 xs
-}
{-
-- There's no need to pattern match at the outer level!
show Nil = "[]"
show (Cons x xs) = "[" ++ (show x) ++ (show2 xs) ++ "]"
where
-- show the elements but don't add any brackets
show2 Nil = ""
show2 (Cons x xs) = show x ++ show2 xs
-}
{-
-- Partial, rather complicated attempt where we add brackets and
-- then at the recursive call we need to inspect the result and
-- get rid of the "extra" brackets.
show Nil = "[]"
show (Cons x xs) =
let ys = if show xs == "[]"
-- doesn't quite work out,
-- we need to check for the pattern "[....]".
-- In fact, there might be nested patterns "[ ... [ ...]...]".
then ""
else show xs
in "[" ++ (show x) ++ ys ++ "]"
-}"Fancy" types in Haskell
Lazy evaluation for code reuse
Intro to Monads and imperative programming
{-
Provided by the Prelude (Haskell standard library)
any :: Foldable t => (a -> Bool) -> t a -> Bool
It's an example of a "generic" function.
Java generics = We can abstract over some type parameters.
This is called (in more technical terms)
parametric polymorphism.
For example, consider the type of any.
We abstract over the types of the element.
We assume the elements are of some type "a".
We apply the predicate (first argument) on each element.
Hence, the type of the predicate is "a -> Bool".
The basic algorithm behind "any".
1. Iterate over all the elements.
2. Check if any element satisfies the predicate.
Over which data structures can we iterate?
1. Lists
2. ...
Obviously, there are many data structures that support iteration (scanning through the elements).
Haskell, uses another form of abstraction where
we make use of type classes + constructor polymorphism (= type constructor classes in Haskell).
For example,
Foldable t
refers to a type class called "Foldable" where the argument "t"
is a type constructor.
Examples of type constructors, e.g "[]".
Whenever we write the type "[Int]", internally this stands for "[] Int".
This is type application (similar to application at the value level).
Recall,
data List a = Nil | Cons a (List a)
where we write "List Int" for a list of integers.
-}
-- Let's define "any" for lists.
any2 :: (a -> Bool) -> [a] -> Bool
any2 _ [] = False
any2 p (x:xs)
| p x = True
| otherwise = any2 p xs
any3 :: (a -> Bool) -> [a] -> Bool
-- any3 p xs = or (map p xs)
any3 p = or . map p -- the same but shorter
msum [] = 0
msum (x:xs) = x + msum xs
main = do
print (msum [1..1000000000]) -- warning, leads to stack overflow
-- Pure vs impure
-- Monads in Haskell
-- IO is a Monad that deals with Input and Output Computations.
-- It's just a "thing" so we can distinguish pure from impure computations.
-- IO is a type constructors, has a type as an argument.
-- For example,
--
-- IO Int
--
-- represents an IO computation and as part of this computation
-- we obtain the result Int.
-- By default, Haskell is pure (expression-based).
-- So, we need a bit of extra syntax
-- to support impure (command-oriented) programming.
-- Consider
-- print :: Show a => a -> IO ()
-- Turns the input via show into a String,
-- and then "prints" the String onto the Console.
-- Doesn't yield a return value, but in Haskell we always
-- have a return value. We use "()" to indicate there's
-- no return value.
-- We need "return" to inject in our case x+1 into a IO computation.
-- When writing programs in "command-oriented" style,
-- we adopt the convention, one command per line,
-- so we won't need "{...}" and ";".
-- Attention: Commands need to be aligned properly!!!
foo :: Int -> Int
foo x = x + 1
foo2 :: Int -> IO Int
foo2 x = do print x
return (x+1)
foo2b :: Int -> IO Int
foo2b x = do { print x ;
return (x+1) }import Data.IORef
-- Pure vs impure
-- Monads in Haskell
-- IO is a Monad that deals with Input and Output Computations.
-- It's just a "thing" so we can distinguish pure from impure computations.
-- IO is a type constructors, has a type as an argument.
-- For example,
--
-- IO Int
--
-- represents an IO computation and as part of this computation
-- we obtain the result Int.
-- By default, Haskell is pure (expression-based).
-- So, we need a bit of extra syntax
-- to support impure (command-oriented) programming.
-- Consider
-- print :: Show a => a -> IO ()
-- Turns the input via show into a String,
-- and then "prints" the String onto the Console.
-- Doesn't yield a return value, but in Haskell we always
-- have a return value. We use "()" to indicate there's
-- no return value.
-- We need "return" to inject in our case x+1 into a IO computation.
-- When writing programs in "command-oriented" style,
-- we adopt the convention, one command per line,
-- so we won't need "{...}" and ";".
-- Attention: Commands need to be aligned properly!!!
foo :: Int -> Int
foo x = x + 1
foo2 :: Int -> IO Int
foo2 x = do print x
return (x+1)
foo2b :: Int -> IO Int
foo2b x = do { print x ;
return (x+1) }
{-
In-place update in C.
int inc(int* x) {
*x = *x + 1;
return *x;
}
Here comes a more verbose version.
int inc(int* x) {
int y = *x;
// y = y + 1;
int z = y + 1;
*x = z;
int tmp = *x;
return tmp; // return y + 1; // also works
// return *x;
}
We can only change the value if the value has a location in memory.
The above C example, makes this explicit, by passing a reference (memory location)
to the function.
Difference between C/Java and Haskell.
Haskell:
We can only change the state of a variable,
if the variable is "referenced".
Represented via a reference to some memory location.
Haskell:
You can't change the state of a variable introduced via "let" or "where"
-}
{-
impossibleInHaskell =
let x = True
x = False
in x
-}
inc :: IORef Int -> IO Int
inc x = do
v <- readIORef x -- readIORef is equivalent to the dereference operator "*" in C.
-- we can't write "v = readIORef x"
-- because "=" is reserved for pure assignment.
-- Haskell introduces instead "<-".
writeIORef x (v+1) -- we can't write " x = v+1", see above.
-- Haskell introduces writeIORef.
-- First argument x is a reference, and seconc argument (v+1) a value.
-- We overwrite the value stored at location x by the value (v+1).
-- return (v+1)
tmp <- readIORef x
return tmp
{-
int inc(int*);
// The above type declaration in C says:
// 1. The argument is a pointer to an int value.
// 2. The return type is an int.
inc :: IORef Int -> IO Int
// The above type declaration in Haskell says:
// 1. The argument is a pointer to an int value.
// 2. We return a value of type int,
// there's a computation taking place to compute this value.
// Here, we find a IO computation.
// IO computation may involve
// - dereferencing
// - overwriting the value stored in a reference
// - printing to the console
// ...
-}
run :: IO ()
run = do r <- newIORef 1
x <- inc r
print x
y <- readIORef r
print y