validate sum of list

[cueckoo]

Originally opened by @codesuki in cuelang/cue#78

Is there any way to validate if a list sums to a specific value?
Let's say I have a list of floats that need to sum to 1.0.
Reading through the docs I couldn't find anything.

[cueckoo]

Original reply by @xinau in cuelang/cue#78 (comment)

@codesuki atm. this is not possible due to the fact that cue has no form of reduce or sum implemented. implementing this functionality could be done by adding functions (like terraform/hcl) or expanding the list comprehension functionality. I hope I didn't miss something, else @mpvl can add some more context to this issue.

[cueckoo]

Original reply by @codesuki in cuelang/cue#78 (comment)

Good to know. Thanks!
Is this a planned feature? Because of this we are still relying on a custom binary that does config validation. Would be neat if we could switch that out for cue.

Since cue is written in Go I might be able to carve out some time and help in case there's a design doc or similar.

[cueckoo]

Original reply by @mpvl in cuelang/cue#78 (comment)

Actually, after a small bug fix, it is actually possible to compute the sum, it is just:

1. not pretty
2. uses various features I would like to deprecate soon

And this is not meant to be a serious answer to your question. Just maybe a fun one.

Indeed, builtins first and later some kind of reduce functionality (not using lambdas) will be a better answer to this. SQL's list.Sum, list.Avg, list.Min, and list.Max seem reasonable to add.

But that's not what you asked. You want to validate that that is true. CUE can already take any builtin returning boolean and turn it into a validator by turning it into a partial function. So having an assert builtin to turn any expression into a validator is not too crazy.

Anyway, this implements sum (with v0.0.8):

fnRec: {nn: [...int], out: (fn & {arg: nn}).out}
fn: {
	arg: [...int]

	out: arg[0] + (fnRec & {nn: arg[1:]}).out if len(arg) > 0
	out: 0 if len(arg) == 0
}
v: (fn & {arg: [1, 2, 3, 4, 5]}).out

To fnRec trick is needed to fool CUE into not fixing variables too early. You can maybe imagine how to turn this into a more generic recursive function construct. But maybe on should let sleeping dogs lie. :)

Note that CUE structs, besides being a very general data type, are also functions. It is actually harder than one would expect to make a language based on recursive data that is not Turing Complete. HTML + CSS3 is even TC.

This features I would like to deprecate are

1. Primitive recursion, as used above, making CUE not Turing Complete (see issue cue: implement occurs check #29 and cue: structural cycles not detected #42). (But recursive types would still be allowed, of course).
2. slices, although that would be replaced with list.Slice() (not sure about this one)
3. I have a proposal ready for (much) nicer comprehensions I would like to transition to after review and all.

Note that it is not per se bad to be TC, and often one will want it. For CUE, there are some benefits in being able to proof termination.

[cueckoo]

Original reply by @mpvl in cuelang/cue#78 (comment)

@codesuki Thanks for offering to help. An implementation of builtins is quite easy in CUE, once an API is designed. The problem is designing the API. For this it would be good to know exactly what you want to do. Is it just sum, or also average, etc. Do you want to use it as a constraint only, in a computation, or both? That sort of stuff. Concrete examples are always a great start for creating
a good design.

[cueckoo]

Original reply by @codesuki in cuelang/cue#78 (comment)

I just left for vacation, I'll get back to this issue once I am back. Thank you for your great answer! Super interesting. I totally missed that you can have functions in cue.

[cueckoo]

Original reply by @rudolph9 in cuelang/cue#78 (comment)

This features I would like to deprecate are

1. Primitive recursion, as used above, making CUE not Turing Complete (see issue #29 and #42). (But recursive types would still be allowed, of course).

2. slices, although that would be replaced with list.Slice() (not sure about this one)

3. I have a proposal ready for (much) nicer comprehensions I would like to transition to after review and all.

@mpvl It makes perfect sense to deprecate those features.

list.Sum, list.Avg, list.Min, and list.Max are very desirable.

Eventually maybe some normal distribution calculations (standard deviation, variance).

[cueckoo]

Original reply by @mpvl in cuelang/cue#78 (comment)

@codesuki

I totally missed that you can have functions in cue.

That was intentional :)

[cueckoo]

Original reply by @mpvl in cuelang/cue#78 (comment)

@rudolph9

list.Sum won't support the OPs issue, but it would with adding another builtin. Something like constraint, which would turn an arbitrary boolean expression into a constraint value:

foo: constraint(list.Sum(foo) == 1)

So constraint would limit foo to be any list for which its values sum to 1.

Note that this is a generalization of CUE's "unary comparators". So

foo: <5

could then also be written as

foo: constraint(foo < 5)

The alternative would be to define functions like list.SumsTo(list, value) error, but that doesn't seem very pretty.

To force alignment between constraints and fields, and avoid every-growing piles of assertions, it could be required that the expression in constraint must refer to the field in which it is defined.

[cueckoo]

Original reply by @jba in cuelang/cue#78 (comment)

Or maybe generalize unary comparators by picking a token to mean "the value of this field":

foo: $ < 5

bar: list.Sum($) == 1

[cueckoo]

Original reply by @xinau in cuelang/cue#78 (comment)

I'm still not sure if CUE needs a function like list.Sum if we add a reduce functionality to list comprehension. The plus side of a function like list.Sum would be readability and maybe easier code generation, but also results in additional functions for Min, Max or Product.
Comparing:

foo: list.Sum([1, 2, 3, 4])

against something like

for x in [1, 2, 3, 4] with acc: 0 reduce acc + x

[cueckoo]

Original reply by @xinau in cuelang/cue#78 (comment)

@jba I like your idea of generalizing unary comparators, but maybe instead of introducing a new token we could do something similar to auto-currying as in haskell. meaning

// foo :: Double -> Bool
// foo = (>) 5
foo: 5 >

// bar :: [Double] -> Bool
// bar = (==) 1 $ sum
bar: 1 == list.Sum

Disclaimer: I'm not sure if this is valid Haskell. It's been a long time since my last endeavors.