idris - Why is this mutually recursive data definition not total and how can I fix it? -

i experimenting idris lot lately , came following "type level definition of set":

mutual   data set : type -> type     empty : set     insert : (x : a) -> (xs : set a) -> not (elem x xs) -> set    data elem : (x : a) -> set -> type     here : elem x (insert x xs p)     there : elem x xs -> elem x (insert y xs p) 

so set either empty or consists of set , additional element proven not in set already.

when totality check this, error

[...] not strictly positive

for insert, here , there. have been searching documentation terms "strictly positive" , totality checker in general, cannot figure out why case in particular not total (or strictly positive). can explain this?

the natural next question of course how "fix" it. can somehow change definition, keeping semantics, totality checks?

since don't need definition (it experiment after all) interesting know whether there another, somehow more idiomatic way represent sets @ type level total.

this post explains strictly positive types , why matter. in case, since not (elem x xs) means function elem x xs -> void, "type being defined occurring on left-hand side of arrow" comes from.

can make this?

mutual   data set : type -> type     empty : set     insert : (x : a) -> (xs : set a) -> notelem x xs -> set    data notelem : (x : a) -> set -> type     notinempty : notelem x empty     notininsert : not (x = y) -> notelem x ys -> notelem x (insert y ys p)