[Haskell-beginners] Create new value for given type

[Mateusz Kowalczyk]

On 09/03/13 00:25, Heinrich Ody wrote:
> Hi,
> 
> I'm given a type 'a' (lets assume the type is infinite) and a set finite
> 'xs'. Now I want to create a new value of type 'a' that does not occur
> in 'xs' and return a set 'ys' that consists of 'xs' and also contains
> the new value.
> How can I do this???
> 
> The types are known at compile time, so I would think it is possible in
> Haskell..
> 
> Greetings,
> Heinrich
> 
> 
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
> 
I just typed out a massive reply after which point I re-read your
question and concluded that I misunderstood you… Here's my second shot
at it. Note that by no means am I an expert.

Long message ahead. The gist of it is: you can't for general case.

Well, given just the information you've written down, it's impossible.
First of all, we need means of testing whether ‘xs’ (I'm assuming that
‘xs :: Set a’) contains any value of type ‘a’ we might throw at it. At
the very minimum we need the type ‘a’ to have an instance of the ‘Eq’[1]
class. Regular caveats of comparing potentially infinite values apply
but that's fine as far as the type system is concerned. So your function
was called ‘generateNewUnique‘ then we end up taking

> genBiggerSet :: Set a -> Set a
to
> genBiggerSet :: (Eq a) => Set a -> Set a

I'd like to mention that your ‘Set’ type might already have such
constraint on it: after all, it has to compare the elements together to
ensure that they are all unique.

OK, so let's say we still want such a function, even if we have to
settle for the ‘Eq’ constraint. What you wanted was to make a new value
that's not in the set. Well:

> generateUniqueValue :: Set a -> a

I don't know about you but I'm starting to see a problem here: we want a
function that takes a set of values and then returns something that's
_not_ in the set. A quick illustration on a set of ‘Integer‘s proves
that such function is not impossible but, and this is a very important
point, only for Integers.

> generateUniqueInteger :: Set Integer -> Integer

Assuming we have functions ‘max :: (Ord a) => Set a -> a‘ and ‘append ::
Set a -> a -> Set a‘, here's one way to solve your problem, for Integers:

> generateUniqueInteger xs = append (max xs + 1) xs

We now that there is an infinite number of Integers so we can always
produce a unique one in a finite set. What's wrong with this solution?
First of all, we are constrained by the definition of a set. A set is a
collection of elements with all the elements being unique. Straight away
you limited yourself to ‘Eq’ as mentioned before. Secondly, my unique
integer generator put on further constraints: ‘Num’ for ‘+’ and ‘Ord’[2]
for ‘max’. The question is whether we can get rid of ‘max’ and ‘+’ and
make them work for any type (although we do get ‘Eq’ to play with). I
don't think we can.

There's simply no way to generate a value out of thin air without more
constrains.

Let's try to make one though! Can we make a function

> makeUnique :: a

? Well, not really. We learn on day 1 that calling a function with the
same parameters will result in the same value – we get referential
transparency this way.

But what about something like

> makeUnique :: IO a

? Can we maybe randomise the value and then return it in the IO Monad
and unwrap it later, test whether it's unique and simply keep trying? We
quickly find out that to be able to do that, we'd have to restrict our
type to ‘makeUnique :: (RandomGen a) => IO a‘ [3]. Not good enough – we
still don't know how to get magically go to a unique value from some
random one.

Clearly then we need more information. We make full circle and come back to

> generateUniqueValue :: Set a -> a

With everything we have learned on the way, we still don't know how to
achieve this for any ‘a‘. In fact, the only way such a function could
exist (I think) is through something like:

> generateUniqueValue :: (Unique a) => Set a -> a

where we define ‘Unique’ as such

> class Unique a where
>      nextUnique :: a -> a

So in the end, the only types you can do this for is:
- for types that have infinite amount of values:
> data Foo = Bar | Baz
  will never work! We can't make a new unique element from {Bar, Baz}
- for types that can be tested for equality
- for types where we can make a new, different value of ‘a’ from already
existing ‘a’


And that's all! To close it off, I'd like to mention that while I don't
believe this is possible for general case, there are some cases where we
can still achieve this somewhat. An example is to settle for ‘a‘ being
bound under ‘Enum’ and then giving it an instance of ‘Unique’ as such

> instance Unique a where
>     makeUnique x = succ x -- we get ‘succ’ thanks to ‘Enum’

We can then define our ‘generateUniqueValue’ by ‘succ’ing any of the
elements in the set until it's unique. Not very efficient but it works.
If we don't want to be bound under ‘Enum’[4], we need to come up with
the means of generating a new value ourselves. Of course the situation
is different if the set is empty – we have nothing to generate from! We
can remedy this by specifying a base value function in our type class:

> class Unique a where
>      nextUnique :: a -> a
>      base :: a

The very last caveat with this is to watch-out for cyclic value
generation. A quick example on Integers of what the type system will not
protect you against:

> f 1 = 2
> f 2 = 1
> f 3 = 3
> f x = x + 1
>
> class Unique a where
>   unique :: a -> a
>
> instance Unique Integer where
>   unique x = f x
>
> findUnique :: (Eq a, Unique a) => [a] -> a
> findUnique xs@(x:_) =
>   if unique x `elem` xs
>     then findUnique (unique x : xs)
>     else unique x

Running it in ghci we get:
> *Main> findUnique [ 6 .. 10 ]
> 11
> *Main> findUnique [ 3 .. 10 ]
>   C-c C-cInterrupted. {- Infinite loop on f 3 -}
> *Main> findUnique [ 1 .. 10 ]
>   C-c C-cInterrupted. {- Infinite loop oscillating from f 1 to f 2 and
back -}

It will also not protect you from exceptions such as ‘succ’ing values of
finite type until the end of the enumeration.


Apologies for a long post but I wanted to make myself clear. It might
just be that someone will come in here and prove me wrong for all I know.


[1] -
http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#t:Eq
[2] -
http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#t:Ord
[3] -
http://hackage.haskell.org/packages/archive/random/1.0.0.2/doc/html/System-Random.html#t:RandomGen
[4] -
http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#t:Enum


-- 
Mateusz K.