<p>Unter the assumption, that lists simply represents arbitrary sets, the mathematical notation should probably read:</p>

<blockquote>
  <p>An ARE is an element of the following set:</p>
  
  <p>$\{ (P, Q) \mid P \subseteq ARF \times ARF, Q \subseteq ARF \} $    </p>
</blockquote>

<p>But as you stated, lists in your domain are always finite, ordering is not important, but multiplicity is. Thus, I would model the lists as finite multisets. Using an explicit notation for mulitsets, a possible definition would be:</p>

<blockquote>
  <p>An ARE is an element of the following set:</p>
  
  <p>$\{ (P_\chi, Q_\xi) \mid P \subseteq ARF \times ARF, 
                           P~\text{finite},~
                           \chi \in (P \to \mathbb{N}^+),
                           Q \subseteq ARF, Q~\text{finite},~
                           \xi \in (Q \to \mathbb{N}^+) \} $    </p>
</blockquote>

<p>Here, the notation $P_\chi$ denotes a multiset with P being the underlying ordinary set and $\chi \in P \to \mathbb{N}^+$ being the multiplicity function of the multiset. </p>

CC BY-SA 3.0
2012-08-16T22:38:10.250Z
To answer your questions: The order is not important (--> multiset) and the "lists" are finite
Johannes Weiss
CC BY-SA 3.0
2012-08-16T23:49:48.743Z
My "mathematical" notation was indeed complete nonsense. Besides formatting issues (non-visible curly brackets because I sometimes typed `{ ... }` instead of `\{ ... \}`), I completely messed it up anyway :-(. Your suggestion using `P` and `Q` being subsets of all possible `ARF`s and $ARF \times ARF$s seems very good. Thanks!
Johannes Weiss
CC BY-SA 3.0
2012-08-17T15:29:29.013Z
Sorry, unfortunately, I identified one problem: How could one notate that $P$ and $Q$ are multisets? $Q \subseteq ARF$ looks like $Q$ being an ordinary set.
Johannes Weiss
CC BY-SA 3.0
2012-08-18T15:51:35.527Z
If you look at, for example, multisets on Wikipedia, for better or worse they use the same notation as regular sets. If you're *only* talking about multisets, I think it's fair to just say "by 'set' I mean 'multiset'" and go from there.
Rob Simmons
CC BY-SA 3.0
2012-08-18T22:25:31.023Z
@Johannes Weiß: Why don’t you just write “P and Q are multisets” explicitly?  I do not think that there is a widely accepted notation for multisets.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-16T17:49:20.530Z
2012-08-23T13:58:27.593Z
2012-08-23T13:58:27.593Z
stefanwehr
<p>I come from <a href="http://haskell.org" rel="nofollow">Haskell</a> programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type.</p>

<p>The Haskell data type is:</p>

<pre><code>data ARE = ARE [(ARF, ARF)] [ARF]   -- Haskell form
type ARE = ( [(ARF, ARF)], [ARF] )  -- alternate form
</code></pre>

<p>An <code>ARE</code> is an <em>affine randomized encoding</em> and an <code>ARF</code> is an <em>affine randomized function</em>. You can think of an <code>ARF</code> just as an abstract entity, just like a field or group element. My problem is how to formally notate a definition for an <code>ARE</code>.</p>

<p>First, I'll try to describe what an <code>ARE</code> is in english: An <code>ARE</code> is a tuple (in the "alternate form", in my Haskell program it's represented as in the "Haskell form") containing:</p>

<ul>
<li>a list (not a set since it could contain duplicates) containing tuples. Each of these tuples is just two <code>ARF</code>s</li>
<li>a list of <code>ARF</code>s</li>
</ul>

<p>What I'm looking for is a formal notation of such an <code>ARE</code>.</p>

<p>(<strong>edit</strong>: removed nonsense notation proposal...)</p>

<p>About the expected audience (and their knowledge domain) of my thesis: I will provide Haskell code, but the entire thesis should be understandable by someone who is not a programmer (and in particular no Haskell programmer). The reader will need some knowledge in cryptography, computer science (but not programming) and basic mathematics (some field theory, especially the finite fields $\mathbb{F}_{2^n}$). In the text I simply want to tell the reader what AREs are and how I transform general expressions to AREs.</p>

