Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Can't install haskell-platform on OpenSuse 10.3 without Glut
(David Carter)
2. Re: Can't install haskell-platform on OpenSuse 10.3 without
Glut (Roger Whittaker)
3. When, if ever, does Haskell "calculate once"? (Travis Erdman)
4. Re: When, if ever, does Haskell "calculate once"?
(Daniel Fischer)
5. Re: When, if ever, does Haskell "calculate once"? (Brent Yorgey)
6. [Fwd: Binary tree algorithm] (legajid)
7. Re: [Fwd: Binary tree algorithm] (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Thu, 6 May 2010 17:55:21 +0100
From: David Carter <[email protected]>
Subject: [Haskell-beginners] Can't install haskell-platform on
OpenSuse 10.3 without Glut
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
I am trying to install haskell-platform on OpenSuse 10.3, i586. I
installed ghc 6.12.1 OK, then unpacked
haskell-platform-2010.1.0.0.tar.gz, but "configure" gives me
configure: error: The GLUT C library is required
I have no particular interest in graphics programming and don't want to
get involved in installing glut or freeglut as that is likely to cause
more installation problems for all I know.
I discovered this message and its reply suggesting looking in the bug tracker,
http://www.haskell.org/pipermail/haskell-cafe/2009-December/070813.html
http://www.haskell.org/pipermail/haskell-cafe/2009-December/070814.html
but http://trac.haskell.org is down (I don't remember ever finding it
up, in fact).
Can anyone suggest a workaround? It's a bit of a showstopper if the main
implementation of Haskell can't be installed without having non-free
software :-(.
Thanks
David
------------------------------
Message: 2
Date: Thu, 6 May 2010 18:07:54 +0100
From: Roger Whittaker <[email protected]>
Subject: Re: [Haskell-beginners] Can't install haskell-platform on
OpenSuse 10.3 without Glut
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, May 06, 2010 at 05:55:21PM +0100, David Carter wrote:
> I am trying to install haskell-platform on OpenSuse 10.3, i586. I
> installed ghc 6.12.1 OK, then unpacked
> haskell-platform-2010.1.0.0.tar.gz, but "configure" gives me
>
> configure: error: The GLUT C library is required
Probably you need to do is
zypper in freeglut-devel
--
========================
Roger Whittaker
[email protected]
http://disruptive.org.uk
========================
------------------------------
Message: 3
Date: Thu, 6 May 2010 11:35:15 -0700 (PDT)
From: Travis Erdman <[email protected]>
Subject: [Haskell-beginners] When, if ever, does Haskell "calculate
once"?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Two questions here, I think they might be related, perhaps even the same, but I
am not sure, so I will ask both:
Q1: Re the function f below, I like the first implementation as it's
"cleaner", but is the second implementation necessary for performance purposes?
-- g = some CPU intensive function
-- alternate 1
f a b = c + (g b)
where
c = dosomethingelse a (g b)
-- alternate 2
f a b = c + saveit
where
saveit = g b
c = dosomethingelse a saveit
Q2: Imagine that I might be creating a custom data structure. I need to
access both the data in that structure, but also "features" (don't know proper
comp sci term) of the data structure. For instance, consider a Haskell list.
The stuff in the list is the data, whereas the length of the list is what I am
calling a "feature" here. Some of my features might be quite a bit more
computationally intensive than "length", and may be referenced multiple times
in many different places in my code. For performance purposes, should I
consider modifying my data structure to embed these "features" as part of the
data to ensure that it is only calculated once? Or can I rely on Haskell to do
that for me? For instance, do I need to create the equivalent of:
data MyList a = MyList {mylist::[a], mylength::Int}
Thanks again for all your generous advice.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100506/2b3fc6f6/attachment-0001.html
------------------------------
Message: 4
Date: Thu, 6 May 2010 21:30:57 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] When, if ever, does Haskell
"calculate once"?
To: [email protected]
Cc: Travis Erdman <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Thursday 06 May 2010 20:35:15, Travis Erdman wrote:
> Two questions here, I think they might be related, perhaps even the
> same, but I am not sure, so I will ask both:
>
> Q1:Â Re the function f below, I like the first implementation as it's
> "cleaner", but is the second implementation necessary for performance
> purposes?
>
> -- g = some CPU intensive function
>
> -- alternate 1
> f a b = c + (g b)
> Â Â Â where
> Â Â Â Â Â Â Â c = dosomethingelse a (g b)
>
A Haskell implementation *might* calculate (g b) only once, but very
probably it will calculate it twice.
      Â
