Skip to content

Instantly share code, notes, and snippets.

@LukasForst

LukasForst/functional.md

Last active June 2, 2019 10:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save LukasForst/4fb989f2bfae18ccd6585161e3e31f1c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save LukasForst/4fb989f2bfae18ccd6585161e3e31f1c to your computer and use it in GitHub Desktop.
Download ZIP
Functional programming sum up for SZZ
Raw
functional.md

Functional languages and their features

  • programming paradigm that treats computation as the evaluation of mathematical functions
  • aim to have no side effects -> this enables better parallelization and verification
  • output of a functions depends only on its inputs
  • no mutable data
  • generally speaking, they are less computationally efficient
  • ie - LISP is used in AutoCad or GImp

imperative programming

  • instructions to change the computer’s state
  • run program by following instructions top-down

Declarative / functional programming

  • functions used to declare dependencies between data values
  • expressions are evaluated -> run programme by evaluating dependencies

Recursion

  • first expression should be condition -> the first test is a termination condition
    • generally speaking it does not have to be the first condition, but it needs to be the first condition before calling next recursion iteration
  • each recursive call brings computations closer to the termination condition
  • analytic or synthetic recursion - return value from termination condition
  • tree or linear recursion - function is called recursively multiple times
  • indirect recursion - function A calls function B which calls A
  • tail recursion - you firstly perform calculations and then executes the recursive call
    • the recursion call needs to be the last instruction in the function
    • some compilers (JavaScript or Kotlin for example) can optimize the tail recursion using tail call optimization -> they compile it as it would be iterative calls that are executed faster

Higher order functions

  • functions taking other functions as arguments or returning functions as the result
  • basically passing the function to another function
  • used to capture/reuse common pattern and contexts
  • closure - technique for implementing lexically scoped name binding -> a record storing function together with an environment
  • curried functions - returned as result of the function
  • partially applied

Binding scopes

  • a portion of the source code where a value is bound to a given name -> ie problems with this in JavaScript
  • lexical scope
    • functions use bindings available where defined
  • dynamic scope
    • functions use binding available where executed

Scheme (LISP dialect)

  • calling function (fn arg1 arg2..argN)
  • ( - operator of calling a function
  • fn name of the function, or expression that evaluates to a procedure
  • #t and #f are booleans
  • it is possible to use mutable data structures -> not recommended

Conditions

  • if statements (if test-exp then=exp else-exp)
  • switch is called cond
(cond 
    (test-exp1 exp)
    (test-exp2 exp)
    (#t exp)
)

Syntax

  • car returns first element of pair, cdr second
  • everything is represented as linked list of pairs
  • null test null?
  • (lambda (arg1 .. argN) <expr>)
  • define new function (define (name args) <body>)
  • let can store data as lambda
  • foldr and foldl -> fold right/left

foldl and foldr expr

Evaluation strategy

  • order of evaluating the expressions
  • eager (functions) - evaluate all arguments before execution
  • lazy (lambda expressions, if, and, or)
    • useful for streams (potentially infinite lists)
  • promise - delayed evaluation with indication whether it was evaluated or not
    • it is used in futures where the evaluation is started and future indicates whether was finished or not

Haskell

  • purely functional (with IO exception), rich syntax sugar
  • Glasgow Haskell Compiler (GHC) -> Haskell compiler, written in Haskell
  • Everything has a type known in compile time

Syntax

  • basic data structure is list -> cons or `[1,2,3]
    • unlike Scheme it supports indexing by !!
    • has functions such as take, length, reverse
  • example application here
data Token = Mult | Add | Num Integer deriving (Show, Eq)

interp :: [Token] -> [Integer] -> Integer
interp ((Num x):tl) s = interp tl (x:s)
interp ((Add):tl) (a:b:ts) = interp tl (a + b : ts)
interp ((Mult):tl) (a:b:ts) = interp tl (a * b : ts)
interp _ s = head s

parse :: String -> Token
parse "*" = Mult
parse "+" = Add
parse x = Num (read x :: Integer)

split :: String -> Char -> [String]
split [] _ = [""]
split (x:xs) c = let rest = split xs c in if x == c then "" : rest else (x : head rest) : tail rest

calculator :: String -> Integer
calculator s = interp (map parse (split s ' ')) []

main :: IO()
main = do 
    s <- getLine
    putStrLn (show (calculator s))
main
  • guarded expressions
    bmiTell :: (RealFloat a) => a -> String  
    bmiTell bmi  
        | bmi <= 18.5 = "You're underweight, you emo, you!"  
        | bmi <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"  
        | bmi <= 30.0 = "You're fat! Lose some weight, fatty!"  
        | otherwise   = "You're a whale, congratulations!"
  • support for type classes
class Eqa where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
  • Types can be instances of classes (polymorphic functions)
  • Higher order functions map :: (a -> b) -> [a] -> [b]
  • list comprehensions - construction of new list from old lists
[(x,y) | x <- [1,2,3], y <- [4,5]]
[(x,y) | x <- [1..3], y <- [x..3]]
[x^2 | x <- [1..]] -- infinite lazy stream
[x | x <- [1..10], even x] -- with guard
  • quick sort
qsort[] = []
qsort(x:xs) = qsort[a | a <- xs, a < x]
              ++ [x] ++
              qsort[a | a <- xs, a >= x]

Pattern matching

  • it supports pattern matching -> native double dispatch
  • Functions can often be defined in many different ways using pattern matching. For example
  • The underscore symbol _ is a wildcard pattern that matches any argument value.
  • Functions on lists can be defined using x:xs patterns
  • lazy pattern matching -> always matches, could fail only when used
    • useful for streams

Lambda Calculus

  • a formal basis for functional programming
  • smallest universal turing complete programming language
  • slides - it is fucking hell

Syntax

  • a program is an expression
<expression> := <name> | <function> | <application> | (<expression>)

<function> := Ξ» <name>.<expression>

<application> := <expression><expression>
  • syntax lambda syntax
  • function is applied by substituting arguments (πœ†π‘₯.π‘₯)𝑦=[𝑦/π‘₯]π‘₯=𝑦
  • free and bound variables -> same as in LGR
  • it does not support function names

Booleans

  • T (tautology, or true) - πœ†π‘₯y.π‘₯
  • F (contradiction, or false) - πœ†π‘₯y.y
  • and - πœ†π‘₯𝑦.π‘₯𝑦𝐹
  • or - πœ†π‘₯𝑦.π‘₯𝑇𝑦
  • negation - πœ†π‘₯.π‘₯𝐹𝑇

Numbers

0 ≑ πœ†π‘ .πœ†π‘§.𝑧 ≑ πœ†π‘ π‘§.𝑧
1 ≑ πœ†π‘ π‘§.𝑠𝑧
2 ≑ πœ†π‘ π‘§.𝑠𝑠𝑧
3 ≑ πœ†π‘ π‘§.𝑠(𝑠(𝑠(𝑧)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment