Haskell Notes
- References
- Lists
- Not Equals
- Ranges
- Data Types (a.k.a Algebraic Data Types)
- Notation
- Basic Types
- Type Variables
- Typeclasses
- Common Typeclasses
- Explicit Type Annotations
- Number Conversions
- Parametric and Ad-hoc Polymorphism
- Data Types
- Derived Types
- Record Syntax
- Data Type Constructors and Type Parameters
- Type Synonyms
- Partially Apply Type Params
- Recursive Data Type
- Typeclasses
- Modules
- Handy Modules
- Defining Functions
- Functions associate to the left
- Infix Functions
- Function Application using
- Conditional expressions
- Guarded expressions
- Pattern Matching
- As Patterns
- Where syntax
- Let expressions
- Case expressions
- Currying and Partial Function Application
- Higher Order Functions
- Recursion
- foldr
- foldr vs foldl
- Dollar Sign ($)
- List Comprehensions
- Tuples
- Lazy Evaluation
- Type Conversion
- GHCI
- Hugs
- Compiling and Running Haskell code
References
Lists
[1,2,3]
is syntactic sugar for 1:2:3:[]
. []
is an empty list.
Use !!
to get an element out of a list by index
[1,2,3] || 0
--> 1
To combine lists, use ++
. This will put the 2nd list on the end of the first list.
['w','o'] ++ ['o','t']
Note: the ++
operator will need to walk thru all elements in list on left side.
To put something on the beginning of a list, use the cons
operator :
'w' : ['o','o','t']
'w' : "oot"
Note: putting element on front of list is instantaneous
Common List Functions
[3,2,1] > [2,1,0]
True
[3,2,1] > [2,1,100]
True
[3,4,2] > [3,4]
True
[3,4,2] == [3,4,2]
True
head [5,4,3]
5
tail [5,4,3]
[4,3]
last [5,4,3]
3
init [5,4,3]
[5,4]
length [5,4,3]
3
null [1,2,3]
False
null []
True
reverse [5,4,3,2]
[2,3,4,5]
take 3 [5,4,3,2]
[5,4,3]
-- take 0 get an empty list
take 0 [5,4,3]
[]
-- take more than elements than in the list, the list is returned
take 5 [1,2]
[1,2]
maximum [5,7,3,2]
7
minimum [5,7,3,2]
2
Other list fn's: sum
, product
, elem
Not Equals
use /=
(unlike most other languages that use !=
)
> 13 /= 13
False
Ranges
-- even numbers
[2,4..20]
-- lowercase letters
['a'..'z']
-- decrementing list
[20,19..1]
-- infinite lists
take 10 [13,26..]
[13,26,39,52,65,78,91,104,117,130]
See also: cycle
, repeat
, replicate
.
Data Types (a.k.a Algebraic Data Types)
Notation
The notation v :: T
means that v is a value in the Type T. v "has the type" T.
False :: Bool
True :: Bool
not :: Bool --> Bool
Basic Types
Bool
:: can beTrue
orFalse
Char
:: a list of chars is a string'a', 'A', '3', '_'
String
:: a list of chars"abc", "1+2=3"
Int
, Fixed Precision Int :: The Hugs system supports int values in the range of -231 to 231-1.Integer
, Arbitrary Precision Int :: use as much memory as necessary for their storage. Slower performance than Fixed Precision, but no limits.Float
:: a real floating point with single precisionDouble
:: a real floating point with double the precision- Lists :: Lazily evaluated so it's not uncommon for a list to have infinite length. The syntax [1,2,3,4] is shorthand. Under the hood, the literal syntax for lists is
(1 : (2 : (3 : (4 : []))))
. The colon:
meansconstruct
orcons
. - Tuples :: Tuples can contain any number of components which is called arity. Tuple with 0 arity is the empty tuple, tuples with arity two are called pairs, tuples of arity 3 are called triples. Tuples with arity 1 are not valid (because parens are used to disambiguate operator precedence). Tuples must have finite arity.
Type Variables
Type Variables are sort of like generics in other languages. Functions that have Type Variables are called polymorphic functions
.
> :t head
head :: [a] -> a
Type variables must be lowercase. They can be longer than a single letter, but usually single chars are used.
Typeclasses
Sort of like an interface that defines some behavior. Think of them like Java Interfaces, but better.
> :t (==)
(==) :: Eq a => a -> a -> Bool
Everything before =>
is called a class constraint
.
Common Typeclasses
Eq
:: members implement==
and/=
Ord
:: types that have ordering.Ord
covers all the comparison functions (<
,>
,<=
, and>=
)Show
:: theshow
presents things as stringsRead
:: theread
function takes a string and returns a member ofShow
Enum
:: members are sequentially ordered types. Can useEnum
types in rangesBounded
:: members have upper and lower bound. UseminBound
andmaxBound
Num
:: numeric typeclass. Members can act like numbers. Members ofNum
must also be members ofShow
andEq
. Members includeInt
,Integer
,Float
, andDouble
Integral
:: includes whole numbers.Int
andInteger
are members ofIntegral
typeclass.Floating
:: Includes typesFloat
, andDouble
Explicit Type Annotations
The read
function can't infer which type you want when you do something like read "4"
. Do you want a Int? Integer? Char? Double?
Use explicit type annotations like so
read "4" :: Int
Number Conversions
It's possible to write a function that uses an argument that must have 2 conflicting types (such as Integral and Fractional). It took me a while to understand why this didn't work. Here's my stack overflow post.
What's the difference between Num and Integral? Awesome explanation here: https://www.haskell.org/tutorial/numbers.html
Parametric and Ad-hoc Polymorphism
The type for the function id
is id :: a -> a
which contains an unconstrained type variable a
. This means this function can be used in contexts requiring Char -> Char
or Integer -> Integer
or many other contexts. This is referred to as "Parametric Poloymorphism".
The type class Eq
defines the function ==
. The lookup
function, for example, constrains the type variable a
to be of type class Eq
in the type definition
lookup :: Eq a => a -> [(a,b)] -> Maybe b
This is referred to as "ad hoc" polymorphism or "overloading". Meaning that ==
is a funciton defined differently for different types.Data Types
One way to make new Data Types is to use data
.
data Bool = False | True
Types can have constructors.
data Shape = Circle Float Float Float | Rectangle Float Float Float Float
The Circle
value constructor has 3 Float arguments. Value constructors are functions that return value of a Data Type. This is sort of strange because Value constructors represent values of Types, not Types!
Derived Types
Use the deriving
keyword to associate a Data Type with a Type Class. For example:
data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)
Record Syntax
data Person = Person { firstName :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, flavor :: String
} deriving (Show)
All types inside value constructors must be compatible with the typeclass. For example, the person type can derive Show because String, Int, Float already implement Show.
Data Type Constructors and Type Parameters
Sort of like generics in java
data Maybe a = Nothing | Just a
Usually not a good idea to put type constraints in data declarations because then it might force functions to specify the type constraint even when the constraint is not applicable.
Type Synonyms
Use type
to associate new synonyms with existing types. This can improve intentions thru types.
For example:
type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]
Now we can do:
inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook
Partially Apply Type Params
You can partially apply type params and get new constructors (just the same as partially applying functions)
For example:
type IntMap v = Map Int v
is the same as:type IntMap v = Map Int v
Recursive Data Type
You can define data types recursively using the new type inside the definition.
Typeclasses
A Typeclass defines behavior. (Remember, Haskell Typeclasses are not the same as concept of classes in Java or Python). Haskell Typeclasses are more conceptually similar to clojure protocols or Java Interfaces.
Here's an example, the "Eq" Typeclass:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x == y = not (x /= y)
x /= y = not (x == y)
You can either use derives
keyword. Or, for more control, use the instance
keyword to associate a data type with a typeclass like so:
data TrafficLight = Red | Yellow | Green
instance Eq TrafficLight where
Red == Red = True
Green == Green = True
Yellow == Yellow = True
_ == _ = False
Note: usually, we'd have to implement both ==
and /=
, but we can get away with only implementing ==
in this case, because the class definition shows the relationship between ==
and /=
.
Beware of concrete types
vs type constructors
! Only concrete types can be used to define instances.
Kinds
Type of a Type is a Kind. Examine the kind of type using the :k
command in ghci. A *
means the type is a concrete type. A concrete type is a type that doesn't have an type parameters. Values can only have types that are concrete types.
Using :k
on a type to get it's kind is similar to using :t
on a value to get it's type.
Modules
Using Modules
Here's how to import modules from.hs
filesimport Data.List
import Data.set
Here's how to import modules from ghci
:m + Data.List Data.Set
Import specific functions from a module
import Data.List (nub, sort)
Import all functions except a few
import Data.list hiding (nub)
Use qualified
to Handle name clashes
import qualified Data.Map
Now we can access Data.Map.filter by fully qualifying. And still have access to Prelude's filter
.
To add an alias for a module
import qualified Data.Map :as M
Making Modules
A Module exports functions.
module Geometry.Equations
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where
-- function definitions here
The dot
notation in Modules must match the directory structure.
Exporting Type Definitions
You can include Data Types in Modules and export those as well
module Shapes
( Point(..)
, Shape(..)
, surface
, nudge
, baseCircle
, baseRect
) where
Handy Modules
Data.List
intersperse
(like join or interpose), intercalculate
(like join or interpose for lists), transpose
transforms 2d grid from columns to rows.
foldl'
and foldl1'
are strict version of the lazy foldl
and foldl1
.
concat
flattens (joins) a list. It will remove one level of nesting
concatMap
is same as first mapping a funciton and then concatenting the list.
and
, or
, any
, all
are predicates that operate on lists
iterate
takes function and starting value and applies the function to the result.
takeWhile
, dropWhile
do what you expect.
span
is kind of like takeWhile
except it returns pair of lists. break
will return pair of lists split at first value that returns true.
Other useful functions: sort
, group
, inits
, tails
, find
, elemIndex
, partition
, elem
and notElem
, partition
, and lots more!
Data.Char
Lots of predicates
isControl
, isSpace
, isLower
, isUpper
, isAlpha
, isUpper
, isAlpha
, isAlphaNum
, isPrint
, isAlphaNum
, isPrint
, isDigit
toUpper
, toLower
, toTitle
, digitToInt
.
Data.Map
Hashmap like structures, a.k.a. dictionaries, a.k.a association lists, a.k.a. key-value pairs
Import like so to avoid name clashes:
import Data.Map as Map
Map.fromList
converts list of key value Pairs into a internaldata structure.Map.empty
gives an empty map
Map.insert
takes a key and a value and a map and returns new map with the new key/value inserted
Map.null
checks if map is empty
Map.size
gets size of map
Some other useful functions: singleton
, lookup
, member
, map
, filter
, toList
, keys
, elems
fromListWith
and insertWith
help with transforming lists of pairs that might have duplicate keys.
Defining Functions
Functions can't begin with an uppercase letter.
When a function doesn't take parameters, it's often referred to as a definition (or a name).
Functions associate to the left
f x g y
means
(((f x) g) y)
This is the opposite of type declarations, which associate to the right.
Infix Functions
+, *, -
are examples of infix functions. You can use them as prefix functions by surrounding them with parenthesis.
2 + 2
(+) 2 2
Function Application using $
The $
operator has the lowest precedence. Normal function application (with a space) is left associative. Function application with $
is right associative. When $
is used, the expression on the right is applied as parameter to the function on it's left. So, for example, instead of this:
sum (map sqrt [1..10])
We can write:
sum $ map sqrt [1..10]
$
can also be used to map function application across functions
ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]
Conditional expressions
In Haskell, each if/then must have a corresponding else. if/then/else statements can be nested. if/then/else are expressions (meaning they always return a value)
safetail1 xs = if null xs then [] else tail xs
Guarded expressions
These are sort of like case or cond statements. Otherwise always evals to True.
safetail4 xs
| null xs = []
| otherwise = tail xs
Pattern Matching
Patterns are tested from top to bottom, so most general patterns should come last.
safetail [] = []
safetail xs = tail xs
Remember that pattern matching variables must be unique. But don'tconfuse this with variables inside type expressions (which can andoften are the same).You can Pattern Match in list comprehensions too
ghci> let xs = [(1,3), (4,3), (2,4), (5,3), (5,6), (3,1)]
ghci> [a+b | (a,b) <- xs]
[4,7,6,8,11,4]
Surround things with parens if binding multiple variables. Pattern match on lists too
head' [] = []
head' (x:_) = x
As Patterns
Place a name and a @
in front of a pattern in order to make reusable patterns. Here's an example:
capital :: String -> String
capital "" = "Empty string, whoops!"
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]
Where syntax
(note that where
is not an expression, it's syntactic sugar)
The names defined inside where
bindings are visible across guards. And names are only available inside the function (so won't pollute global namespace).
initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
where (f:_) = firstname
(l:_) = lastname
Let expressions
let
bindings are similar to where
bindings except they don't apply across all guards.
where
is syntactic sugar. let
is a first class expression (so they can be put anywhere).
ghci> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]
You don't need the in
part of the let
when in list comprehensions
calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]
Using let
to bind variables is convenient from the repl.
ghci> let foo x y z = x * y + z
ghci> foo 3 9 2
29
Case expressions
Case expressions and pattern matching are similar. Pattern Matching can only be used in function definitions. case
expressions can be used pretty much anywhere. Pattern matching in functions is syntactic sugar for case expressions.
describeList :: [a] -> String
describeList xs = "The list is " ++ case xs of [] -> "empty."
[x] -> "a singleton list."
xs -> "a longer list."
Currying and Partial Function Application
Haskell functions typically only accept a single parameter. Currying is the illusion of a function accepting multiple parameters. A function will accept a single param and return a function which accepts another param and so on.
This makes it easy to use partial function application. For example:
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x
compare
is a function that accepts a single param (in this case the arg is 100) and returns a function that accepts another param (in this case, x
). This can be re-written:
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100
Now compareWithHundred
returns a function that accepts another param.
Sections
(I don't really understand sections, other than they are a short hand for writing functions that take a single argument?)
Infix functions can be partially applied using sections.
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)
Lambda (Anonymous) Expressions
\x -> x + x
The backslash x
is Haskell's way of expressing a λ.
(\x -> x + 1) 4
5 :: Integer
It's also possible to define anonymous functions with arguments:
(\x y -> x + y) 3 5
8 :: Integer
Function Composition
A function f(x)
composed with a function g(x)
is the same as calling f(g(x))
.
In Haskell, use the .
operator to compose functions.
You can only compose functions that take same number of params
The .
can be used to write functions in Pointfree
style.
Note: Pointfree
has nothing to do with points (.
)! The Points
in Pointfree
has to do with the values that functions operate on.
For example:
-- not Pointfree
fn x = ceiling (negate (tan (cos (max 50 x))))
-- Pointfree version
fn = ceiling . negate . tan . cos . max 50
Higher Order Functions
Useful Higher Order Functions
map
, filter
, foldl
, foldl1
, foldr
, foldr1
, zipWith
scanl
, and scanr
are like foldl
and foldr
except that they report all intermediate accumulator states.
Recursion
- Think about the type
- Enumerate the cases
- Define simple cases. Usually this will be the base cases. For example the product of empty list of numbers is 1.
- Define other cases
- Generalize and Simplify
foldr
Nice way to think about foldr
is replacing each cons operator in a list by the function f
, and the empty list at the end by the value v
. For example, applying the function foldr (+) 0
to the list 1:(2:(3:[]))
gives the result 1+(2+(3+0))
foldr vs foldl
Note that the positional arguments for foldl
and foldr
have different meanings. foldl acc next
vs foldr next acc
where acc
is the accumulator value.
Dollar Sign ($)
The $ operator is for avoiding parenthesis. Anything appearing after it will take precedence over anything that comes before.
List Comprehensions
-- doubles of all natural numbers from 1 to 10
> [x*2 | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
-- with a predicate
> [x*2 | x <- [1..10], x*2 > 12]
[14,16,18,20]
Here's an example of using a list comprehension (and a lambda expression) to define a function named "evens".
evens = \xs -> [x | x <- xs, even x]
List comprehensions can operate on multiple lists.
> [ x*y | x <- [2,5,10], y <- [8,10,11]]
[16,20,22,40,50,55,80,100,110]
Tuples
A tuple of 2 elements is called a pair
. A tuple of 3 elements is called a triple
. A tuple of 4 elements is called a 4-tuple
.
[(1,2), (8,11), (4,5)]
You can compare 2 tuples as long as they're both the same size.
Useful functions for pairs include fst
, snd
.
zip
is a function that produces pairs.
> zip [1..] ["Bob", "Jenny", "Jake"]
[(1,"Bob"),(2,"Jenny"),(3,"Jake")]
Lazy Evaluation
There are multiple ways to evaluate an expression. Different Pieces of an expression that can be reduced are called reducible expressions
, or, redex
for short.
For example, the expression: (1+2)*(3+5)
contains 3 redexes: (1+2)
, (3+5)
, and (1+2)*(3+5)
.
Innermost Evaluation (call-by-value)
One way to evaluate expressions is to evaluate from innermost redex to outermost. If there are multiple innermost redexes, then evaluate from left to right. This is called call-by-value
.
- call-by-value is guaranteed to require the least number of reductionsteps.
- call-by-value doesn't always guarantee that an expression will terminate.
Outermost Evaluation (call-by-name)
Another way to evaluate expressions is to evaluate from outermost redex to innermost, moving from left to right. This is called call-by-name
.
- call-by-name has the nice property that if an evaluation can terminate, then call-by-name will ensure that it does terminate (whereas call-by-value might run infinitely).
- call-by-name might have to repeat steps, whereas call-by-value will always do the least number of steps.
But, we can work around the problem where call-by-name
might repeat steps by storing pointers to duplicate steps (and then only having to evaluate each step once).
Haskell uses call-by-name
in conjunction with sharing, a.k.a, lazy evaluation.
Type Conversion
Integer to String
map intToDigit (take 3 (repeat 9))
String to Integer
fst (head (reads "999" :: [(Integer, String)]))
GHCI
Display time and memory usage
:set +s
Hugs
Display results of IO
:set +I
Compiling and Running Haskell code
ghc --make file.hs
You can also use runhaskell
runhaskell file.hs