Please enable JavaScript.
Coggle requires JavaScript to display documents.
Elements of Functional Computing (OCaml (Simple variable assignment - let…
Elements of Functional Computing
Rewrite Systems
A system which has a set of rules. Eg. Replace capital letters with lower case letters.
Determinism - Only 1 way to go from the input to the next step
Confluence - The rules can be applied in any order and the same outcome will be achieved.
Convergence - There is no infinite loop of rules.
Canonical - Each string has a unique normal form (outcome)
OCaml
Simple variable assignment - let <name> = <val> Eg. let x = 1
Local variable assignment - let <name> = <val> in <exp> Eg. let x = 1 in x + x (= 2)
Functions - let <name> <var> = <exp> Eg. let square x = x * x
Pattern matching - let <name> <var> = match <var> with [ ] → <exp> | [a] → <exp> | etc... Eg. let first x = match x with [ ] → None | x → Some x
Recursive functions - let rec <name> <var> = <expression> Eg. let rec add x = 1 + add (x-1)
Pattern matching v2 - let rec <name> = function [ ] → <exp> | [x] → <exp> | etc... Eg. let rec first = function [ ] → None | [x] → Some x
Associations - f(g(x)) = f
@
g
@
x = x |> g |> f
Tuples - let <name> (a, b) = <exp>
Lists - [a; b; c; d] = a :: {list} = {list} @ [a]
Failwith. Crashes program nicely - failwith <msg>
Random stuff
Isomorphism - When data can be converted to a different data type and back without losing any information
Numbers
Unary/Natural Numbers - A numbering system where the value is calculated by how many times a certain piece of data is repeated. Eg. 111 = 3 or Suc Suc Suc Zero = 3.
Integers can be stored as a positive nat part and a negative nat part. So (m,n) where m-n.
Floating Point - An approximation. But is an easier version of real numbers.
OCaml Modules
module <name> = struct
type ..
let .. = function
eg. <name>.isEmpty then
OCaml Types
Defining types - type <name> = <val> | <val> | etc...
More types - type <type> <name> = <val> | <val> of <type> | <val> of <type>
* <type> Eg. type 'a value = Nothing | Int of int | Str of string
* string
How to use - (Str "Hello")
Option Types - Built in types: None | Some <val>. Allows any value to be outputted.
Pointless Programming
Abstract function which simplifies re-writing similar functions. Eg. let fold g a = function | [] -> a | x :: xs -> let v = fold g a xs in ... g x v.
Makes a program more concise, means that you don't have to explicitly write code.
Structural Induction
A method of proving soundness in programming languages. Similar to proof by induction. Allows isomorphism to be proved.
Basically runs through all the possible inputs and outputs, but uses the idea of recursion as well.
Eg. n = Zero ..., n = Suc n' ...