New answers tagged functional-programming
3
votes
Accepted
Proving transitivity in an intuitionistic type theory without the K rule
$\newcommand{\J}{\mathsf{J}} \newcommand{\K}{\mathsf{K}} \newcommand{\refl}{\mathsf{refl}}$
Yes, this just uses axiom $\J$. $\K$ is only necessary for translating certain particular cases of pattern ...
1
vote
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
@D.W. what if at each step, there is not a fixed finite number of choices, rather some $k$ choices. In that case, there would be $O(k^t)$ different control-flow paths. By properly tuning, $k$ and $t$ ,...
5
votes
Accepted
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
Without arrays, $\Omega(\log n)$ time is needed. Without arrays, the memory address you access is entirely determined by the control-flow path, i.e., the sequence of control-flow decisions (if ...

D.W.♦
- 140k
Top 50 recent answers are included
Related Tags
functional-programming × 355programming-languages × 82
lambda-calculus × 80
type-theory × 43
category-theory × 32
terminology × 21
haskell × 18
reference-request × 17
algorithms × 14
data-structures × 14
compilers × 14
dependent-types × 13
semantics × 12
imperative-programming × 12
recursion × 11
programming-paradigms × 10
logic × 9
proof-techniques × 9
proof-assistants × 9
lisp × 8
type-checking × 7
type-inference × 7
combinatory-logic × 7
mathematical-foundations × 6
software-verification × 6