SKI - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

TheMatten

Is this "correspondence" useful or interesting in any way? (talking about SKI combinators):

I <~> ask
K <~> pure
S <~> (<*>)

(in context of Applicative (r ->))

Hjulle

Oh, the ask is a new one that I hadn't thought about before.
We cal also derive I the usual way with S and K, I = S K K = pure <*> pure, but that doesn't have any meaningful interpretation outside of the (->) r instance for Applicative.

The only use for that correspondence that I have seen is in the @pl extension of LambdaBot that transforms arbitrary haskell programs into point free style, by using combinators (including SKI).

TheMatten

Yeah - like, if you can efficiently translate LC to SKI (I'm reading http://okmij.org/ftp/tagless-final/ski.pdf BTW), then this is basically how you turn it into point-free

Hjulle

I was recently reading this post, which mentions that it is the method LambdaBot uses: https://doisinkidney.com/posts/2020-10-17-ski.html

Pedro Minicz

Ben Lynn has write about compiling lambda calculus to WASM by first translating it to SKI. http://www-cs-students.stanford.edu/~blynn/lambda/sk.html

Pedro Minicz

This correspondence is something I noticed a while ago while playing with ((->) r). I've written a small piece about it: https://pedrominicz.github.io/arrow

Pedro Minicz

The correspondence between ask and id is very interesting. Hadn't noticed it before.