Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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. Re: How to "add column" to a Table? (Michael Orlitzky)
2. Re: Partition a number or optimize (Ertugrul S?ylemez)
3. Re: Partition a number or optimize (Animesh Saxena)
4. Re: Partition a number or optimize (Mike Meyer)
5. This year's Google Summer of Code (Kim-Ee Yeoh)
6. Data and Typeable for an opaque type (Elise Huard)
----------------------------------------------------------------------
Message: 1
Date: Mon, 27 Apr 2015 09:25:08 -0400
From: Michael Orlitzky <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] How to "add column" to a Table?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
On 04/27/2015 02:46 AM, martin wrote:
>
> Aren't you adding a *row* to a Table which allows rows of multiple
> shapes? What I am looking for is an operation which adds a *column*
> to a regular table, i.e. one where all rows have the same shape.
>
Oh, shit =)
Adding a column is a lot harder and does need some kind of "heterogenous
list" library. To do it without one, you need something like,
https://github.com/orlitzky/tuple/commit/8f6623b827f2192343c4fa4d520a4eb173033d9d
That has one advantage: you can understand what it's doing. But it's
not, uh, what's the word -- "aesthetically pleasing." My "prepend" is
basically your "addColumn," and you can see that the type is,
prepend :: a -> b -> c
but that there's a functional dependency,
a b -> c, b c -> a
which basically means that the output tuple's type is going to depend on
the input tuple's type and the type of the element that you're
prepending to it. You can make this work on a table, too:
type Table a = [a]
addColumn :: Prep a b c => a -> Table b -> Table c
addColumn col = map (prepend col)
But if you know the type of the new (bigger) row at compile-time, what
you probably want instead is fixed-vector-hetero. Then you can write,
import qualified Data.Vector.HFixed as H ( cons )
...
addColumn col = map (H.cons col)
That will work for any HVector row type, but you need to either specify
or have the result type inferred. Otherwise you'll get an ambiguous type
error. So this won't work:
ghci> let p1 = (1,"mjo",9000,True) :: Person
ghci> let t1 = [p1] :: Table Person
ghci> addColumn "new" t1
But this would,
ghci> addColumn "new" t1 :: Table (String, Int, String, Int, Bool)
[("new",1,"mjo",9000,True)]
If the result type can't be inferred, the tuple solution I mentioned
earlier might be less annoying, but switching "prepend" to "append" is
up to you!
------------------------------
Message: 2
Date: Mon, 27 Apr 2015 16:19:20 +0200
From: Ertugrul S?ylemez <[email protected]>
To: Animesh Saxena <[email protected]>, The Haskell-Beginners
Mailing List - Discussion of primarily beginner-level topics related
to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Partition a number or optimize
Message-ID: <[email protected]_W_723V_1_36_000>
Content-Type: text/plain; charset="utf-8"
> Now i wrote a crude parts function to do this
>
> nparts 0 = []
> nparts n = [n] : [x:xs | x <- [1..n`div`2], xs <- nparts(n - x)]
>
> which is a bad bad example of recursion coz it?s slow!
It's not the recursion that makes it slow, but its asymptotic runtime,
which is O(2^n). This one might run slightly faster:
intParts :: Integer -> [[Integer]]
intParts n = do
x <- [1..n]
let r = n - x
if r > 0
then map (x :) (intParts (n - x))
else [[x]]
Verify that this function takes a lot of time for an argument as small
as 20, because it finds 2^19 partitionings. You need to eliminate
candidates early. For example if you know that you only need
2-partitionings, then there is no need at all for the recursion and you
can get away with O(n). Alternatively you can eliminate certain
partitions by changing the third line.
x <- [2..n]
This finds partitions of at least 2. Or introduce a stop-early
condition.
Greets,
Ertugrul
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150427/e5ae1589/attachment-0001.sig>
------------------------------
Message: 3
Date: Mon, 27 Apr 2015 22:23:44 +0800
From: Animesh Saxena <[email protected]>
To: Ertugrul S?ylemez <[email protected]>
Cc: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Partition a number or optimize
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
I did find a better solution but it?s still slow
let cities = 6
let clinics = 10
let populations = [1,10000,2,3,400,1]
let nparts n k = filter ((==n) . sum) $ replicateM k [1..n]
let d2 = nparts clinics cities
let d1 = map maximum (map (\x -> zipWith (/) populations (map (\n->
fromIntegral n) x)) $ d2)
maximum $ zipWith (\n x -> (n `div` x) + (n `mod` x) ) populations $ d2 !!
(head $ filter ((==minimum d1) . (d1 !!)) [0..])
here also nparts take time?.if we choose clinics > 10
Heres the problem statement
The World Health Organization (WHO) wants to establish a total of B
vaccination clinics across Ncities to immunization people against
fatal diseases. Every city must have at least 1 clinic, and a clinic
can only vaccinate people in the same city where they live. The goal
is to minimize the number of vaccination kits needed in the largest
clinic. For example, suppose you have:
2 cities and
7 clinics to be opened.
If 200,000 is the population of the first city and
500,000 is the population of the second city, then
two clinics can open in the first city and
five in the second. This way,
100,000 people can be immunized in each of the two clinics in the
first city, and
100,000 can be immunized in each clinic in the second city.
So the maximum number of people to be immunized in the largest clinic is 100,000
-Animesh
> On Apr 27, 2015, at 10:19 PM, Ertugrul S?ylemez <[email protected]> wrote:
>
> as 20, because it finds 2^19 partitionings. You need to eliminate
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150427/cf27bc86/attachment-0001.html>
------------------------------
Message: 4
Date: Mon, 27 Apr 2015 11:21:16 -0500
From: Mike Meyer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Partition a number or optimize
Message-ID:
<CAD=7U2DpvTGzhw37-BzBL=cCw4p6_eEDLiZN=v3u3hcahg7...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
You don't want to do full search here. You want to do a "branch and bound"
search, keeping track of the current best value (which suggests the State
monad) and then terminating searches of subtrees when the best possible
value for that subtree is worse than the current global best possible.
I haven't looked into doing this in Haskell, but it should be a lot faster
than trying to search the full tree.
On Mon, Apr 27, 2015 at 9:23 AM, Animesh Saxena <[email protected]>
wrote:
> let cities = 6
> let clinics = 10
> let populations = [1,10000,2,3,400,1]
> let nparts n k = filter ((==n) . sum) $ replicateM k [1..n]
> let d2 = nparts clinics cities
> let d1 = map maximum (map (\x -> zipWith (/) populations (map (\n->
> fromIntegral n) x)) $ d2)
> maximum $ zipWith (\n x -> (n `div` x) + (n `mod` x) ) populations $ d2 !!
> (head $ filter ((==minimum d1) . (d1 !!)) [0..])
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150427/c79b27c9/attachment-0001.html>
------------------------------
Message: 5
Date: Tue, 28 Apr 2015 14:20:57 +0700
From: Kim-Ee Yeoh <[email protected]>
To: "[email protected]" <[email protected]>
Subject: [Haskell-beginners] This year's Google Summer of Code
Message-ID:
<capy+zdsb9g7bmqutrbnfke6zm7nrh2owqfykpd79bqr4n9b...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
will see one of the actively helpful members of this list, Sumit Sahrawat,
help contribute to making a full-featured Computer Algebra System an
open-source reality.
He will take the IHaskell package (inspired by IPython) one step closer to
feature parity with Mathematica:
https://www.google-melange.com/gsoc/project/details/google/gsoc2015/sumit_sahrawat/5750085036015616
Sumit: Congrats for bagging GSOC !
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150428/b0fb8930/attachment-0001.html>
------------------------------
Message: 6
Date: Tue, 28 Apr 2015 11:37:49 +0200
From: Elise Huard <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Data and Typeable for an opaque type
Message-ID:
<CAHfyCqke_e2rg8aNdaxmeqmKvPEJBC_p1b4ChhSLFYxMK=4...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi,
I'm working on an open source patch, but stumbled upon the following
problem: I'm introducing a type that is basically a pointer in a FFI
library, pointing to an opaque type (which I'm told is common
practice).
-- | An opaque type encapsulating a font in C.
data Font_Opaque
type Font = Ptr Font_Opaque
The problem is that insertion in the current code would require this
to be an instance of Data and Typeable.
In this case (gloss library) I've not 100% understood why that's a
requirement, I've been grepping (case-insensitive) for typeOf, constr,
gfold, and I've not found any obvious use.
Anyway, the rough-and-ready approach for this would be to manually
define instances of Data and Typeable for the opaque type - my
question is: what would sensible implementations look like for such a
type?
Thank you,
Elise
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 82, Issue 41
*****************************************
