Haskell: Sets

Given a finite Set type (not Data.Set), find a map Set -> Int that is bijective! (Let's try injective first, how would you do that?)

The definition of Set I have in mind is this:
data Set = Empty | Set [Set]
But if you want to use some other equivalent definition go ahead.

#define SET(type, init_size) type * data[size]
...
typedef SET(int, 10000) muh_set;

>>2
Why T*[]?

why

data Set = Empty | Set [Set]

and not

data Set = Set [Set]

you stupid haskel faget

>>4
<https://en.wikipedia.org/wiki/Leaky_abstraction>

did you mean something like:

data Nil :: *
data Cons :: * -> * -> *

data Set :: * -> * where
Nil :: Set Nil
Cons :: h -> Set t -> Set (Cons h t)

>>6
It depends on the underlying set axioms of the category FinSet you are implementing. For example, yours is with urelements while mine is GST.

>>6
Though the problem is that while my Set is countable, yours is not! Therefore, a binjection with Ints can not be found.

>>8
count my anus

Isn't this just Peano arithmetic?

Quoting 10:(my phone doesn't have them brackets ffs)
The peano arithmetic is an injection from sets to the integers that also has the nice property of translating set-theoretic terms into arithmetic ones. Going the other way you can construct an injection from the integers to finsets. I hadn't though of that, I had found another way myself, I'll post the idea some other time. With that said, how do you go from peano to bijection? I don't think you do.:-)

>>11
Nice answer. Why do you own a expensive toy with a touchscreen though?

>>12 actually now that I think of it some more, there is no "going the other way", peano arith gives an
Injection from integers to sets fullstop.

for the toy remark, it cost $60 second-hand n I just came to the US

>>13
Did immigration control require you to carry around the tracking collar in case you try to stay when your visa expires?

>>11

I don't think you do.:-)

Really? Peano evens count negative, odds count positive. Are we good, or do you want to talk about homos now?

Or do you want to talk about homos now?

I was serious when I asked this btw. I am prepared to talk about homomorphisms if you want to go there.

Fucking haskell, I have to fucking format my system to install an update. This is the Set -> Int injection I had in mind.

concatInteger :: [Integer] -> Integer
concatInteger = read . concatMap show

setLen Empty = 0
setLen (Set s) = length s

set2List Empty = []
set2List (Set s) = length s : sort $ concatMap set2List s

set2Int = concatInteger . set2List

>>17
Disregard setLen. It's not needed.

>>17,18
I just realized this is not 1-1

https://math.stackexchange.com/questions/130788/isnt-there-a-bijection-between-real-numbers-and-natural-numbers

>>14
There's no immigration control in the US. The politicians want more immigrants from whatever hellhole.

>>20
Thats not relevant, finset is countable

>>21
Thats not relevant, immigrants are uncountable

Count my dubs.

>>22
It's relevant.

>>19
Okay so the solution for it to be 1-1 is to use 0 as a delimiter.

What I'm doing here is this:

Sets are basically things of this sort:
{{{},{{}}, {{},{{}}}}, {}}
Because the comma can be deduced, it runs down to this:
{{{}{{}}{{}{{}}}}{}}
Now what this really is, is just a tree without labels (hence the Set type definition looks exactly like a Tree). I will depict the above set in an ASCII tree diagram:
2 / \
1 /
3 / / \
1,2 / /\
1 \

At the left side is the number of branches. At the right side is the tree (so for example / / \ means there are 3 branches). The idea to give a unique integer to this tree is this: Sort out lists (the only list here is 1,2), and concatenate integers, with 0 as a delimiter. So what we'd get is this:
20103020101
The reason 0 is used as a delimiter is because I figured that it's not clear whether 21 means 2 and then 1 or really 21 nodes. It may be possible to deduce which of the two is true if you keep scanning the integer code to find the "only" legit set, but it may be that two different sets map to the same integer. I haven't figured out which of the two is true, but if you use 0 as a delimiter you are good to go.

Anyhow, that's the injection. Anybody up for the bijection? I tried lexicographical order on the {{{}{{}}{{}{{}}}}{}} representation, but it turns out it's not good enough: You run into infinity because of expressions like {{{{...}}}, X} and it doesn't matter what X is.

bijection was posted twice and ignored

>>27
Alright, elaborate then please. As far as I understand it you're wrong.

>>28
Try reading the thread, genius.

>>23
oh dear