Learn You a Haskell For Great Good
I tried going through this book a few times when I was younger, but lacked the mathematical knowledge to understand a lot of what was going on. Now the functional ideas and type system are a breeze but lazinesss is still very new and mysterious.
Referential transparency: if a function is called multiple times with the same inputs, it will produce the same outputs.
Programs are a series of transformations on data.
ghci: haskell's REPL
negative numbers -3, must be wrapped in parens. (-3).
- is an infix function, not just an operator
function application has the highest precedence.
succ 9 + max 5 4 + 1
= 16
' is a convention for strict or slightly modified versions of functions.
Functions cannot begin with uppercase letters.
Functions which do not take parameters are called definitions.
Lists are homogenous in haskell.
++ concatenation.
: cons. 1:[2, 3, 4] = [1, 2, 3, 4]
[1, 2, 3] is syntactic sugar for 1:2:3:[]
car => head
cdr => tail
Are lists implemented as cons cells? That seems to be a poor choice.
Another infix example:
4 elem [3,4,5,6]
cycle takes a list and repeats it infinitely many times:
cycle [1, 2, 3]
= [1, 2, 3, 1, 2, 3, ...]
math set comprehensions {2 * x | x \n \N and x <= 10 } Wikipedia
output function: left side of the pipe input set: N predicate: x <= 10
so we take all elements from the input set, filter them by the predicate, and apply an output function.
Haskell: [x*2 | x <- [1..], x <= 10]
A fun example which is the cartesian product of nouns and adjectives.
let nouns = ["hobo", "frog", "pope"]
let adjectives = ["lazy", "grouchy", "scheming"]
[adjective ++ " " ++ noun | adjective <- adjectives, noun <- nouns]
["lazy hobo", "lazy frog", "lazy pope"... ]
A clever implementation of length:
length xs = sum [1 | _ <- xs]
Tuples have a fixed length and are not homogenous.
Assigining an index to a list of things:
zip [1..] ["apple" "orange" "cherry" "mango"]
use :t in ghci to inspect types :: "has type of"
typing out an example to get me familiar with the syntax:
removeNonUppercase :: [Char] -> [Char]
removeNonUppsercase ls = [ c | c <- ls, ls `elem` ['A'..'Z']]
Hmm, why are all paremeters just separated by ->? (My guess is currying, but lets see...)
addThree:: Int -> Int -> Int -> Int
addThree x y z = x + y + z
head :: [a] -> a a is not a type, its a type variable.
Polymorphic functions: functions with type variables.
Typeclasses generalize types. If a type is a member of a type class, then it it implements the behaviour it defines.
"Like java interfaces, only better."
:t (==)
(==) :: (Eq a) => a -> a -> Bool
Everything before => is called a class constraint. A must be mamember of the Eq class.
parens can be used to call an infix operator as prefix operator.
Explicit annotations:
read "5" :: Int
5
read "5" :: Float
5.0
factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)
Pattern matching is allowed to fail. You can have patterns which do not match. "non exhaustive patterns"
Pattern matching also works inside list comprehensions.
Pattern matching with the cons operator:
head :: [a] -> a
head [] = error "empty list, no head!"
head (x:_) = x
as patterns: xs@(x:y:ys) xs can still refer to the whole list, even though the pattern breaks it into pieces.
A way of handling different cases in a function.
Typing out an example to get familiar...
bmiTell :: (Float a) => a -> String
bmiTell bmi
| bmi <= 18.5 = "underheight"
| bmi <= 25.0 = "normal"
| bm <= 30.0 = "fat"
| otherwise = "hugEEE!"
Where clause is used to save values for usage in a guard. Both an optimizaiton and a code clarifier.
Let <bindings> in <expression>
Lets are expressions unlike where. Just like lisp, Lets can be used to define local functions.
Why not use let instead of where everywhere?
answer: let cannot be used across guards
function patterns are syntatic sugard for case
head :: [a] -> a
head [] = error "no head for empty lists"
head (x:_) = x
==
head :: [a] -> a
head xs = case xs of [] -> error "no head for empty lists"
(x:_) -> x
case <expr> of <pattern> -> <result>
<pattern> -> <result>
If you still don't know what recursion is, read this sentence
My attempt at writing this, just based on the name:
Lisp
(define (max ls)
(define (helper ls best)
(if (null? ls) best
(helper (cdr ls)
(if (> (car ls) best) (car ls) best))))
(helper ls -1))
max :: [a] -> a
max [] = error "empty list"
max [a] = a
max x:xs
| x >= max xs = x
| otherwise = max xs
- I felt like I needed a helper function to pass the max down the tail call chain.
- I need to learn more about tail call in haskell. Good SO answer
- I also calculated max twice.
- I need an ordering constraint in order to compare
Here is the real one:
max :: (Ord a) => [a] -> a
max [] = error "empty list"
max [x] = x
max x:xs
| x >= maxTail = x
| otherwise = maxTail
where maxTail = max xs
I like their take example. Another good one to type out.
take :: (Num i, Ord a) => i -> [a] -> [a]
take n _
| n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
A sorted list is a list that has all the values smaller than the head in front, then comes the head, and then come all values larger
My attempt:
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs)
let front = quicksort [y | y <- xs, y <= x]
behind = quicksort [y | y <- xs, y > x]
in front ++ [x] ++ behind
Just some minor syntax mistakes I fixed.
The illustration is beautiful. Here is it in symbolic form:
[5, 1, 9, 4, 6, 7, 3]
[1, 4, 3] ++ [5] ++ [9, 6, 7]
[] ++ [1] ++ [4, 3] [6, 7] ++ [9] ++ []
[3] ++ [4] ++ [] [] ++ [6] ++ [7]
a sum is the first element of a list plus the sum of the rest of the list a product of a list is the first element of a list times the product of the rest the length of a list is one plus the length of the tail
often the edge case turns out to be an identity
Of course, disguised underneath this is mathematical induction. This is natural property of all sets which can be corresponsed with the natural numbers.
Every function in Haskell officially only takes one parameter
Compare has a type of (Ord a) => a -> (a -> Ordering)
and calling it with 100 returns a (Num a, Ord a) => a -> Ordering
It looks like application is sort of reducing the chain by one link.
Lets expand this example:
applyTwice (multThree 2 2) 9
((2 * 2 * (2 * 2 * x))) => x = 9
= 144
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f x:xs y:ys = (f x y) : zipWith f xs ys
If the type declaration of a function says it accepts an
a -> b -> cfunction as a parameter, it will also accept ana -> a -> afunction.
Functional programming uses higher order functions to abstract away common patterns
A cool example:
flip' :: (a -> b -> c) -> (b -> a -> c)
flip' f = g
where g x y = f y x
A beautiful description of map
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Mapping and filtering is the bread and butter of every functional programmer's toolbox
An interesting example of partial application:
let listOfFuns = map (*) [0..]
This gives an infinite list of function which take one paramter and multiply them by a natural number.
(listOfFuns !! 4) 5
= 20
Lambda which multiplies two values. (\x y -> x * y)
People who are not well acquainted with how currying and partial application works often use lambdas where they don't need to.
Two equivalent definitions:
addThree :: (Num a) => a -> a -> a -> a
addThree x y z = x + y + z
addThree :: (Num a) => a -> a -> a -> a
addThree = \x -> \y -> \z -> x + y + z
Lambdas can pattern match, but they can't have multiple patterns.
Another helpful diagram:
(\accum x -> accum + x) 0 [3, 4, 2, 1]
0 + 3
[3, 4, 2, 1]
3 + 4
[4, 2, 1]
7 + 2
[2, 1]
9 + 1
[1]
10
[]
Left fold: (\acc x -> ...) Right fold: (\x acc -> ...)
$ is function application with really low precedence.
sqrt $ 3 + 4 + 9 vs sqrt 3 + 4 + 9
The definition of the function composition operator is perfectly mathematical!
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
point free style (or pointless style):
A Haskell module is a collection of related functions, types and typeclasses.
Syntax: import Data.List
all the functions that Data.List exports become available in the global namespace
Selective import: import Data.List (nub, sort)
Import keeping it inside a namespace: import qualified Data.Map as M
A great way to pick up new Haskell knowledge is to just click through the standard library reference and explore the modules and their functions.
if you ever get stack overflow errors when doing lazy folds, try switching to their strict versions. This comment alone suggests it is difficult to reason about laziness.
The most obvious way to represent association lists in Haskell would be by having a list of pairs.
Lisp:
((BETTY . "555-2938") (BONNIE . "452-2928") (PATSY . "493-2928"))
Haskell:
[("Betty", "555-2938"), ("Bonnie", "452-2928"), ("Patsy", "493-2928")]
takes a key, a value and a map and returns a new map that's just like the old one, only with the key and value inserted.
I wonder how ineffecient a full copy is in practice?
Like sets from mathematics
intersections, unions, etc
At the top of the file do something like this:
module Geometry
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where
It looks like haskell allows definitions and usage to be in any order.
data types: define a type according to the values it can have.
value contructors: function which constructs a data type from parameters.
value constructors are not types. They cannot appear in type listings. They can however appear in patterns.
data Bool = False | True
interesting, so its a set like \Z or \R.
Record syntax is for when positional arguments get too combersome.
data Person = Person { firstName :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, flavor :: String
} deriving (Show)
A value constructor can take some values parameters and then produce a new value. type constructors can take types as parameters to produce new types
data Maybe a = Nothing | Just a
never add typeclass constraints in data declarations
Why?
If we put or don't put the
Ord kconstraint in the data declaration forMap k v, we're going to have to put the constraint into functions that assume the keys in a map can be ordered. But if we don't put the constraint in the data declaration, we don't have to put(Ord k) =>in the type declarations of functions that don't care whether the keys can be ordered or not.
Ok, so put them in the functions that need them, not the data declarations.
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
deriving (Eq, Ord, Show, Read, Bounded, Enum)
Odd that you have to explicity specifify which it implements, instead of it naturally conforming to different interfaces.
Don't define new types, they just define new names for types. (Perhaps like typedef in C?)
type String = [Char]
He uses it as a sort of Hungarian notation to define a type in terms of another primitive:
type PhoneNumber = string
I will have to ask Kyle if this is idiomatic.
Type synonyms can also be parameterized.
data List a = Empty | Cons a (List a)
You can think of an I/O action as a box with little feet that will go out into the real world and do something there (like write some graffiti on a wall) and maybe bring back some data.
If we want to deal with impure data, we have to do it in an impure environment. So the taint of impurity spreads around much
The last action cannot be bound to a name.
I/O actions can still be claled recursively.
return in Haskell is really nothing like the return in most other languages. it makes an I/O action out of a pure value.
return doesn't exit early.
each chunk has a size of 64K. So if you evaluate a byte in a lazy bytestring (by printing it or something), the first 64K will be evaluated. After that, it's just a promise for the rest of the chunks.
Protip: it really helps to first think what the type declaration of a function should be before concerning ourselves with the implementation and then write it down. In Haskell, a function's type declaration tells us a whole lot about the function, due to the very strong type system.
https://wiki.haskell.org/Name_clashes_in_record_fields https://mail.haskell.org/pipermail/haskell-cafe/2008-September/048296.html