> -- alternate 2Â Â Â Â Â Â Â
> f a b = c + saveit
> Â Â Â where
>        saveit = g b  Â
> Â Â Â Â Â Â Â c = dosomethingelse a saveit
A Haskell implementation is allowed to calculate saveit twice, but a decent
one won't.
If you want to share the result of a computation, give a name to it.
One reason why sharing the common subexpression (g b) in the first snippet
is not done is that it often is a terrible idea.
If, for example, g b is a large list, sharing hogs a lot of memory. If
dosomethingelse and (+) consume that list in a suitable manner, only a
small portion of it need be in memory at any given time.
Of course, if (g b) takes only very little memory (certainly if it is an
Int, Word, ..., Integer [almost certainly]), automatic sharing would be a
good idea.
However, looking for common subexpressions to share depending on their type
would be even more complicated than looking for all common subexpressions,
so probably nobody implemented it.
>
>
> Q2: Imagine that I might be creating a custom data structure. I need
> to access both the data in that structure, but also "features" (don't
> know proper comp sci term) of the data structure. For instance,
> consider a Haskell list. The stuff in the list is the data, whereas the
> length of the list is what I am calling a "feature" here. Some of my
> features might be quite a bit more computationally intensive than
> "length", and may be referenced multiple times in many different places
> in my code. For performance purposes, should I consider modifying my
> data structure to embed these "features" as part of the data to ensure
> that it is only calculated once?
Yes, unless these features eat too much memory (then recalculating might be
cheaper).
If you need the features only for the big total, a wrapper analogous to
MyList below is a good choice
data FeatureThing = FT { feature1, feature2 :: Int, feature3 :: Bool, ...,
thing :: Thing }
, otherwise incorporate the features directly in Thing (like the size is
incorporated in Set/Map).
> Or can I rely on Haskell to do that for me?
No, you can't rely on that.
> For instance, do I need to create the equivalent of:
>
> data MyList a = MyList {mylist::[a], mylength::Int}
>
>
>
> Thanks again for all your generous advice.
------------------------------
Message: 5
Date: Thu, 6 May 2010 15:37:20 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] When, if ever, does Haskell
"calculate once"?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
On Thu, May 06, 2010 at 11:35:15AM -0700, Travis Erdman wrote:
> Two questions here, I think they might be related, perhaps even the same, but
> I am not sure, so I will ask both:
>
> Q1: Re the function f below, I like the first implementation as it's
> "cleaner", but is the second implementation necessary for performance
> purposes?
>
> -- g = some CPU intensive function
>
> -- alternate 1
> f a b = c + (g b)
> where
> c = dosomethingelse a (g b)
>
> -- alternate 2
> f a b = c + saveit
> where
> saveit = g b
> c = dosomethingelse a saveit
You need alternative 2. In general, GHC (and, I imagine, other
Haskell compilers) do not do much common subexpression elimination,
because in some cases it can be a *pessimization*. The classic example is
length [1..1000000] + length [1..1000000]
vs
let a = [1..1000000] in length a + length a
The first will execute in constant space, since each list will be
lazily generated as needed by the length function and then the garbage
collector will come along behind length and get rid of the nodes that
have already been processed. However, in the second expression, the
garbage collector cannot get rid of the nodes that are already
processed by the first call to length, since the second call to length
still needs the list. So the entire list [1..1000000] will end up
being in memory at once.
So, if you want to be sure that something is only computed once, you
must introduce the necessary sharing yourself by giving it a name.
>
>
> Q2: Imagine that I might be creating a custom data structure. I need to
> access both the data in that structure, but also "features" (don't know
> proper comp sci term) of the data structure. For instance, consider a
> Haskell list. The stuff in the list is the data, whereas the length of the
> list is what I am calling a "feature" here. Some of my features might be
> quite a bit more computationally intensive than "length", and may be
> referenced multiple times in many different places in my code. For
> performance purposes, should I consider modifying my data structure to embed
> these "features" as part of the data to ensure that it is only calculated
> once? Or can I rely on Haskell to do that for me? For instance, do I need
> to create the equivalent of:
>
> data MyList a = MyList {mylist::[a], mylength::Int}
There's no magic going on here, if you call a function to compute some
complicated feature of a data structure multiple places in your code,
it will be computed multiple times, just like in any other language.
Caching the features you need as in the above example is a good idea
if the data structures won't change often, and you really do need the
features many times.
-Brent
------------------------------
Message: 6
Date: Thu, 06 May 2010 21:51:47 +0200
From: legajid <[email protected]>
Subject: [Haskell-beginners] [Fwd: Binary tree algorithm]
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Oops, mistake in sender name.
Hi,
i wanted to write an algorithm for loading a binary tree, then get the
values in order and other operations.
So, i created a data type :
data AR a = R a (AR a) (AR a) | N deriving (Show, Ord, Eq)
for an example : R 30 (R 10 (N) (R 20 N N )) (R 40 (N) (R 50 N N ))
the main problem i had is : how to update such a complex value, to add
another one.
After hours of trying (and error !) my solution is : find where to
insert the new value, then read the whole tree and copy its values,
except for the one for insert.
The tree must be read entirely as long as there are values to insert.
For large numbers of values, i guess calculation time will increase
seriously.
I wrote it using "basic" Haskell capabilities. Are there some modules
that manage this in a quicker way? using mutable variables ?
Below is my code. How can it be improved ?
Several limitations to my program (i could solve them) :
. only Int values (strings should not be a problem)
. minimum 2 values to make a tree
. no duplicate values :it's used to find the node where to insert a new
value. To allow duplicates, i should generate a unique "node id".
-- cre [30, 10, 40, 50, 20]
cre :: [Int] -> AR Int
cre val =
-- add values except the first one
cre' (tail val) arb
where
-- init tree with first value
arb=R (head val) N N
-- Add values to the tree
cre' :: [Int] -> AR Int -> AR Int
cre' [] arb = arb -- at the end, get last value for the tree data
cre' (x:xs) arb =
cre' xs (cre'' x arb)
-- Find the node where to insert the new value and proceed
cre'' :: Int -> AR Int -> AR Int
cre'' n arb =
cre''' n arb (r, gd)
where
(r, gd)= trouve n arb -- insert at node value r, g(auche) ou
d(roite)
-- Read the whole tree and update the specified node to insert the new
value
cre''' :: Int -> AR Int -> (Int, String) -> AR Int
cre''' _ N _ = N
cre''' n (R x y z) (r, gd) =
R x (cre''' n y' (r,gd)) (cre''' n z' (r,gd))
where
-- left value (<)
y' = if x == r && gd=="g" then R n N N
else y
-- right value (>)
z' = if x == r && gd=="d" then R n N N
else z
-- find the node where to insert the value
trouve :: Int -> AR Int -> (Int, String)
trouve n (R x y z)
| n <= x && y == N = (x, "g")
| n <= x = trouve n y
| n > x && z == N = (x, "d")
| n > x = trouve n z
trouve n (N) = (0, " ")
Thanks for your comments and help.
Didier.
------------------------------
Message: 7
Date: Thu, 6 May 2010 22:32:42 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] [Fwd: Binary tree algorithm]
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Thursday 06 May 2010 21:51:47, legajid wrote:
> Oops, mistake in sender name.
>
> Hi,
> i wanted to write an algorithm for loading a binary tree, then get the
> values in order and other operations.
>
> So, i created a data type :
> data AR a = R a (AR a) (AR a) | N deriving (Show, Ord, Eq)
> for an example : R 30 (R 10 (N) (R 20 N N )) (R 40 (N) (R 50 N N ))
>
> the main problem i had is : how to update such a complex value, to add
> another one.
insert :: Ord a => a -> AR a -> AR a
insert x ar@(R y l r)
| x < y = R y (insert x l) r
| x == y = ar
| otherwise = R y l (insert x r)
insert x N = R x N N
However, this might lead to very skewed trees. In general it is preferable
to use balanced trees to prevent that. Then you would store the size (or
the depth) in the nodes alongside the data and rebalance the tree when it
becomes too skewed. There are packages for trees on Hackage, also you could
look at the implementation of Data.Set for deeper insights.
> After hours of trying (and error !) my solution is : find where to
> insert the new value, then read the whole tree and copy its values,
> except for the one for insert.
> The tree must be read entirely as long as there are values to insert.
> For large numbers of values, i guess calculation time will increase
> seriously.
If you don't balance the tree, you risk that its depth (and hence an
insert) is O(size), making the building of a tree of size n an O(n^2)
algorithm [okay, that is the worst case, when the list of items to insert
is basically sorted; more often it would be a depth of O(n^0.5) or so].
With a balanced tree, the depth is O(log size), making the building an
O(n*log n) algorithm.
Also, for efficiency, you should make the tree strict (at least the
structure),
data AR a = R a !(AR a) !(Ar a)
>
> I wrote it using "basic" Haskell capabilities. Are there some modules
> that manage this in a quicker way?
Search Hackage for "tree", look at Data.Set.
> using mutable variables ?
>
> Below is my code. How can it be improved ?
> Several limitations to my program (i could solve them) :
> . only Int values (strings should not be a problem)
> . minimum 2 values to make a tree
> . no duplicate values :it's used to find the node where to insert a new
> value. To allow duplicates, i should generate a unique "node id".
>
> -- cre [30, 10, 40, 50, 20]
> cre :: [Int] -> AR Int
> cre val =
> -- add values except the first one
> cre' (tail val) arb
> where
> -- init tree with first value
> arb=R (head val) N N
>
> -- Add values to the tree
> cre' :: [Int] -> AR Int -> AR Int
> cre' [] arb = arb -- at the end, get last value for the tree data
> cre' (x:xs) arb =
> cre' xs (cre'' x arb)
>
> -- Find the node where to insert the new value and proceed
> cre'' :: Int -> AR Int -> AR Int
> cre'' n arb =
> cre''' n arb (r, gd)
> where
> (r, gd)= trouve n arb -- insert at node value r, g(auche) ou
> d(roite)
>
> -- Read the whole tree and update the specified node to insert the new
> value
> cre''' :: Int -> AR Int -> (Int, String) -> AR Int
> cre''' _ N _ = N
> cre''' n (R x y z) (r, gd) =
> R x (cre''' n y' (r,gd)) (cre''' n z' (r,gd))
> where
> -- left value (<)
> y' = if x == r && gd=="g" then R n N N
> else y
> -- right value (>)
> z' = if x == r && gd=="d" then R n N N
> else z
>
> -- find the node where to insert the value
> trouve :: Int -> AR Int -> (Int, String)
> trouve n (R x y z)
>
> | n <= x && y == N = (x, "g")
> | n <= x = trouve n y
> | n > x && z == N = (x, "d")
> | n > x = trouve n z
>
> trouve n (N) = (0, " ")
>
> Thanks for your comments and help.
>
> Didier.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 4
****************************************
