### Types, named (was: "Name that type!"), plus two more questions

Here are the answers to the previous quiz.

The first datatype holds any factorial number of values. Here it is again, with one small change and a few de-obfuscations:

> data FacHelp (f :: * -> *) (y :: *) = > Stop y > | More (FacHelp (OneMore f) (f y)) > newtype OneMore (f :: * -> *) (y :: *) = > OneMore (y, f y) > newtype Identity y = Identity y > type Factorial y = FacHelp Identity y

Here's that datatype again, renamed:

> data LongList x = Two x x > | AndAnother x (LongList x) > data Composite x = Composite (LongList (LongList x))

**Update:**

Chung-chieh Shan pointed out to me that I got that datatype wrong. (The other text above is correct, I think.) Anyway, here's his counterexample:

> test :: Composite Char > test = Composite (Two (Two 'a' 'b') > (AndAnother 'c' (Two 'd' 'e')))This is a correct (I think!) implementation of a container that can't be of a prime size:

> data Product f g a = Times (f (g a)) > | LeftIncr (Product (OneMore f) g a) > | RightIncr (Product f (OneMore g) a) > newtype Pair a = Pair (a,a) > type Comp = Product Pair Pair

**End update**

The third datatype uses the type `H`

, which encodes containers with a square number of elements. `H`

is based on the idea that the sequence of partial sums of the sequence of odd natural numbers is the same as the sequence of squares. That is, {0, 1, 1+3, 1+3+5, …} = {0^{2}, 1^{2}, 2^{2}, 3^{2}, …}

We can now use Lagrange's four-square theorem to see that question 3(b) is, strangely, a container that can hold any number of elements. An extension of this by Legendre showed [cite] that every number not of the form 4^{k}(8m + 7) is representable by the sum of three squares, and this answers question 3(a).

Here are both parts again, renamed and cleaned up a bit:

> data SqHelp x y = End > | Extra x (SqHelp (y,y,x) y) > type Square a = SqHelp a a > data Legendre x = Legendre (Square x) (Square x) (Square x) > data Lagrange x = Lagrange (Square x) (Legendre x)Here are two more questions:

4. Can we write something analogous to 3(a) in a more direct way?

5.

> data M a b = N b > | O (M (a,b) a) > newtype P a = P (M a a)

## 4 comments:

OK, after my total failure on the last quiz I came up with some new ways of reasoning about these types and so I >think< that "P a" is a list of elements that must be a fibonacci number in length (i.e. 1, 1, 2, 3, 5... elements). Pretty neat :-)

Umm, what is the second question? :)

BlackMeph: The second question is "What can we say about the structure of elements of this type?"

I really like your Fibonacci type. Here's a challenge for you: write a useful function on this type. Perhaps a function that takes a list and returns all permutations of that list ([a] -> Fibonacci [a]).

Post a Comment