Programming III Flashcards
What are the distinct type operators in the below function definition?
(,) , -> , [] , Maybe
What are the distinct data constructors in the below function definition?
Nothing , Just , []
Higher Order Function
A function that takes a function as an argument, or returns a function.
Example: all curried functions
Curried function
A function that returns a function
curry and uncurry
curry: takes function that takes a single argument, and returns that function so that it takes multiple arguments.
uncurry: takes function that takes multiple arguments, and returns that function so that it takes a single argument.
Polymorphic function
A function is polymorphic if its type definition contains one or more unconstrained type variable
zip function
Appends two lists together, combining values from the same index into a pair.
If one list is shorter, it truncates the longer list.
zip: [a] -> [b] -> [(a,b)]
Alpha equivalent
Two terms are alpha equivalent if one can be converted to the other by alpha conversion.
* λ x -> λ y -> x y z is alpha equivalent to:
λ x -> λ w -> x w z
* λ x -> λ y -> x y z is not alpha equivalent to:
λ x -> λ z -> x z z
Redex
Reducible expression:
an expression comprising a function applied to an argument expression.
Innermost redex
A redex containing no other redexes
Outermost redex
A redex not contained in any other redex
Innermost evaluation
Innermost redexes are evaluated first
Outermost evaluation
Outermost redexes are evaluated first
Leftmost evaluation
Start with the leftmost redex
Rightmost evaluation
Start with the rightmost redex