validate sum of list

[cueckoo]

Originally opened by @codesuki in https://github.com/cuelang/cue/issues/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 https://github.com/cuelang/cue/issues/78#issuecomment-526347337

@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 https://github.com/cuelang/cue/issues/78#issuecomment-526368902

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 https://github.com/cuelang/cue/issues/78#issuecomment-526371209

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 #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.

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 https://github.com/cuelang/cue/issues/78#issuecomment-526510893

@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 https://github.com/cuelang/cue/issues/78#issuecomment-526823358

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 https://github.com/cuelang/cue/issues/78#issuecomment-526975773

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 https://github.com/cuelang/cue/issues/78#issuecomment-527794079

@codesuki

I totally missed that you can have functions in cue.

That was intentional :)

[cueckoo]

Original reply by @mpvl in https://github.com/cuelang/cue/issues/78#issuecomment-527798670

@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 https://github.com/cuelang/cue/issues/78#issuecomment-527859884

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 https://github.com/cuelang/cue/issues/78#issuecomment-527867573

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 https://github.com/cuelang/cue/issues/78#issuecomment-527878854

@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.

[cueckoo]

Original reply by @joshburkart in https://github.com/cuelang/cue/issues/78#issuecomment-531331490

I think I'd like a sum builtin... For example, say I have a list comprehension that produces a list of lists. I then want to flatten it into a single list. Is there some way to do this without a sum builtin that works similarly to or and and?

[cueckoo]

Original reply by @xinau in https://github.com/cuelang/cue/issues/78#issuecomment-532341327

@joshburkart the sum built-in is available with cue version v0.0.9 under list.Sum. A flatten function is being worked on ;) but if you know your list structure, this should also be possible with list comprehension I think. (going to evaluate that later)

[myitcv]

As part of the recent issue garden, we are focussing on non-feature requests. As such, I'm removing the milestone on this feature request. We will revisit feature requests in a later pass, at which point we will start to milestone and prioritise new features (in addition to those that we are already working on).