Recursion


CUE does not permit general recursion. It intends to be Turing Incomplete. That being said, there are some forms of recursion that can be represented.

Structural Recursion

CUE also disallows cyclic references. However, this does not prevent us from defining infinite structures such as linked lists or binary trees. We call this structural recursion, where the process works on a finite piece of data.

linked-list.cue

// Definition of an infinite linked list
#List: {
	data: _
	next: #List | *null
	// note, the default to null is required
	// otherwise it looks like a cyclic reference
}

// manually construct a linked list
l: #List & {data: 1, next: #List & {data: 2}}

ds: [1, 2, 4, 8]
// comprehend a linked list from some data
ll: [ for i, d in ds {
	data: d
	if i < len(ds)-1 {
		next: ll[i+1] // note how we reference "future" list elements!
	}
}]

L: ll[0] // we really only want the first element

cue eval linked-list.cue

#List: {
	data: _
	next: null
}

l: {
	data: 1
	next: {
		data: 2
		next: null
	}
}

ds: [1, 2, 4, 8]

ll: [{
	data: 1
	next: {
		data: 2
		next: {
			data: 4
			next: {
				data: 8
			}
		}
	}
}, {
	data: 2
	next: {
		data: 4
		next: {
			data: 8
		}
	}
}, {
	data: 4
	next: {
		data: 8
	}
}, {
	data: 8
}]

L: {
	data: 1
	next: {
		data: 2
		next: {
			data: 4
			next: {
				data: 8
			}
		}
	}
}

Bounded Recursion

Bounded recursion is a limited form of general or generative recursion. The problem CUE has with general recursion is that it becomes difficult or impossible to run the evaluator and verify your CUE code. Bounded recursion puts a limit on recursion depth, thus making the problem not infinite and permissible under CUE’s philosophy. There were some comments made about permitting bounded general recursion in: https://github.com/cue-lang/cue/issues/990

In the meantime, and as a thought experiment, you can simulate bounded recursion with a comprehension and a function generator. You can find the following code and examples, as well as many more “recursive” structural helpers, in the Cuetils project on GitHub. There you will also find Go versions of these functions. For any serious usage, it is highly recommended using a language with proper general recursion support. Cuetils provides these same helpers as a Go package that supports CUE values as arguments. Expect performance issues when using the CUE version of RecurseN and the “recursive” functions built with it.

recurse.cue

package r

import "list"

#RecurseN: {
	// this is the bound on our recursion
	#maxiter: uint | *4

	// This is the function list element
	// we generate this to simulate recursion
	#funcFactory: {
		#next: _
		#func: _
	}

	// this is our "recursion unrolling"
	for k, v in list.Range(0, #maxiter, 1) {
		// this is where we build up our indexed functions and the references between them
		#funcs: "\(k)": (#funcFactory & {#next: #funcs["\(k+1)"]}).#func
	}

	// our final value needs to be null
	#funcs: "\(#maxiter)": null

	// we embed the head of the list so that the values
	// we write this into can be used like other CUE "functions"
	#funcs["0"]
}

depth.cue

package r

import "list"

#DepthF: {
	#next: _
	#func: {
		#in:    _
		#basic: int | number | string | bytes | null
		out: {
			// if we have a basic type, we are at a leaf, depth is 1
			if (#in & #basic) != _|_ {1}

			// if we are not a basic type, then we are 1 + the max of children
			if (#in & #basic) == _|_ {
				// this is our "recursion" for each child
				let depths = [ for k, v in #in {(#next & {#in: v}).out}]
				list.Max(depths) + 1
			}
		}
	}
}

#Depth: #RecurseN & {#maxiter: 11, #funcFactory: #DepthF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

d: #Depth & {#in: tree}

Note the {(#next & {#in: v}).out} in the let depths = ... line. This is “recursion” or really the reference from one of the generated “functions” to the next.

  • todo, show what an unrolled #Depth value looks like, this should help with understanding

We should be clear, there are no functions or calls or recursion happening here. What we are really doing is taking an incomplete definition and creating a sequence of them, which refer to their neighbors (the for comp in #RecurseN). It’s a way to reduce the writing, but each “function” has its own label and is a separate value. So we are essentially unrolling a “bounded recursion” into struct fields with a field (for) comprehension, and using an index suffix to name them so they are independent values.

Some more examples:

pick.cue

package r

#pickF: {
	#next: _
	#func: {
		#X: _
		#P: _
		pick: {
			// if P is not a complex type
			if (#P & ({...} | [...])) == _|_ {
				// then take the leaf value if it unifies (note to dev, should there be an if here?)
				#P & #X
			}

			// if P is a complex type
			if (#P & ({...} | [...])) != _|_ {
				// for each field in P
				for i, p in #P {
					let x = #X[i]

					// if they unify (samish type)
					if (x & p) != _|_ {
						// if not a struct, pick the value
						if (x & {...}) == _|_ {
							"\(i)": x
						}

						// if it is a struct, then "recurse"
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

					// if they do not unify
					if (x & p) == _|_ {
						// and if struct, then recurse
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #P: p}).pick
						}
					}

				}

			}
		}
	}
}

#Pick: #RecurseN & {#funcFactory: #pickF}

tree: {
	a: {
		foo: "bar"
		a: b: c: "d"
	}
	cow: "moo"
}

P: {
	a: foo: string
	cow: "moo"
}

p: #pick & {#X: tree, #P: P}

diff.cue

package r

#DiffF: {
	#next: _
	#func: {
		#X: _
		#Y: _
		diff: {
			{
				for i, x in #X {
					let y = #Y[i]
					if y == _|_ {
						"-": "\(i)": x
					}
					if y != _|_ {
						if (x & {...}) != _|_ {
							"\(i)": (#next & {#X: x, #Y: y}).diff
						}
						if (x & {...}) == _|_ {
							if (x & y) == _|_ {
								"-": "\(i)": x
								"+": "\(i)": y
							}
						}
					}
				}
			}
			"+": {
				for i, y in #Y {
					if #X[i] == _|_ {
						"\(i)": y
					}
				}
			}
		}
	}
}

#diff: #RecurseN & {#funcFactory: #DiffF}

ex: {
	x: {
		a: "a"
		b: "b"
		d: "d"
		e: {
			a: "a"
			b: "b"
			d: "d"
		}
	}
	y: {
		b: "b"
		c: "c"
		d: "D"
		e: {
			b: "b"
			c: "c"
			d: 1
		}
	}
	diff: (#diff & {#X: x, #Y: y}).diff
}

Packages

The Go API
Get CUE support and training from Hofstadter

Published 2024-03-31

Edit this page Create page issue Create project issue
We'll never share your email with anyone else.
2024 Hofstadter, Inc