CC BY-SA 3.0
2012-08-16T16:59:38.950Z
(I "migrated" the question from math stackexchange: Posted new version and deleted the one on math stackexchange ( http://math.stackexchange.com/questions/182932/mathematical-representation-of-haskell-data-types ))
Johannes Weiss
<ds.data-structures><pl.programming-languages><notation>
Formal Representation of Haskell Data-Types
Johannes Weiss
# Formal Representation of Haskell Data-Types

(Asked by: username_0 on 2012-08-16)

I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type.
The Haskell data type is:
data ARE = ARE [(ARF, ARF)] [ARF]   -- Haskell form
type ARE = ( [(ARF, ARF)], [ARF] )  -- alternate form

An ARE is an affine randomized encoding and an ARF is an affine randomized function. You can think of an ARF just as an abstract entity, just like a field or group element. My problem is how to formally notate a definition for an ARE.
First, I'll try to describe what an ARE is in english: An ARE is a tuple (in the "alternate form", in my Haskell program it's represented as in the "Haskell form") containing:

a list (not a set since it could contain duplicates) containing tuples. Each of these tuples is just two ARFs
a list of ARFs

What I'm looking for is a formal notation of such an ARE.
(edit: removed nonsense notation proposal...)
About the expected audience (and their knowledge domain) of my thesis: I will provide Haskell code, but the entire thesis should be understandable by someone who is not a programmer (and in particular no Haskell programmer). The reader will need some knowledge in cryptography, computer science (but not programming) and basic mathematics (some field theory, especially the finite fields $\mathbb{F}_{2^n}$). In the text I simply want to tell the reader what AREs are and how I transform general expressions to AREs.

**Tags:** ds.data-structures, pl.programming-languages, notation

> **Comments:**
> **username_0**: (I "migrated" the question from math stackexchange: Posted new version and deleted the one on math stackexchange ( http://math.stackexchange.com/questions/182932/mathematical-representation-of-haskell-data-types ))  

---

## 1 answers

### Answer by username_1 on 2012-08-16. Score: 6 | Accepted answer

Unter the assumption, that lists simply represents arbitrary sets, the mathematical notation should probably read:

> An ARE is an element of the following set:
>
> $\{ (P, Q) \mid P \subseteq ARF \times ARF, Q \subseteq ARF \} $

But as you stated, lists in your domain are always finite, ordering is not important, but multiplicity is. Thus, I would model the lists as finite multisets. Using an explicit notation for mulitsets, a possible definition would be:

> An ARE is an element of the following set:
>
> $\{ (P\_\chi, Q\_\xi) \mid P \subseteq ARF \times ARF,
> P~\text{finite},~
> \chi \in (P \to \mathbb{N}^+),
> Q \subseteq ARF, Q~\text{finite},~
> \xi \in (Q \to \mathbb{N}^+) \} $

Here, the notation $P\_\chi$ denotes a multiset with P being the underlying ordinary set and $\chi \in P \to \mathbb{N}^+$ being the multiplicity function of the multiset.

> **Comments:**
> **username_0**: To answer your questions: The order is not important (--> multiset) and the "lists" are finite  
> **username_0**: My "mathematical" notation was indeed complete nonsense. Besides formatting issues (non-visible curly brackets because I sometimes typed `{ ... }` instead of `\{ ... \}`), I completely messed it up anyway :-(. Your suggestion using `P` and `Q` being subsets of all possible `ARF`s and $ARF \times ARF$s seems very good. Thanks!  
> **username_0**: Sorry, unfortunately, I identified one problem: How could one notate that $P$ and $Q$ are multisets? $Q \subseteq ARF$ looks like $Q$ being an ordinary set.  
> **username_2**: If you look at, for example, multisets on Wikipedia, for better or worse they use the same notation as regular sets. If you're *only* talking about multisets, I think it's fair to just say "by 'set' I mean 'multiset'" and go from there.  
> **username_3**: @Johannes Weiß: Why don’t you just write “P and Q are multisets” explicitly?  I do not think that there is a widely accepted notation for multisets.  

---

