All Questions
Tagged with functional-programming combinatory-logic
8 questions
4
votes
1
answer
104
views
Book references for combinatory logic as applied in Haskell?
I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell?
I found "Combinators: ...
- 261
3
votes
2
answers
158
views
How, if possible, can we efficiently compute with lazy data structures in 𝜆-calculus?
In Haskell, we can use the following code to define fibonacci numbers,
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
And its time complexity is linear.
I cannot find ...
- 63
2
votes
1
answer
81
views
Computation equivalence of functional and procedural programming
I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
- 23
1
vote
2
answers
78
views
Is there a combinator that introduces brackets to a combinatory logic expression using just B?
Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:
$Xabcdef=a(bcd)(ef)$.
Is it possible to express $X$ using just the $B$ combinator, defined by
$Babc=a(bc)$?
Is ...
- 151
7
votes
1
answer
448
views
Y combinator, function composition
I am trying to understand Y combinators. Could you please explain why the following are equivalent
(Y (f ∘ g))
(f (Y (g ∘ f)))
(Y is a fixed point combination)...
- 163
10
votes
1
answer
374
views
Are combinatory logic terms always larger?
So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I ...
- 3,800
9
votes
1
answer
914
views
Simply Typed Combinatory Logic?
As there is an untyped lambda calculus, and a simply-typed lambda calculus (as described, for example, in Benjamin Pierce's book Types and Programming Languages), is there a simply-typed combinatory ...
Scott Walck
2
votes
1
answer
694
views
What is the name of this combinator?
I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use ...
- 123