Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Performance problem with Haskell/OpenGL/GLFW (Jesper S?rnesj?)
2. Create new value for given type (Heinrich Ody)
3. Re: Create new value for given type (Mateusz Kowalczyk)
----------------------------------------------------------------------
Message: 1
Date: Fri, 8 Mar 2013 23:25:34 +1100
From: Jesper S?rnesj? <sarne...@gmail.com>
Subject: [Haskell-beginners] Performance problem with
Haskell/OpenGL/GLFW
To: beginners@haskell.org
Message-ID:
<CALex+WhKvebqL4KJnvm3tfwSFByGJ1cSkMAm=upvkf7_w5s...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hi there!
My first post here. :)
I have a curious performance problem with a Haskell/OpenGL/GLFW
program that I just can't figure out.
The program's CPU usage is quite high in general, and increases with
the number of pixels redrawn per frame. It uses OpenGL 3.2, does most
of its work on the GPU, and should do a constant amount of work per
frame on the CPU, so this makes little sense.
I've created a smaller program (still 91 lines, though), which renders
a single triangle, but still reproduces this problem. If I make the
triangle smaller (by editing vertexData), CPU usage goes down, and if
I make it bigger, CPU usage goes up. [1]
I've also created a C program which does the same thing (as far as
possible), but which does not exhibit this problem. CPU usage is far
lower, and stays constant regardless of the number of pixels redrawns
per frame. [2]
The library functions I use (from OpenGLRaw-1.3.0.0 and
GLFW-b-0.1.0.5) are only thin wrappers around their C counterparts, so
I strongly believe the problem is in my program.
Any thoughts?
--
Jesper S?rnesj?
http://jesper.sarnesjo.org/
[1] https://gist.github.com/sarnesjo/5116084#file-test-hs
[2] https://gist.github.com/sarnesjo/5116084#file-test-c
------------------------------
Message: 2
Date: Sat, 9 Mar 2013 01:25:17 +0100
From: Heinrich Ody <heinrich....@gmail.com>
Subject: [Haskell-beginners] Create new value for given type
To: beginners@haskell.org
Message-ID:
<CAMc+G-nZ4tPxhPs=Eg=NjkraBp4=yo79j8zpmurprnvtmgf...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20130309/620573fe/attachment-0001.htm>
------------------------------
Message: 3
Date: Sat, 09 Mar 2013 02:10:29 +0000
From: Mateusz Kowalczyk <fuuze...@fuuzetsu.co.uk>
Subject: Re: [Haskell-beginners] Create new value for given type
To: beginners@haskell.org
Message-ID: <513a9a15.9090...@fuuzetsu.co.uk>
Content-Type: text/plain; charset=windows-1252
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@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.
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 57, Issue 8
****************************************
