Cheatography

# 442 Cheat Sheet (DRAFT) by jenwwnewnw

just a midterm cheatsheet

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Basic Syntax

 ``null []`` return True if list is empty ``'H' `elem` "­Hel­lo"`` return True if H is in the string ``head [1,2,3]`` return 1 ``tail [1,2,3]`` return [2,3] ``last [1,2,3]`` return 3 ``init [1,2,3]`` return [1,2] ``:t`` return the type ``fst (5,2)`` return 5 ``snd (5,2)`` return 2 ``1:2:3:[]`` same as [1,2,3] ``length []`` give length of list ``reverse []`` reverse the list ``[] !! n`` gives the nth element ``filter test []`` return everything that passes the test ``[] ++ []`` list concat­enation ``[] : []`` list concat­enation ``drop n []`` delete the first n element from list ``take n []`` make a new list containing just the first N element ``splitAt n []`` split list into two lists at nth position ``zip [a..] [0...]`` combine tow list into tuples [(a,0]..] ``map function [[]`` apply a function to all list elements

### Termin­ology

 Polymo­rphic Types Families of types. For example, (forall a)[a] is the family of types consisting of, for every type a, the type of lists of a. Lists of integers (e.g. [1,2,3]), lists of characters (['a',­'b'­,'c']), even lists of lists of integers, etc., are all members of this family. Type Variable Lower case, can be of any type. e.g. fst::(a,b)->a Typeclass A sort of interface that defines some behavior. Basic type classes: Read, Show, Ord, Eq, Enum, Num. Num includes Int, Integer, Float, Double. Higher­-or­dered Functions A function that takes other functions as arguments or returns a function as result. Ex: foldl, folder­,zi­pWith, flip. Module A collection of related functions, types and typecl­asses Refere­ntial Transp­arency An expression is called refere­ntially transp­arent if it can be replaced with its corres­ponding value without changing the program's behavior. substi­tuting equals for equals, different from other programing languages

### Type Signatures

 In type signature, specific (String) and general (a,b) types can be mixed and matched. ``concat­3::­Str­ing­->S­tri­ng-­>St­rin­g->­String`` ``concat3 x y z = x++y++z`` ``const :: a->­b->a`` ``const x y = x`` ``allEqual :: (Eq a) => a -> a -> a -> Bool`` ``allEqual x y z = x == y && y == z`` ``(.)::(­b->­c)-­>(a­->b­)->­a->c`` ``f.g = \x-> f (g x)`` ``(\x->1­0+x)5`` Lambda function, lead with \, then arguments, then ->, then the comput­ation

### Data Types

 Haskell uses various data types, all of them starts by a capital letter: -Int: Integer number with fixed precision -Integer: Integer number with virtually no limits -Float: Floating number -Bool: Boolean. Takes two values: True or False. -Char: Character. Any character in the code is placed between quotes ('). -String: Strings (In fact, a list of Chars).

 Pure No side effects in functions and expres­sions No assignment operators such as ++ and =+ I/O is an exception Promotes refere­ntial transp­arency Once x is assigned to a value, the value stays Functional Use recursion instead of iteration Allows operations on functions Lazy Don't do an operation unless you need the result.

### Recursive Descent Parser

 ``````-- our parsers generally are of type Parser [Ptree] data Ptree = VAR String | ID String | FCN String [Ptree]     deriving (Show, Eq, Read) data Presult a = FAIL | OK a String deriving (Show, Eq, Read) type Parser a = String -> Presult a -- As before, we use &> and |> as AND / OR combinators on parsers expr = variable |> fcnCall |> identifier fcnCall = buildCall . (identifier &> skip "(" &> arguments &> skip ")") arguments = expr &> argTail |> empty argTail = skip "," &> expr &> argTail |> empty identifier input = beginsWith ID Data.Char.isLower isTailChar (dropblank input) variable input = beginsWith VAR Data.Char.isUpper isTailChar (dropblank input) empty = OK [] -- empty string parser always succeeds --------------------------------- -- UTILITY ROUTINES -- Parse a string but don't save it as a parse tree skip :: String -> Parser [a] skip want input =     let found = take (length want) input         remainder = dropblank (drop (length want) input)      in         if want == found then OK [] remainder         else FAIL -- Build a singleton list of a function call parse tree from a list with -- an identifier followed by list of arguments buildCall :: Presult [Ptree] -> Presult [Ptree] buildCall FAIL = FAIL buildCall (OK [] _) = FAIL buildCall (OK (ID fcn : args) remainder) = OK [FCN fcn args] remainder -- Build a singleton list of a parse tree given the kind of tree we want -- and the kinds of head and tail characters we want beginsWith :: (String -> Ptree) -> (Char -> Bool) -> (Char -> Bool) -> Parser [Ptree] beginsWith _ _ _ "" = FAIL beginsWith builder isHead isTail (c:cs)     | isHead c = let tail = Data.List.takeWhile isTail cs                   in OK [builder (c:tail)] (dropblank (drop (length tail) cs))     | otherwise = FAIL -- Remove spaces (and tabs and newlines) from head of string. -- dropblank :: String -> String dropblank = Data.List.dropWhile Data.Char.isSpace -- kind of character that makes up 2nd - end character of an id or var -- isTailChar :: Char -> Bool isTailChar c = Data.Char.isAlphaNum c || c == '_' ------------------------------- -- Concatenation and alternation operators on parsers -- (|>) is an OR/Alternation operator for parsers. -- infixr 2 |> (|>) :: Parser a -> Parser a -> Parser a (p1 |> p2) input =     case p1 input of         m1 @ (OK _ _) -> m1 -- if p1 succeeds, just return what it did         FAIL -> p2 input -- (&>) is an AND/Concatenation operator for parsers infixr 3 &> (&>) :: Parser [a] -> Parser [a] -> Parser [a] (p1 &> p2) input =     case p1 input of         FAIL -> FAIL -- p1 fails? we fail         OK ptrees1 remain1 ->             case p2 remain1 of -- run p2 on remaining input                 FAIL -> FAIL -- p2 fails? we fail                 OK ptrees2 remain2 -> -- both succeeded                     OK (ptrees1 ++ ptrees2) remain2``````

### Tree

 ``data Tree a = Leaf a | Branch a (Tree a) (Tree a) deriving (Eq, Show)`` ``treeEq :: (Eq a) => Tree a -> Tree a -> Bool`` ``treeEq (Leaf x) (Leaf y) = x == y`` ``treeEq (Branch x1 l1 r1) (Branch x2 l2 r2) = x1 == x2 && treeEq l1 l2 && treeEq r1 r2`` ``treeEq _ _ = False`` treeShow ``treeShow :: Show a => Tree a -> [Char]`` ``treeShow (Leaf x) = "­(Leaf " ++ show x ++ "­)"`` ``treeShow (Branch x left right)= "­(Branch " ++ show x ++ " "++ treeShow left ++ " "++ treeShow right ++ "­)"`` Preorder via standard recursion ``preorder :: Tree a -> [a]`` ``preorder (Leaf x) = [x]`` ``preorder (Branch x left right)= x : preorder left ++ preorder right`` Tail-r­ecu­rsive traversal ``preorder' :: Tree a -> [a] -> [a]`` ``preorder' (Leaf x) xs = x : xs`` ``preorder' (Branch r left right) xs= r : preorder' left (preorder' right xs)``

### Function Syntax

 ``````addFour w x y z =  let a = w + x      b = y + a  in z + b ----------------------- addFour w x y z =   z + b  where   a = w + x   b = y + a ----------------------- fib n   | n < 2 = 1   | otherwise = fib (n - 1) + fib (n - 2) ----------------------- fib n =   case n of     0 -> 1     1 -> 1 ----------------------- fib n =   if n < 2    then 1    else fib (n - 1) + fib (n - 2) ---------------------- nameReturn :: IO String nameReturn = do putStr "What is your name? "                 name <- getLine                 putStrLn ("Pleased to meet you, " ++ name ++ "!")                 return full``````

### Regex

 . Any character except new line (\n) \w Word * 0 or more \S Not white space + 1 or more \s White space ? 0 or 1 \W Not word {3} Exactly 3 \d Digit {3,} 3 or more \D Not digit {3,5} 3, 4 or 5 \b Word boundary ^ Beginning of String \B Not word boundary \$ End of String [^ ] matches characters NOT in bracket [ ] matches characters in brackets | Either Or ( ) Group ε Empty string containing no characters
^ [ . \$ { * ( \ + ) | ? < >
Matech­ara­cters need to be escaped

### Currying

 Currying is the process of transf­orming a function that takes multiple arguments in a tuple as its argument, into a function that takes just a single argument and returns another function which accepts further arguments, one by one, that the original function would receive in the rest of that tuple. from ``g :: (a, b) -> c`` to ``f :: a -> (b -> c) `` ``f :: a -> (b -> c) `` is the same as ``f :: a -> b -> c `` `` g (x,y) = x + y `` is an uncurried function, has the type ``g :: Num a => (a, a) -> a`` `` h x y = x + y`` is a curried addition, has the type ``h :: Num c => c -> c -> c`` ``curry g`` can convert it to a curried function

### Fold List

 Foldl takes a binary operation, a starting value, and the list to fold ``foldl (-) 0 [3,5,8]`` => `` (((0 - 3) - 5) - 8)`` => ``-16`` foldl and foldr is under the type class ``Foldable`` ``foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b`` ``foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b``
``elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys``

### Notes

 ``head_r­epeats n x = (take n x) == (take n (drop n x))`` returns True if the first n elements of x equals the second n elements of x.If n ≤ 0, return True. ------­---­---­---­---­---­---­---­---­----- ``swap_ends [] = []`` ``swap_ends [y] = [y]`` ``swap_ends x = last x : (reverse (drop 1 (reverse (drop 1 x))))++ [head x]`` Define a function swap_ends that takes a list and returns the same list but with the first and last elements swapped. ------­---­---­---­---­---­---­---­---­----- iterate via standard recursion ``iterate1 n f`` `` | n <= 0 = id`` ``| otherwise = f . (iterate1 (n-1) f)`` iterate via foldl ``iterate2 n f = foldl (.) id [f | i <- [1..n]]`` ------­---­---­---­---­---­---­---­---­----- ``f1a :: (b, a) -> (a, b)`` ``f1a = \(x, y) -> (y, x)`` ``f1b :: a -> [a] -> [[a]]`` ``f1b = \x y -> [[x], y]`` ``f1c :: a -> a -> [a] -> [[a]]`` ``f1c = \x y z -> [x : z, y : z]`` ``f1d :: (a -> Bool) -> [a] -> Int`` ``f1d f = length . (filter f)``
``(:) :: a -> [a] -> [a]``

``(++) :: [a] -> [a] -> [a]``

``++``
is only used for list concat­ena­tion, whereas
``:``
is used for joining element with lists

Num class does not support /, Fractional does

### Pattern Matching

 ``(x:xs)`` head x and tail xs ``(x:3:xs)`` list where 2nd element is 3 ``myData a _ c`` ignore one of the component ``data Pattern a = P a | POr (Pattern a) (Pattern a)| PAnd (Pattern a) (Pattern a) deriving Show``
``match pattern [] = (False, [])``

``match (P x) (y : ys) = if x == y then (True, ys) else (False, y : ys)``

``match (POr pat1 pat2) xs`` =case match pat1 xs of``

``(True, leftover) -> (True, leftover)``

``(False, _) -> match pat2 xs``

``match (PAnd pat1 pat2) xs`` =case match pat1 xs of ``

`` (False, _) -> (False, xs)``

``(True, leftover) ->case match pat2 leftover of ``

``(False, _) -> (False, xs)``

``(True, leftover2) -> (True, leftover2)``

### Regex Examples

 ``Natural numbers with no leading zeros except just 0`` 0 | [1-9] \d* ``Floating point numbers w/o leading zeros`` (0 | [1-9] \d*.\d* | . \d+)?([eE][+-]?[0-9]+)) ``Hex numbers allowing leading zeros`` 0x[0-9a-fA-F]+ ``Strings with an even #a's or number ofb's divisible by 2`` (b*ab*a)*b*|(a*ba*ba*b)*a*

### Match regular expres­sions using backtr­acking

 ``````data RegExp = Rnull             | Rend             | Rany             | Rch Char             | Ror RegExp RegExp             | Rand RegExp RegExp             | Ropt RegExp             | Rstar RegExp             deriving (Eq, Show) data Mresult = FAIL | OK String String deriving (Eq, Show) match :: RegExp -> String -> Mresult match Rnull str = OK "" str match Rend "" = OK "" "" match Rend str = FAIL match Rany "" = FAIL match Rany (c : cs) = OK [c] cs match (Rch ch1) "" = FAIL match (Rch ch1) (str @ (ch2 : left))     | ch1 == ch2 = OK [ch1] left     | otherwise = FAIL match (Ror exp1 exp2) str =     case match exp1 str of         FAIL -> match exp2 str         result1 @ (OK match1 remain1) ->             case match exp2 str of                 FAIL -> result1                 result2 @ (OK match2 remain2) ->                     if length match1 >= length match2 match (Rand exp1 exp2) str =     case match exp1 str of         FAIL -> FAIL         ok @ (OK match1 remain1) ->             extend match1 (match exp2 remain1) match (Ropt exp) str = match (Ror exp Rnull) str match (Rstar exp) str =     case match exp str of         FAIL -> OK "" str         OK match1 remain1 ->             if match1 == "" then OK "" str             else                 extend match1 (match (Ror (Rstar exp) Rnull) remain1) extend match1 (OK match2 remain2) = OK (match1 ++ match2) remain2 extend match1 FAIL = FAIL -- mkAnd string = the exp that matches each character of the string in sequence. -- mkAnd (c : "") = Rch c mkAnd (c : cs) = Rand (Rch c) (mkAnd cs) -- mkOr (c : "") = Rch c mkOr (c : cs) = Ror (Rch c) (mkOr cs)``````

### More Examples

 ``````(Find out whether a list is a palindrome) isPalindrome'' :: (Eq a) => [a] -> Bool isPalindrome'' xs = foldl (\acc (a,b) -> if a == b then acc else False) True input where input = zip xs (reverse xs) (Eliminate consecutive duplicates of list elements) compress :: Eq a => [a] -> [a] compress = map head . group (Count the leaves of a binary tree) countLeaves Empty = 0 countLeaves (Branch _ Empty Empty) = 1 countLeaves (Branch _ left right) = countLeaves left+ countLeaves right (User-Defined Polymorphic Lists) (a) Define the function foldList which acts on user-defined lists just as foldr acts on native lists. foldList :: (a -> b -> b) -> b -> List a -> b foldList f init Nil = init foldList f init (Cons x xs) = f x (foldList f init xs) (b) Define the function sumList which adds up the entries in an argument of type (List Int). sumList :: (List Int) -> Int sumList = foldList (+) 0``````

### Lecture 11

 ``````data ParseT = STR String | LIST [ParseT] deriving (Show, Eq, Read) data PResult = FAIL | OK [ParseT] String deriving (Show, Eq, Read) type Parser = String -> PResult type TreeBuilder = [ParseT] -> ParseT -- LIST, for these trees -- Note use of &> as AND and |> as OR list = parse LIST (skip "(" &> list &> sublist &> skip ")"                   |> skip "[" &> list &> sublist &> skip "]"                   |> identifier) sublist = (skip ",") &> list &> sublist |> empty identifier = literal "x" empty = OK [] -- empty string parser always succeeds -- expr = expr &> literal "+" &> identifier |> empty ---------------------------------------------------------------------- -- UTILITY ROUTINES -- Parse a string and make it a parse tree literal :: String -> Parser literal want input =     let found = take (length want) input         remainder = dropblank (drop (length want) input)      in         if want == found then OK [STR want] remainder         else FAIL -- Parse a string but don't save it as a parse tree skip want input =     case literal want input of         FAIL -> FAIL         OK _ remain -> OK [] remain -- Remove spaces from head of string dropblank = Data.List.dropWhile Data.Char.isSpace ---------------------------------- -- Concatenation and alternation operators on parsers -- (|>) is an OR/Alternation operator for parsers. -- infixr 2 |> (|>) :: Parser -> Parser -> Parser (p1 |> p2) input =     case p1 input of         m1 @ (OK _ _) -> m1 -- if p1 succeeds, just return what it did         FAIL -> p2 input -- (&>) is an AND/Concatenation operator for parsers -- infixr 3 &> (&>) :: Parser -> Parser -> Parser (p1 &> p2) input =     case p1 input of         FAIL -> FAIL -- p1 fails? we fail         OK ptrees1 remain1 ->             case p2 remain1 of -- run p2 on remaining input                 FAIL -> FAIL -- p2 fails? we fail                 OK ptrees2 remain2 -> -- both succeeded                     OK (ptrees1 ++ ptrees2) remain2 ------------------------------------------- -- Building a parse tree from list of found parse trees parse :: TreeBuilder -> Parser -> Parser parse builder parser input =     case parser input of         FAIL -> FAIL         (OK [] remain) -> OK [] remain         (OK trees remain) -> OK [builder trees] remain``````