Higher-Order Functions in K?

Question

Is it possible to write higher-order functions in K?

Particularly, things like Map and Fold, where I traverse a structure and apply a function to every element.

For example, if I have a list:

A ~> B ~> C

and I want to map a function F to every element of the list:

F A ~> F B ~> F C

Or maybe produce a fold:

F A (F B (F C))

where F is [function, functional] and is meant to evaluate, not be there syntactically.

Answer 1

If you know is advance what functions you want to be using in a higher order fashion, you can approximate this with something like:

syntax MapFunction ::= "foo"
syntax KItem ::= MapFunction "(" KItem ")" [function]

rule foo(...) => ...

syntax List ::= map(List, MapFunction) [function]
rule map(.List, _) => .List
rule map(ListItem(K) L, F) => ListItem(F(K)) map(L, F)

I recognize this is not ideal since it's not really a higher order function and you have to be explicitly aware of every function you intend to use this way and write it in a different fashion, but it's a decent workaround if you just need something quick and dirty in a couple places in the semantics.

As for the rest of your question, we would love to support higher order functions more generally, but we do not yet.