Show Menu
Cheatography

442 Cheat Sheet (DRAFT) by

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).

Properties of Haskell

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