exam1 342

- when there is exactly one recursive call and its return value is immediately returned by the calling function
- compilers in Haskell turns tail recursion to a loop
- recursion allows Haskell to run without using loops, runs in constant space
- transform a recursive function into a tail recursive function using accumulating parameters
fact_acc(n-1,n*f)

- tail recursive
- combines elements from the left
foldl (+) 0 [1,2,3] =
((0+1)+2)+3)

- not tail recursive
- combines elements from the right
foldr (+) 0 [1,2,3] =
1+(2+(3+0))

- applies a function to every element in the list
map(:"") "Hi!" =
["H","i","!"]

- puts two list together
- must be the same type
(++) :: [a] -> [a] -> [a]
[1,2,3]++[4,5] =
[1,2,3,4,5]

- evaluation of expressions has no side effects
- has immutable variables unlike c where there are mutable variables

- consists of specifying patterns to which some data should confirm and then do an operation
product [] = 1
product (x:xs) = x * product xs

- algebraic data types in particular co-products

- means "or"
data Gender = Female | Male
- this means the gender data type has two constants, either female or male

- means "and"
Data Person = Person String Int Gender
- this means that the person data type has 3 components, an string, an int, and a gender
Consider the Haskell function definitions
const x _ = x

- will return 101
- x and _ are both arguments
- const will always ignore the right argument because of the definition given to us const x _ = x
- we evaluate the function as:
(const (1+) 10) 100
(1+) 100
101
Consider the Haskell function definition
const x _ = x

- const :: a -> b -> a
- must return the same type
Consider Haskell function definition
const x _ = x
Evaluate the Haskell expression

- foldr (const (1+)) 0 [2,1,3] =
const(1+) 1
const(1+)2
const(1+)3
const(1+)0
- const ignores the second argument so this will only evaluate to 1+1+1 = 3
What does the function

- flattens a list of lists
[[a]] -> [a]
foldr (++) [] ["abc","def","xyz"] =
"abc"++"def"++"xyz"
== "abcdefxyz"

- examples of data constructor are : (cons) and [] (nill)
Data Person = Person String Int Gender
- Person on the left of the equal sign is a type constructor and the person on the right is the data constructor

- a sort of interface that defines some behavior, if a type is a part of a typeclass, that means that it supports and implements the behavior the typeclass describes
- they are not classes, but are like interfaces
- Type Classes define a set of functions that can have different implementations depending on type of data they are given

- consists of both products and co-products
data List a = Nil | Cons a (List a)
- A list of elements type a is either nil or a cons (constructor), this is co-product
- the cons has two arguments "a (List a)", this is our product
"a" is a type variable and list a is a list of elements of type a
- List a is the type recursion because we are using the type in its own definition, not a recursive function because it has the data keyword
- Nil and Cons are the data constructors
- List is the type constructor
- in C we use null pointers instead of co-products

- if, else if, and else statments
- written as:
absolute x
| x < 0 = -x
| otherwise = x

List1 = 1 : (2 : (3 : []))

A function in C that gives a pointer a specified amount of memory, call free() after to reallocate the memory, prevents memory leak

-- A binary tree data structure
data Tree a = Tip | Branch (Tree a) a (Tree a) deriving Show


-- Tree traversal

-- Traverse in order
inOrder :: Tree a -> [a]
inOrder Tip = []
inOrder (Branch l a r) = inOrder l ++ [a] ++ inOrder r

test = Branch Tip 5 Tip

-- Traverse in order by making our trees foldable
instance Foldable Tree where
foldr f z Tip = z
foldr f z (Branch l m r) = foldr f (f m (foldr f z r)) l

-- toList = foldr (:) []


-- Insert an element into a sorted tree
insert :: Ord a => a -> Tree a -> Tree a
insert a Tip = Branch Tip a Tip
insert a (Branch l p r) | a <= p = Branch (insert a l) p r
| otherwise = Branch l p (insert a r)

-- Convert a list to a sorted tree
toTree :: Ord a => [a] -> Tree a
toTree = foldr insert Tip

-- Use our tree data structure for sorting
sort :: Ord a => [a] -> [a]
sort = toList . toTree